@唐風
重復數量有限而且不多時，還是可以接受的……
范型庫經常會做這種事情。比如iterator_traits，numeric_limits……

concepts嘛…… 砍了也好……
支持C++標準的謹慎態度。

沒有concepts，雖然代碼很難寫，但也已經寫出來了。
但concepts一旦加入標準，又發現它不是想象中那么好的話，就再也拿不掉了。

C++就是拿boost這種庫當試驗田。
等某個特性確實各方面都符合條件時，再加入標準之中。
而不像java、.net，動不動就加入一個；過段時間發現不好，再加入一個替代品；使得庫很臃腫；還要一直保持向下兼容。
C++不是商業公司擁有的…… 沒人有這么好的精力做這些事情……

@溪流
哈哈，被你看出來了……
我就是一anti-OOP者……

其實也不是完全是這樣。只是太多人將OOP當作萬能藥了。
以為OOP的設計，就一定是好的設計。OOP成分越多，設計越好。
我反對的是這種態度。

@溪流
我再使用上面的觀點狡辯一次吧……

1. 非虛析構
如果、假設、萬一真的出現了這樣的需求 —— 幾乎不可能 —— 需要被繼承而且以父類指針delete子類。

還可以這樣：
class StringDerivable {
String s_;
public:
virtual ~StringDerivable();
};
并從StringDerivable繼承。


2. 虛析構
如果一開始就使用虛析構，無論是否需要被繼承 —— 幾乎不可能 —— 用戶都必須承擔一個虛指針的代價。


非虛析構對于不需要繼承的客戶來說，沒有額外的代價。對需要繼承的變態客戶來說，也有辦法實現 —— 多一個步驟。
這是貫穿整個C++語言設計的一個重要原則：0代價原則。
虛析構無論客戶是否需要，多態的代價都必須承受。


設計不單單只是你做了什么，也包括你沒有做什么。

代碼字體挺好看的。
知名應用抄錯了：

enum {value = sizeof(test<T>()) == sizeof(one)};

這里要以一個0去調用test<T>：
enum {value = sizeof(test<T>(0)) == sizeof(one)};
如果T不是內建類型，0就可以隱式轉換到T的成員的指針，否則匹配省略號版本。


詳細見這里，包含一個更簡單的不使用SFINAE實現(代碼也更多)is_buildin的方法：
http://www.shnenglu.com/Charlib/archive/2009/03/16/76799.html

@李佳
如果只是練習著玩玩，機器碼寫都沒問題。

如果是實際應用上，這么實現這么簡單的需求 —— 10行代碼了事 ——用到匯編和線程局部存儲，那……
有點過了……

別搞了兄弟，用vsprintf之類的函數就可以了。

@溪流
何時需要虛析構函數？當通過父類類指針delete子類時。
String這種類型不應該作為基類，也不應該被多態使用，所以虛析構函數是不必要的。

@溪流
一個虛函數都沒有，繼承來做啥？

SetProp/GetProp …… 居然還有這種函數……

SetWindowLongPtr(hwnd, i , data );
data = GetWindowLongPtr(hwnd, i );

i 是一個數組的index。
數組大小和窗口注冊時填入的cbWndExtra有關。

有個重要的地方忘記說了……
虛析構函數是不需要的

"必須要將fopen或者freopen放到所有變量定義的下面，否則會編譯錯誤..."
C89是不能隨處定義自動變量的，只能在函數開始，所有語句之前。
C99和C++允許使用前定義。
可能是C-free（好東西）默認建的是C工程？


win下不是"CONIN$"與"CONOUT$"嗎？我記錯了？


其實也可以這樣：
FILE* fin = fopen("in.txt","r"); /* or fin = stdin */
FILE* fout = fopen("out.txt","w"); /* or fout = stdout */

/*
使用fprintf(fout, format, ... ); fscanf(fin, format, ... );
*/

any會使用動態內存，效率比較低。而且，你也不希望看到如下代碼：
CSrcRelease ... 產生異常吧？

可以用function<void ()>來保存bind的結果，并在析構函數中調用。
或者，使用Loki::ScopeGuard。

nelem是size_t類型，不是size_t*
不一定是升序，也可以是降序，跟fcmp參數有關。
(void*)&i,(void*)&a是不必要的，(const)T*到const void*的轉換可以是隱式的。

