总结：C++ STL 容器.doc

总结：C+ STL 容器STL的叫法是“容器”，标准库里面容器不多，数组、链表、红黑树，实现都不负责thread safe、mutable之类，对比下Java的，选择很多，也挺混乱。序列容器：动态数组vector，双端队列deque（本质是动态数组加索引），链表list。关联容器：set，map，multiset，multimap，bitset（叫bit_array更合适）。容器适配器：stack，queue，priority_queue。除了bitset，都用到模板，声明大概是这样的：STL Standard Containers，点击加号展开！STL Container Adaptors，点击加号展开！C+是注重效率的，所以STL很强调一点就是amortized的性能，下面的表很不错，还可以用来速查：Sequence containersAssociative containersHeadersMemberscomplexvectordequelistsetmultisetmapmultimapbitsetconstructor*constructorconstructorconstructorconstructorconstructorconstructorconstructorconstructordestructorO(n)destructordestructordestructordestructordestructordestructordestructoroperator=O(n)operator=operator=operator=operator=operator=operator=operator=operatorsiteratorsbeginO(1)beginbeginbeginbeginbeginbeginbeginendO(1)endendendendendendendrbeginO(1)rbeginrbeginrbeginrbeginrbeginrbeginrbeginrendO(1)rendrendrendrendrendrendrendcapacitysize*sizesizesizesizesizesizesizesizemax_size*max_sizemax_sizemax_sizemax_sizemax_sizemax_sizemax_sizeemptyO(1)emptyemptyemptyemptyemptyemptyemptyresizeO(n)resizeresizeresizeelement accessfrontO(1)frontfrontfrontbackO(1)backbackbackoperator*operatoroperatoroperatoroperatoratO(1)atatmodifiersassignO(n)assignassignassigninsert*insertinsertinsertinsertinsertinsertinserterase*eraseeraseeraseeraseeraseeraseeraseswapO(1)swapswapswapswapswapswapswapclearO(n)clearclearclearclearclearclearclearpush_frontO(1)push_frontpush_frontpop_frontO(1)pop_frontpop_frontpush_backO(1)push_backpush_backpush_backpop_backO(1)pop_backpop_backpop_backobserverskey_compO(1)key_compkey_compkey_compkey_compvalue_compO(1)value_compvalue_compvalue_compvalue_compoperationsfindO(log n)findfindfindfindcountO(log n)countcountcountcountcountlower_boundO(log n)lower_boundlower_boundlower_boundlower_boundupper_boundO(log n)upper_boundupper_boundupper_boundupper_boundequal_rangeO(log n)equal_rangeequal_rangeequal_rangeequal_rangeunique memberscapacityreservespliceremoveremove_ifuniquemergesortreversesetresetflipto_ulongto_stringtestanynoneContainer AdaptorsHeadersMembersstackqueuepriority_queueconstructor*constructorconstructorconstructorcapacitysizeO(1)sizesizesizeemptyO(1)emptyemptyemptyelement accessfrontO(1)frontbackO(1)backtopO(1)toptopmodifierspushO(1)pushpushpushpopO(1)poppoppopset、map一般会实现成红黑树，这就是它的模板声明里面不需要一个类似Equal_to之类的functor来判断找到Key没有的原因：它调用两次Compare来判断等于。要是不用排序这个特性，只看效率搜索树一般比不过哈希表。还有一点STL里面iterator是一等公民，主要为了很多算法的效率和封装统一接口，但全是iterator我个人觉得用起来有点不舒服。C+0x里面会有基于哈希表的unordered_xxx系列（就是现在很多实现里面的hash_xxx