容器

一、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。

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有