好像說偏題了……

chinaunix上討論時，他并沒有說是哪一題，只說有題目提示說要用scanf/printf。他自己也記不清楚是哪一題了。
2602是我自己找出來的，覺得這題比較變態。

如果樓主在做其他題目時，發現題目下面有提示說使用scanf/printf的話，還請通知我一下，謝謝~_~

同意cm的意見：緩存的層次越少越好。
真要做，就直接與VirtualAlloc, mmap, sbrk交互，不通過crt。


解決內存碎片的算法除了垃圾收集以外，也是存在的。
但這個算法是要client端（內存的使用者）配合才行。
如果內存分配器對內存的請求的方式一無所知，只靠猜測，這種generic內存分配器已經沒有提高余地了。
要繼續提高內存分配效率，必須讓client告訴內存分配器他會以何種方式使用內存。內存分配器根據不同的使用方式來優化自己的算法。

例如，假設實現一種類似<<c interfaces and implementations>>中的arena，并且不通過crt，直接使用VirtualAlloc。當arena被釋放的時候，確實就不存在任何碎片。

@iSsay
這個嘛，你去測吧，嘿嘿。


做2602的背景是這樣的：chinaunix上有人說poj上有題目建議使用scanf/printf，否則做不出來。
然后我就去試了試。 先隨便在網上扒了一份代碼，TLE……
干脆自己寫，用g++提交，結果就過了，換c++提交，第2次就跳到no1去了。
不過oj上的時間測不準，精度太低。其他人多提交幾次可能也會沖到no1去。


iostream的格式化是靜態分派的，printf/scanf是動態分派。
在格式化上，iostream的機制理論上的效率是會高而不是低。

iostream輸在格式化后的其他事情上去了。iostream下還有一層client可知的streambuf層次。

iostream多這一個層次，就將"格式化"與"緩沖"工作分開了。
你可以復用iostream的格式化功能，但給它一個不同于file的目的地，比如socket、memory、null —— 只要傳遞給它相應的streambuf就行。

對于memory作為目的地，stl提供了stringbuf。并有相應的stringstream在iostream上增加一些接口，使得client不用直接操縱stringbuf。
C標準庫相應有sprintf,sscanf。但要這么看，sprintf不能擴容。
類似的還有在我最開始接觸vector的時候，也覺得它慢。因為我拿vector和固定大小數組比較。但當我不做oj，數組大小不方便提前計算出時，怎么辦？
而且，stl其實還有strstream……

以socket作目的地？ printf/scanf怎么搞？
自己實現printf/scanf嗎？ 你覺得這容易嗎？
如果不自己實現printf/scanf，那就只能利用緩存。
拿這種情況和iostream + socketbuf比較，那才公平。

iostream還有很多亂七八糟的功能，locale，expcetion，callback，fillchar……

總之，在一個只處理build-in類型，數組/緩沖大小可以提前計算并按最大值提供，不需要按需提供/擴展，不處理多語言的情況下 —— OJ的情況下 ——確實利用不了iostream,vector等提供的功能。
但OJ做多了，就反過來說它們的不是，就很扯蛋了。
說實話，OJ的代碼普遍是上不得臺面的，大家自己心里清楚。
根本就沒有一點點軟件工程的美感在里面。可復用嗎？不能，都是一次性筷子，完全是為了AC而已。

在實際開發中，沒有這么多美好的前提條件。

即使iostream功能比printf/scanf多得多，如果iostream的格式化比printf/scanf有數量級的差異，沒得說，那肯定是iostream實現得太爛……
同樣的是格式化和讀寫文件操作，多一個間接層次就導致效率數量級的下降？那不是寫得爛能是什么呢？找個好點的吧。
還有用VC6的OJ（非POJ），你能拿它怎么辦呢？

@iSsay
標準IO？cin,cout,cerr,clog不就是標準IO么？

你指的是formatted io？

@溪流
一個google帳號好像可以建5個項目。每個項目好像可以有2g空間。但是只能放和代碼相關的哦，否則被發現了google帳號會被禁用。

每個項目可以傳文件上去，比如打包好的代碼。

