Containers

发布时间：2011-5-31 11:35
分类名称：STL

[vector]

性能：

末端插入删除效率高，中间效率低。

要求：

assignable && copyable

注意：

1. 一旦内存重新分配，所有的reference，pointers，iterators都将失效。

   保留内存的方法：

   1. 使用reverse()函数。（注意，reverse出来的内存，不能直接引用）
   2. 初始化的时候，分配足够的空间
2. vector使用reverse()不能缩减内存容量。所以，即便删除元素，不会导致内存重新分配，其reference，pointers，iterators都将继续有效。到如果是insert操作，可能会导致内存重新分配，从而导致reference，pointers，iterators失效。
3. 缩减vector容量的办法，使用swap()函数。（vector<T>(v).swap(v);）
4. 将vector作为一般Arrary是来使用（而且是个动态数组）。C++标准规格书将确保vector中的元素都是连续分布的。将vector作为数组操作时（&v[0]），要注意分配足够大的内存，不然会发生越界访问。

混淆：

size(), max_size(), capacity()

例子代码：

    vector<int> nTest(10, 0);

    nTest.reserve(20);

    cout << "size() " << nTest.size() << endl;

    cout << "max_size() " << nTest.max_size() << endl;

    cout << "capacity() " << nTest.capacity() << endl;

输出

size() 10                    （当前实际存储的元素数量）

max_size() 1073741823        （vector能存储的最大元素数量）

capacity() 20                （vector在重新分配空间之前，能容纳的最大数量）

reverse(), resize()

错误代码：

vector<char> myVec;

myVec.reserve(100);

char szTest[] = "how do you do";

memcpy(&myVec[0], szTest, sizeof(szTest));

编译没有问题，运行的时候，可能你的运气比较好，不会崩溃；可能你的运气差，一运行就崩溃了。

原因：

vector 的reverse只是增加了vector的capacity，但是size没有改变！ resize同时改变了vector的capacity和size！

reserve是容器预留空间，但并不真正创建元素对象，在创建对象之前，不能引用容器内的元素，因此当加入新的元素时，需要用push_back()/insert()函数。

resize是改变容器的大小，并且创建对象，因此，调用这个函数之后，就可以引用容器内的对象了，因此当加入新的元素时，用operator[]操作符，或者用迭代器来引用元素对象。

[Deque]

性能：

两端插入删除效率高，中间效率低。

要求：

assignable && copyable

注意：

1. 存取元素时，deque内部多了一个间接过程，速度比vector稍微慢点。
2. 不只一块内存，其max_size可能更大。
3. 不支持对容量和内存重新分配时机的控制。除了头尾，在其他任何地方安插和删除元素，将导致reference，pointers，iterators都失效。deque重新分配由于vector，因为重新分配后，无需复制其中的元素。
4. 内存可以缩减。（标准不保证）

区别（vector）：

deque不提供capacity和reserve支持。

deque多了push_front和pop_front支持。

[List]

性能：

不支持随机存取（所以不知道at(), []），在list遍历元素很缓慢。在任何位置安插和移除的速度都很快。

要求：

assignable && copyable

注意：

1. 安插和移除操作不会使得reference，pointers，iterator失效。
2. lists对异常处理方式，要么操作成功，要么什么都不发生，不会"只成功一半"。
3. lists不提供容量，空间重新分配，没有必要，每个元素拥有独立的内存，删除之前一直有效。
4. lists提供不少特殊成员函数，比使用通用的算法函数效率更高。
5. back和front函数，不检测容器是否为空，所以需要手动检测。（所有的容器都不检测）

[Sets & Multisets]

性能：更具特定的排序准则，自动将元素排序。（Multisets运行重复排序）。内部建立二叉树，使得搜索性能很高。

要求：

assignable && copyable && comparable

注意：

1. 排序准则：
   1. 反对称（antisymmetric）

if x < y is true, then y < x is false.

1. 可传递

if x < y is true and y < z is true , then x < z is true.

1. 非自反

   x < x is false forever.

1. 其内部通常以平衡二叉树（或者红黑树）构建的。
2. 一个重要限制：由于是自动排序，所以不能直接更改元素内部的值。改变元素的值，需要先删除之，在插入之。
3. 迭代器的角度看，元素是常数。
4. 元素的比较只能用在相同的类型中。（元素和排序准则必须有相同的型别）
5. 由于Sets和multisets优化了元素搜索速度，所以使用其成员函数来搜索。
6. sets insert(单参数)会返回一个pair<iterator, bool>值。
7. asdf

[Maps & Multimaps]

性能：和Sets multisets一样，只不过maps中的元素成了一个pair，而不是一个value。

要求：

value    ：assignable &&copyable

key        ：comparable