标签: 顺序容器

Vector是一种容器。 本章"Sequential Container"是第三章"Strings, Vectors, and Arrays"的扩展。 顺序容器的元素位置，取决于元素加入的顺序；关联容器的元素位置，取决于关联元素的key。 容器classes共享公共的接口，使得它易于学习。 A container holds a collection of objects of a specified type. 9.1 Overview of the Sequential Container ---------------------------------------------------------------- 顺序容器有下面几种类型： vector        : Flexible-size array. deque         : Double-ended queue. list          : Doubly linked list. forward-list  : Singly linked list. array         : Fixed-size array. string        : A specialized container, similar to vector.   string和vector将它们的元素存储在连续的空间里，因此增加或删除元素是很复杂的操作； list和forward_list可以在任何位置快速添加/删除元素，它不支持random访问，而必须用迭代器。 deque更加复杂，它支持random访问，在中间添加/删除元素的开销很大，但在首尾却很方便。 array不支持添加/删除操作，forward_list没有size操作。 一般来说，请使用容器，而不是旧的数据类型。 怎样选择合适的容器呢？  • 除非你有理由选择其他的容器，否则请使用vector。  • 如果你的程序有很多small元素，并且空间matters，不要使用list或forward_list。  • 如果你的程序要求有random访问，那就使用vector或者deque。  • 如果你的程序要求在中间插入或删除元素，就使用list或者forward_list。  • 如果你的程序要求在首尾插入或删除元素，就是用deque。  • 如果你的程序只要求在容器的中间使用reading input的方式插入元素，并且要求random访问：     再次确认你是否真的要求在中间插入？     如果真的要求，则使用list插入，再转换成vector。 9.2 Container Library Overview ---------------------------------------------------------------- 所有的容器都提供了以下操作，比如： iterator C c; c.size(); c.insert(args); ==, != c.begin(); 顺序容器提供了以下操作： C seq(n); C seq(n, t); 每种容器都定义在了自己的同名头文件中， deque定义在了deque头文件中，list定义在了list头文件中。 容器实际上是类的模板，我们必须提供额外的信息才能产生特定的容器类型。 这里的额外信息，大部分但并不是所有，是指元素的类型。 容器几乎可以是任何类型的，当然也可以是容器类型： listdequeint lst; 容器的范围是个很重要的概念，一般使用迭代器获取它： [begin, end) 我们可以使用容器内的类型，来定义我们的变量，比如： liststring::iterator iter; vectorint::difference_type iter; liststring a = {"Milton", "Shakespeare", "Austen"}; auto it1 = a.begin();    //a的迭代器 auto it2 = a.rbegin();   //a的反向迭代器 auto it3 = a.cbegin();   //a的const迭代器 auto it4 = a.crbegin();  //a的const反向迭代器 虽然我们不能使用传统的数据进行复制的操作，但是容器array可以： arrayint, 10 digits = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; arrayint, 10 copy = digits; 容器array不支持赋值操作： copy = {0};  //非法操作 另外，swap除了可以调换容器内部的两个元素之外，还能够调换两个容器本身： vectorstring svec1(10); vectorstring svec2(24); swap(svec1, svec2); 两个相同类型的顺序容器，可以进行比较操作。 9.3 Sequential Container Operations ---------------------------------------------------------------- 9.4 How a vector Grows ---------------------------------------------------------------- 为了保证对vector的快速访问，vector是连续存储的，因此， 如果没有空间来增加新的元素，整个vector都必须迁移到新的地点。 由于有allocation strategy的存在，vector的效率通常比list或deque要高: c.shrink_to_fit()  // 返还被保留的空间，但不做保证 c.capacity()       // 返回剩余的空间量 c.reserve(n)       // 为容器保留n空间量，但绝不会缩减空间 9.5 Additional string Operations ---------------------------------------------------------------- 9.6 Container Adaptors ---------------------------------------------------------------- Essentially, an adapter is a mechanism for making one thing act like a different type. 容器适配器的概念有些难以理解，需要慢慢来。 如果想让一个deque表现得像栈一样，则： stackint stk(deq); 如果想从vector来将长stack，则： stackstring, vectorstring str_stk; 所有的adaptor都需要添加或删除元素的能力，因此array不能被建立成adaptor。 结语： 本章内容是对之前学过的vector、string等顺序容器的总结和扩展。 本章内容具备自身的逻辑性，因此虽然内容很多，但是易于理解和记忆（所以笔记很少）！