|
C++的标准库中提供给了我们容器的概念，今天主要学习的是顺序容器。容器，即可以容纳特定的对象的集合；顺序，即按位置存储和访问元素。能够成为容器元素的对象必须满足最基本的条件：具有赋值和复制操作。引用不能进行赋值，I/O库也不能进行赋值和复制，所以二者不能作为容器容纳的特定对象。顺序容器有三种：vector，list和deque（double-ended queue）。自己学习这一部分的感觉就是：便捷。用C来写数组，需要考虑指针，添加/删除等各种实现，而现在已经有标准库提供的vector数据结构，直接定义使用，调用push_back()/erase()等方法就可以方柏霓的实现对于vector的操作。 1. 顺序容器的定义 使用三种顺序容器之前当然首先要包含其头文件：#include <vector>, <list>, <deque>。有几种基本的构造函数是最基本，也是自己平时最为常用的： vector<int> ivec; //default constructor vector<int> ivec1(ivec) //object initialized, necessary to ensure the same type of container and element vector<int> ivec2(ivec1, ivec1.begin(). ivec1.end()) mid = ivec1.begin() + ivec1.size()/2; vector<int> ivec3(ivec1, ivec.begin(), mid); 自己最为常用的还是先定义再初始化（复制或者循环赋值）。需要注意的一个问题是容器内操作的类型约束，容器提供了一部分通用的操作和一部分某些类型可以使用的操作，使用时要注意区分；另外，容器本身也可以包含另一个容器： vector< vector<int> > lines; //注意<<与>>之间的空格，必须存在否则编译器会解读为输入输出操作符 2. 迭代器与迭代器范围 迭代器为容器提供了一组通用操作，简单来说就是解运算（(*iter).mem/iter->mem），自增减运算（++iter/iter--）与关系运算（iter1 != iter2/ iter1 == iter2）。这里需要注意的是，iter++这样的自增减运算是所有顺序容器都可以使用的，但是由于list属于链表，因此只有list和deque的迭代器可以使用算数运算（iter + n）。出于编程便捷方便的考虑，迭代器范围通通使用左闭合区间[first, last)，即左端的first指向的元素属于范围，而右侧last指向的元素则不属于范围，last指向了最后一个元素的下一个位置，这样设定最大的便利是可以在循环中用作循环终止判定的条件。在实际使用容器编程时，如果对容器进行了添加或删除操作，那么就要小心谨慎地使用迭代器，因为当对容器进行修改的时候，有可能会部分甚至全部地导致迭代器失效，从而引用迭代器时发生不可预知的错误，后面的程序例子中会有体现。 3. 顺序容器的操作 这部分主要来看看C++标准库为我们提供了哪些基本的操作，以下说明的操作大多可以用于各个顺序容器，为编程实现提供了极大的便利。一个容器我们一定会用到的四大操作：添加元素、删除元素、确定大小以及获取容器内的第一个元素和最后一个元素。 3.1 begin()和end()操作 二者分别返回容器的第一个元素和最后一个元素的下一个位置（不可用），可以利用begin() == end()时来判断容器为空。返回的是指向容器元素的迭代器，由于迭代器不是一个简单的指针，而更像是指针的升级版“智能指针”，因此不能直接使用cout << end()这样的语句来查看迭代器的值。 3.2 添加元素 三种顺序容器都可以在尾部添加新元素：obj.push_back()，此时标准库会自动为新元素分配空间，但是由于vectore的原型是数组，而且头部相对固定，所以只有list和deque可以在头部添加元素:obj.push_front()。以上两种操作返回的都是void。 使用insert方法则没有这么多限制，一般的使用方法是：obj.insert(iter, elem); 即在iter指向元素的前方插入元素elem，同时返回新添加元素的迭代器。至于obj.insert(iter, n, elem)和obj.insert.(iter, iterb, itere)则分别表示在iter指向的前方插入n个elem和来由iterb/itere指定范围的元素段。 3.3 关系操作符 对于两个顺序容器间的关系操作判定规则：若二者存在包换关系，则父容器大于子容器；否则则依据二者第一个不同的元素大小来判断。 3.4 容器大小的操作 自己比较常用的就三种：obj.size(), obj.empty()和obj.resize()。之前我们已经使用过前两种，现在说说第三种，resize()可以重新设置容器的大小，若之前size大于设定后的值，则超出的值被舍去；若小于设定后的值，则以默认值初始化填充。 3.5 访问元素 如果容器非空，那么容器类型的front()和back()成员会返回容器内第一个和最后一个元素的引用；对于连续存储的vector和deque来说，可以使用下标访问具体的元素，而对于链表结构的list则不可以。 3.6 删除元素 同添加元素的情况一样，vector也不能使用pop_front()删除头部的第一个元素，而只能使用pop_back()删除尾部的第一个元素；而list和deque可以使用以上两种操作。二者返回类型为void。 如同提供一种更为通用的操作insert来实现添加元素，C++标准库也提供了erase()方法来删除元素。erase(iter)会删除iter指向的元素，当然也可以说使用erase(iterb, itere)删除iterb和itere之间的元素。erase返回删除对象后面元素的迭代器。删除容器内所有元素直接使用obj.clear()即可。下面是一个容器元素删除的例子，调用了find()方法，前提要包含#include <algorithm>头文件。 点击(此处)折叠或打开
 上述程序先是初始化了一个10个元素的list，然后调用find()函数确定元素'5'的迭代器，然后删除之，打印出删除后的list。细心的你不晓得发现了么，list删除元素前后其lst.end()的数值是一样的，虽然list长度减少了，可是end()指向的迭代器没有改变！ 3.7 赋值与swap 容器提供的赋值操作其实是insert和erase二者结合使用的效果，赋值操作符首先删除左值中容器的所有元素，然后将右值容器的元素insert到左边容器中。我们可以使用obj.assign(iterb, iterc)来实现将迭代器iterb和iterc间的元素复制到obj中。由于赋值操作首先要删除左侧容器，所以iterb和iterc不能指向obj本身。、 当使用obj1.swap(obj2)时会将二者交换，但是要注意的是，对于assign而言，操作完成后左侧容器的迭代器全部失效，而swap运算后原有的迭代器全部仍旧有效。 4. vector容器的自增长 终于到了自己感觉惊奇的一节了。vector容器采用连续存储的形式存放数据，由此便于实现按照位置的随机访问读取。但是这样的组织方式却使得在中间插入删除元素、或者重新分配空间相当麻烦。尤其是当向vector中插入元素时，为了保证空间仍旧连续，不能像list那样直接链接即可，而是需要重新申请空间分配，这个过程会导致相当低的性能。但是现实中为什么大家使用vector多于list呢？哈哈，原因在于聪明的C++标准库工程师们设置了vector自动增长的机制，每次初始化后期capacity属性会大于size()，而且如果数据太大需要重新分配时capacity会增大至当前capacity的数倍（不同的实现增长多少不一定，偶自己的库是2倍）。如此就极大的减少了申请分配新空间的开销。vector和deque适合随机访问读取，而list适合添加和删除元素，具体使用哪一种，要根据自己的数据结构对象最频繁的操作来定。一般来说，使用vector多于list。 点击(此处)折叠或打开
 刚刚定义vector的时候起size和capacity都为0，当初始化为12个元素的时候，capacity增大到16个，随后当填充满整个vector时，再添加元素就导致申请分配新的空间，capacity直接翻倍——100。 5. 容器适配器 除了三种基本的顺序容器，C++标准库还提供了“特化”的容器：stack/queue/priority_queue，这里不再细述，给出一个stack的例子程序，其他细节留待用到时补充。 点击(此处)折叠或打开
 |
|
|