還有一個repository。原來只提供svn的，后來加入了hg。不過沒有加git。
svn的repository就是上面說的那樣，擁有者才有commit權限以及授權的權限。
普通用戶只有check out的權限。要么只看不改，要么找你要授權，要么給你發補丁。


自己機器上做一個svn repository的事…… 我也這樣干過……
所以很痛恨svn，所以打算用git。

@iSsay
就事論事而已，我不是大牛，pku上就沒過幾道題。
代碼里面有很多速度測試的代碼，所以很長。

其實是用istream::read 一次讀完所有輸入到buf。
將buf[0],buf[2],buf[4], ... 看作a
將buf[1],buf[3],buf[5], ... 看作b
然后高精度加高精度。
加法時沒有沒有轉換到0-9 直接用'0'-'9'計算，輸出時也省去了另一次轉換，直接輸出一個字符串。

木有

@溪流
別人只能check out不能commit。除非你授權。或者把補丁發給你。
用git吧，趨勢……

@iSsay
少扯了，uther是我臨時注冊的馬甲。

@溪流
嗯嗯，你說中了，炒作~_~
類似的還有很多……

"經實踐,在大規模輸入輸出下,cin,cout效率遠遠低于scanf()和printf()"
遠遠低于？ 太夸張了……
野蠻人拿到打火機可能也會抱怨"還不如我的木頭"。

看看這個：
http://acm.pku.edu.cn/JudgeOnline/problemstatus?problem_id=2602

第1個uther的，就是用C++ iostream做的。

如果不加保護，兩種寫法都有可能產生2個實例。

書上采用第2種形式居多的原因，可能是因為Gof的書……
第1種形式是Scott Meyers后來發明的。

@溪流
你就沒領會后者的精妙~_~

后者的精妙之處在于：增加的東西不可能輕易拿掉 —— 否則會破壞舊有代碼。
反之，加入原本不存在的東西是很容易的事情……

如果某個功能確實很常用，你可以再得到這種反饋之后將其作為aux添加進去。
反之，如果一開始就有某個設計糟糕的功能存在了，你得到反饋之后也很難將其去掉，并且還要一直維護這個糟糕設計…… 很惡心


我很欣賞lua的設計，將lua庫分為core和aux兩個層次，而不是混淆在一起。
加上client，總共就是3個層次。
保持core的精簡對維護是非常重要的。
aux本身實現就不難，多提供一些對維護影響不大。是否提供完全看需求 —— 這是否是很常見的一種使用方式。

以unix的機制、策略論來說：core就僅僅提供機制，aux將一些常用策略打包，方便client使用。


設計之初就要考慮如何將core精簡到最小。這對日后維護是非常有幫助的。
一種精簡的大方向就是僅提供機制。比如vprintf_parse，就是一種機制。

客戶會如何使用它？就是策略了。客戶可以非常多的方式（dst不同）使用它。
可以預見：將string作為dst是一種很常見的使用策略。
仍然可以先不提供它…… 萬一這種估計錯誤了呢-_-
如果估計正確，大量代碼的使用者向你抱怨"為什么不提供string.format?"，你再提供也來得及~

其他的精簡方式…… 再慢慢總結吧……

@溪流
1.
這是C++的缺陷…… 當初可能沒想到模板會被這么用，所以模板的功能其實還比較弱。
即使比較弱，也比java和C#強大，它是真正的代碼生成器……
C#的模板有一些約束，java的根本就是垃圾……
所以，模板還是很復雜的……

更本質的說，其實體現的是一種ducking type，以單一函數作為組件之間交互的接口，而不是整個類型。ruby、python、lua這種動態類型語言都支持ducking type。而C++的模板只支持編譯時的ducking type。
C++社區給這種使用方式取了一個新的名字，叫concepts……

ducking type可能屬于新東西，而且很可能是意外產物（比如C++、python、lua；ruby好像是設計之初就考慮到這種用法），所以沒有提供專門的、顯示的通過短小的代碼（比如interface聲明）就可以表達的方式。只能通過文檔了……

說穿了，那些抵觸這種設計的，要么是偷懶不想看文檔，要么是已經學會OO就不想學任何其他新事物，要么就是理解能力不夠……

心里疙瘩放下吧……
1.1. 雖然沒有專門的語法支持，但語言還是會檢查的，比如C++編譯時出錯，其他3個語言運行時出錯。
1.2. 比如python標準庫中，序列就沒有單獨的size()成員。所有的序列都通過len得到長度。已經開始向這種思想靠攏了。
1.3. stl也這么多年了……



