一、vector
数据结构是动态数组。支持随机存取，时间复杂度是O(1)。迭代器是随机存取迭代器。
在尾端添加或删除元素时，时间复杂度是O(1)。在其他位置添加或删除元素时，需要移动该位置后面的所有元素，每一次移动调用赋值运算符。
vector容量很重要有两个原因：
1.一旦内存重新分配，与vector元素相关的所有references、pointers、iterators都会失效。
2.内存重新分配很耗时间。
避免重新分配内存的最好方法是使用reserve()保留适当容量。
vector不能使用reserve()来缩减容量，这一点和string不同。
两个vector交换内容后，两者的容量也会互换，下面的例子虽然保留了元素，却缩减了容量：
1 template<class T> 2 void shrinkCapacity(std::vector<T> &v) 3 { 4 std::vector<T> tmp(v); 5 v.swap(tmp); 6 }
可以利用下面的语句直接缩减容量：
1 std::vector<T>(v).swap(v);
swap()之后原先所有的references、pointers、iterators都换了指涉对象，所以它们都失效。
插入元素和删除元素，都会使“作用点”之后的各元素的references、pointers、iterators失效。如果插入操作甚至引发内存重新分配，那么该容器身上的所有references、pointers、iterators都会失效。
二、deque
数据结构是动态数组。支持随机存取，接口和vector几乎一模一样。迭代器是随机存取迭代器。
deque通常实现为一组独立区块，第一区块朝某方向扩展，最后一个区块朝另一方向扩展。
与vector相比，deque功能上的不同处在于：
1.两端都能快速插入和删除元素，时间复杂度是O(1)。
2.存取元素时，deque的内部结构会多一个间接过程，所以元素的存取和迭代器的动作会稍微慢一些。
3.迭代器需要在不同区块间跳转，所以必须是特殊的智能指针。
4.在对内存区块有所限制的系统中（例如PC系统），deque可以内含更多元素，因为它使用不止一块内存。因此deque的max_size()可能更大。
5.除了头尾两端，在任何地方插入和删除元素，都将导致指向deque元素的任何pointers、references、iterators失效。
deque的内存重分配优于vector，因为其内部结构显示，deque不必在内存重分配时复制所有元素。
6.deque的内存区块不再被使用时会被释放。deque的内存大小是可缩减的。
三、list
list使用一个双向链表来管理元素。迭代器是双向迭代器。
list与vector和deque存在明显区别：
1.list不支持随机存取。
2.任何位置上插入和删除元素都非常快，时间复杂度是O(1)，因为无需移动任何其它元素。实际上内部只是进行了一些指针操作。
3.插入和删除不会造成指向其它元素的各个pointers、references、iterators失效。
4.list对于异常有着这样的处理方式：要么操作成功，要么什么都不发生。
list所提供的成员函数与vector和deque的不同：
1.由于不支持随机存取，list即不提供下标运算符，也不提供at()。
2.list不提供容量、空间重新分配等操作函数，因为每个元素都有自己的内存，在被删除之前一直有效。
3.list提供了专门用于移动元素的成员函数。较之同名的STL通用算法，这些函数执行起来更快，因为它们无需拷贝或移动，只需调整若干指针即可。
四、set和multiset
set和multiset会根据特定的排序准则，自动将元素排序。两者不同处在于multiset允许元素重复而set不允许。迭代器是双向迭代器。
如果没有传入特别的排序准则，就采用标准库函数对象less<T>，以operator<对元素进行比较，以便完成排序。
set和multiset通常以平衡二叉树实现。自动排序的主要优点在于使二叉树在查找元素时具有良好性能。
自动排序造成set和multiset的一个重要限制：你不能直接改变元素值，因为这样会打乱原本正确的顺序。
因此，要改变元素值，必须先删除旧元素，再插入新元素。
有两种方式可以定义排序准则：
1.以模板参数定义。
2.以构造函数参数定义。
set和multiset提供了特殊的查找函数，这些函数是同名的STL算法的特殊版本。这些优化算法的时间复杂度是O(logn)，STL算法的时间复杂度是O(n)。
要删除与某值相等的元素，只需调用erase()，它返回被删除元素的个数：
1 std::set<Elem> coll; 2 3 coll.erase(value);
如果multiset含有重复元素，你不能使用erase()来删除这些重复元素中的第一个。你可以这么做：
1 std::multiset<Elem> coll; 2 3 std::multiset<Elem>::iterator pos; 4 pos = coll.find(elem); 5 if (pos != coll.end()) 6 coll.erase(pos);
这里应该采用成员函数find()，而非STL算法find()，因为前者速度更快。
作用于序列式容器和关联式容器的erase()函数，其返回值有以下不同：
1.序列式容器提供下面的erase()成员函数：
iterator erase(iterator pos);
iterator erase(iterator beg, iterator end);
2.关联式容器提供下面的erase()成员函数：
void erase(iterator pos);
void erase(iterator beg, iterator end);
存在这种差别，完全是为了性能。在关联式容器中查找某元素并返回后继元素可能颇为耗时，因为这种容器的底部是以二叉树完成。
无论是将排序准则作为第二个模板参数传入，或是采用标准库函数对象less<T>，通常你都会将排序准则定义为类型的一部分。
但有时必须在执行期处理排序准则，或者你可能需要对同一种数据类型采用不同的排序准则。
此时你就需要一个用来表现排序准则的特殊类型，使你能够在执行期间传递某个准则。以下程序说明了这种做法：
1 #include <iostream> 2 #include <set> 3 #include "print.hpp" 4 5 using namespace std; 6 7 template<calss T> 8 class RuntimeCmp 9 { 10 public: 11 enum cmp_mode{normal, reverse}; 12 13 private: 14 cmp_mode mode; 15 16 public: 17 RuntimeCmp(cmp_mode m = normal) : 18 mode(m) 19 { 20 } 21 22 bool operator()(const T &t1, const T &t2) const 23 { 24 return mode == normal ? t1 < t2 : t2 < t1; 25 } 26 27 bool operator==(const RuntimeCmp &rc) 28 { 29 return mode == rc.mode; 30 } 31 }; 32 33 typedef set<int, RuntimeCmp<int>> IntSet; 34 35 void fill(IntSet &set); 36 37 int main() 38 { 39 IntSet coll1; 40 fill(coll1); 41 PRINT_ELEMENTS(coll1, "coll1: "); 42 43 RuntimeCmp<int> reverse_order(RuntimeCmp<int>::reverse); 44 IntSet coll2(reverse_order); 45 fill(coll2); 46 PRINT_ELEMENTS(coll2, "coll2: "); 47 48 coll1 = coll2; 49 coll1.insert(3); 50 PRINT_ELEMENTS(coll, "coll: "); 51 52 if (coll1.value_comp() == coll2.value_comp()) 53 cout << "coll1 and coll2 have same sorting criterion" << endl; 54 else 55 cout << "coll1 and coll2 have different sorting criterion" << endl; 56 } 57 58 void fill(IntSet &set) 59 { 60 set.insert(4); 61 set.insert(7); 62 set.insert(5); 63 set.insert(1); 64 set.insert(6); 65 set.insert(2); 66 set.insert(5); 67 }
程序输出如下：
coll1: 1 2 4 5 6 7
coll2: 7 6 5 4 2 1
coll1: 1 2 3 4 5 6 7
coll1 and coll2 have same sorting criterion
五、map和multimap
map和multimap将key/value pair当做元素，它们可根据key的排序准则自动将元素排序。multimap允许重复元素而map不允许。迭代器是双向迭代器。
元素的次序由它们的key决定，和value无关。如果使用者未传入特定排序准则，就使用标准库函数对象less<T>，以operator<来进行比较。
map和multimap通常以平衡二叉树实现。map可作为关联式数组来运用。
map和multimap根据元素的key自动对元素进行排序。自动排序这一性质使得map和multimap身上有了一条重要的限制：你不可以直接改变元素的key，因为这会破坏正确次序。
要修改元素的key，你必须先移除拥有该key的元素，然后插入拥有新的key/value的元素。
有两种方式可以定义排序准则：
1.以模板参数定义。
2.以构造函数参数定义。
map和multimap不支持元素直接存取，因此元素的存取通常是经由迭代器进行。不过有个例外：map提供下标运算符，可直接存取元素。
在map和multimap中，所有元素的key都被视为常数。因此元素的实质类型是pair<const key, T>。
这个限制是为了确保你不会因为变更元素的key而破坏已排好的元素次序。所以你不能针对map或multimap调用任何变动性算法。
你不能对它们调用remove()，因为remove()算法实际上是以一个参数值覆盖被移除的元素。如果要移除map和multimap的元素，你只能使用它们所提供的成员函数。
如果你一定得改变元素的key，只有一条路：以一个value相同的新元素替换掉旧元素。下面是个模板函数：
1 namespace MyLib 2 { 3 template<class Cont> 4 inline 5 bool replace_key(Cont &c, 6 const typename Cont::key_type &old_key, 7 const typename Cont::key_type &new_key) 8 { 9 typename Cont::iterator pos; 10 pos = c.find(old_key); 11 12 if (pos != c.end()) 13 { 14 c.insert(typename Cont::value_type(new_key, pos->second)); 15 c.erase(pos); 16 return true; 17 } 18 else 19 { 20 return false; 21 } 22 } 23 }
map提供了一种非常方便的手法让你改变元素的key。只需这样做：
1 coll["new_key"] = coll["old_key"]; 2 coll.erase("old_key");
有三个不同的方法可以在map中插入一个元素：
1.运用value_type
为了避免隐式类型转换，你可以利用value_type传递正确类型。value_type是容器本身提供的类型定义。例如：
1 std::map<std::string, float> coll; 2 3 coll.insert(std::map<std::string, float>::value_type("otto", 22.3));
2.运用pair<>
1 std::map<std::string, float> coll; 2 3 coll.insert(std::pair<std:;string, float>("otto", 22.3)); 4 coll.insert(std::pair<const std::string, float>("otto", 22.3));
上述第一个insert()语句内的类型并不正确，所以会被转换成真正的元素类型。为了做到这一点，insert()成员函数被定义为成员模板。
3.运用make_pair()
1 std::map<std::string, float> coll; 2 3 coll.insert(std::make_pair("otto", 22.3));
和做法2一样，也是利用成员模板insert()来执行必要的类型转换。
六、各种容器的运用时机
1.缺省情况下应该使用vector。vector的内部结构最简单，并允许随机存取，所以数据的存取十分方便灵活，数据的处理也够快。
2.如果经常要在序列头部和尾部插入和删除元素，应该采用deque。如果你希望元素被移除时，容器能够自动缩减内存，那么你也应该采用deque。
此外，由于vector通常采用一个内存区块来存放元素，而deque采用多个区块，所以后者可含有更多元素。
3.如果需要经常在容器的中段执行元素的插入、删除和移动，可考虑使用list。list提供特殊的成员函数，将元素从A容器转移到B容器，时间复杂度是O(1)。
但由于list不支持随机存取，所以如果只知道list的头部却要访问list的中间元素，性能会大打折扣。和所有以节点为基础的容器相似，只要元素还是容器的一部分，
list就不会令指向那些元素的迭代器失效。vector则不然，一旦超过其容量，它的所有iterators、pointers、references都会失效；执行插入或删除操作时，也会令
一部分iterators、pointers、references失效。至于deque，当它的大小改变，所有iterators、pointers、references都会失效。
4.如果你要的容器是这种性质：每次操作若不成功，便无效用。那么你应该选用list，或是采用关联式容器。
5.如果你经常需要根据某个准则来查找元素，那么应当使用以该排序准则对元素进行排序的set或multiset。
6.如果想处理key/value pair，请采用map或multimap。
7.如果需要关联式数组，应采用map。
8.如果需要字典结构，应采用multimap。
- 还没有人评论，欢迎说说您的想法！
客服