2
我對0依賴的看法不是"難"，而是"通常沒有必要"。
應該盡可能復用已有的優秀的代碼。
盡可能向已有的，還過得去不算垃圾的標準靠攏，而不是自己獨立發明一套，結果在實際應用中無法融合。

當然，這和練習編程技巧相抵觸……
所以我想提出一些建議，既可以練習；并且練習的結果是可以真正派上用場的。

比如，你可以考慮實現這樣一個函數：
int vprintf_parse(void (*handler)(const char* s,void* context),void* context
const char* format, va_list arg );

按vprintf的標準去解析format與arg。每處理完一個%就調用handler一次。
由handler去考慮將s"輸出"到哪里。
這樣的話，vprintf_parse就可以用于很多很多地方：傳遞不同的hanlder給它就行。
當然，你也可以用它來實現string.format。 但一定要將vprintf_parse暴露出來，否則窩在string.format中太暴殄天物了。


更進一步…… 還可以提供一些讓客戶代碼擴展的機制，讓它自己定義%后的轉義符，以及處理方式。



3
我的意思是，這種方式是行不通的。
你要插入的元素是T吧？
std::set<std::list<T> > 元素是 std::list<T> 哦， 不是T了。
比較也是按std::less<std::list<T> >比較，而不是T。

不管multiset的底層實現是rbtree還是rbtree+list，都需要真正定義一個類，將底層實現的接口adapt一下才行。僅僅typedef是不夠的……

再給你說個玄乎一些，不那么實際的理論吧……

一種設計傾向是"添加直到無法添加"。
一種設計傾向是"減少直到無法減少"。

我傾向于后者。也相信你寫過一些代碼之后會對前者感到反感。

1.
"盡管很“巧合”有幾個一樣的接口"
stl組件之間的通信就是通過這種"巧合"。


2.
為什么要零依賴？ 這個需求很怪……

想練習發明輪子的心情可以理解……
再給你提供一個練習而又不是重復發明的東西吧：
將printf和scanf的解析過程抽象出來。
這樣，string就只是管理內存就可以了。
format交給別的地方去做。
相互之間保持正交。

這樣，format的src和dst可以是FILE*,socket, 以及任何可擴展長度的順序結構，比如各種string，std::vector,std::deque,std::list。
不要將format的功能"埋葬"到你那個string中，太可惜了。將它剝離出來。


還有stl中的反向迭代器其實是有單獨一個模板的，在<iterator>中，通常不需要自己手工編寫。
你可以重復發明它一次，然后應用于你的各種容器之上，而不是重復發明多次。



3.
至少std::multiset<T>和 std::set<std::list<T> > 或 std::set<std::vector<T> > 語意都是不同的。

@溪流
好像是這樣的…… 很尷尬……

RbTree和Set還好一些，因為它們的接口不一定相同，可能真的需要用RbTree實現Set，并增加或隱藏一些成員。

我以前遇到的情況是實現了一個allocator，然后想運用到STL的容器當中去，發現了這個問題……

下面這種想當然的代碼行不通：
template<typename T>
typedef std::vector<T,my_allocator<T> > my_vector;

而且my_vector和vector行為完全相同。不像RbTree，本來就需要Set去adapt一下。比如下面3種代碼，都很惡心：

1.
template<typename T>
my_vector : public std::vector<T,my_allocator<T> > {};

2.
template<typename T>
my_vector : std::vector<T,my_allocator<T> > {
// forwarding functions
};

3.
template<typename T>
my_vector {
std::vector<T,my_allocator<T> > v_;
// forwarding functions
};


后來想想，算了，我的工作就是提供allocator，不負責為其取一個好聽的名字。
敢用allocator的人，肯定知道應該這么用：
std::vector<his_element,my_allocator<T> > v; //一個使用了my_allocator的std::vector。
同樣工作得很好嘛。



相反，使用c++0x的功能，可能還會造成一些問題：
my_vector<int> v; // my_vector是什么東西？

哦，看到這些代碼，才能明白它是什么東西：
template<typename T>
using my_vector = std::vector<T,my_allocator<T>>;


這和typedef的誤用會過多引入不必要的概念是一個道理。

C++0x可以...
好像叫template alias

@bujiwu
map.erase有3個重載
...
返回iterator的erase是不符合STL標準的。

Windows還是linux沒有直接關系。于STL實現有直接關系。
map.erase有3個重載：
void erase ( iterator position );
size_type erase ( const key_type& x );
void erase ( iterator first, iterator last );

返回iterator的erase是不符合STL標準的。

DWORD GetProcessId(HANDLE process); ？？？

@空明流轉
謝謝~_~

請教一下：
"但是如果你使用、修改了別人LGPL協議的源代碼，那么，修改后的源代碼就必須要公開，并且一樣遵守LGPL協議。"

假設這樣一個場景，一個庫L，使用LGPL。
某個家伙，比如我吧，對這個庫作了一些修改，成為L1，并且使用L1做了一個應用程序，叫A1。

必須公開的部分是L1，還是L1+A1 ？


我覺得后者好像說不過去。
因為我總可以將我做的事情分成2步：
1. 發布一個使用LGPL的L1 // 必須公開L1代碼
2. 使用LGPL的L1產生A1 // 貌似不必公開A1代碼？

是這樣嗎？ 謝謝~_~

代碼很好看。

GetN(int n)始終返回1？ 復制時弄錯了？

@Little star
標準就這么規定的。

《C 語言常見問題集》 5.14中介紹了一些古怪的空指針。
“至少PL/I, Prime 50 系列用段07777, 偏移0 作為空指針。
……
CDC Cyber 180 系列使用包含環(ring), 段和位移的48 位指針。多數用戶
(在環11 上) 使用的空指針為0xB00000000000。
在舊的1 次補碼的CDC 機器上
用全1 表示各種數據, 包括非法指針, 是十分常見的事情。
Symbolics Lisp 機器是一種標簽結構, 它甚至沒有傳統的數字指針; 它使用
<NIL, 0> 對(通常是不存在的<對象, 偏移> 句柄) 作為C 空指針。
”

浮點如果是采用IEEE754， 0.0恰好是二進制全0。
但標準沒有保證浮點數一定采用IEEE754。

@Little Star
class C {
/* data declaration */
public:
C() { memset(this,0,sizeof(*this); }
};

改為：
class C {
struct data {
/* data declaration */
} data_;
public:
C() { memset(&data_,0,sizeof(data_); }
};


還是需要注意memset( ... 0 ... );
不能保證： 指針是nullptr，浮點數是0.0, 0.0f, 0.0lf。
能保證：整數是0， 字符是null字符，即'\0'。

@codejie
STL有輸入、輸出、前向、雙向、隨機，5種迭代器。
erase有范圍刪除：
first = v.begin()+start;
v.erase( first, first+min(size,v.size()-start) );

沒有虛函數也不可以亂來。
空指針并不一定是二進制全0。

1.
char* label = 0;

2.
char* label;
memset(&label,0,sizeof(label) );

有平臺上兩者功能不同。

暈……
v.erase(v.begin()+1);

1.要搜kbcwait4ibe，不要搜"虛擬鍵盤"。
2.以下劃線開始的標識符是C/C++語言所保留的啊，同學們……

具備你說的那些能力后，想讀研又是麻煩事了……
會成天想著具備更多的能力，然后成績一塌糊涂……
學校是認成績（以及關系）而不是能力的地方……

刪去最大最小值(O(1)) ???

刪除操作不包括shift？ 不shift的話，剩下的就不是堆了。
刪除操作包括shift，復雜度就是對數。

java的慢，不僅僅是在編譯上，而是在其內存模型上。
即使有JIT也沒用，再優化JIT也沒有用。除非修改其內存模型。
但那是不可能的。

java效率媲美C/C++的實際例子：
要么是是在emulator層上跑C/C++代碼；
要么是例子過于簡單以體現不出java的缺陷；
要么兩者兼有。

說java效率可以C/C++媲美的人，要么是奸商，要么是sb。

哎…… 懶得批了……

有假設就寫到代碼里嘛。
隨便找個編譯單元：
static char assume[sizeof(header)==sizeof(u16)*3?1:-1];

或者就在header下方寫：
typedef int assume[sizeof(header)==sizeof(u16)*3?1:-1]];