C++ 容器（一）：顺序容器简介

C++提供了使用抽象进行高效编程的方式，标准库中定义了许多容器类以及一系列泛型函数，使程序员可以更加简洁、抽象和有效地编写程序，其中包括：顺序容器，关联容器和泛型算法。本文将简介顺序容器（vector，list和deque）的相关内容。

1.顺序容器的概念

标准库vector类型，就是一种最常见的顺序容器，它将单一类型元素聚集起来成为容器，然后根据位置来存储和访问这些元素，这就是顺序容器。顺序容器的元素排列顺序与其值无关，而仅仅由元素添加到容器里的次序决定。

标准库定义了三种顺序容器：vector，list和deque。它们的区别在于访问元素的方式，以及添加或删除元素相关操作的运行代价。如下表：

（1） 头文件
为了定义一个容器类型的对象，必须先包含相关的头文件：

#include <vector>  // vector
#include <list>    // list
#include <deque>   // deque

（2） 定义
所有容器都是类模版，要定义某种特殊的容器，必须在容器名后加一对尖括号，里面提供存放元素的类型：

vector<string> sVec; // empty vector that can hold strings
list<int> iList;     // empty list that can hold ints
deque<float> fDeque; // empty deque that can holds floats

（3）初始化
容器的构造函数：

注意： 所有的容器类型都定了默认构造函数，用于创建制定类型的空容器对象。默认构造函数不带参数。为了使程序更加清晰、简短，容器类型最常用的构造函数时默认构造函数。在大多数的程序中，使用默认构造函数能达到最佳运行性能，并且使容器更容易使用。

• 将一个容器初始化为另一个容器的副本

vector<int> iVec;
vector<int> iVec2(iVec);   // ok
vector<double> dVec(iVec); // error, iVec holds int not double
list<int> iList(iVec);     // error, iVec is not list<int>

注意：讲一个容器复制给另一个容器时，必须类型匹配（容器的类型和元素的类型都必须相同）。

• 初始化为一段元素的副本
  通过使用迭代器，间接实现将一种容器内的元素复制给另一种容器。使用迭代器时，不要求容器类型相同，容器内的元素类型也可以不相同，只要它们相互兼容，能够将要复制的元素转换为所构建的新容器的元素类型，即可实现复制。

vector<string> sVec;
// initialize sList with copy of each element of sVec
list<string> sList(sVec.begin(), sVec.end());
// calculate the midpoint in the vector
vector<string>::iterator mid = sVec.begin() + sVec.size() / 2;
// initialize front with first half of sVec: the elements up to but not including *mid
vector<string> front(sVec.begin(), mid);

// also can initialize with a pointer
char* words[] = {"first", "second", "third", "forth"};
int sizeOfWords = sizeof(words) / (sizeof(char*));
vector<string> word2(words, words + sizeOfWords);

// cout
for ( int idx=0; idx<sizeOfWords; idx ++ )
    cout << word2[idx] << endl;

• 分配和初始化指定数目的元素
  创建顺序容器时，可显式地指定容器大小和一个（可选的）元素初始化式。容器的大小可以是常量或者非常量表达式，元素初始化式必须是可用于初始化其元素类型对象的值：

const list<int>::size_type listSize = 64; // also can be: int listSize = 64
list<std::string> lstr(listSize, "str");  // 64 strings, each is str

vector<int> iVec(listSize); // 64 ints, each initialized to 0 

（4）容器内元素的类型约束
C++语言中，大多数类型都可用作容器的元素类型。容器元素类型必须满足最基本的两个约束：

• 元素类型必须支持赋值运算；
• 元素类型的对象必须可以复制。

除此外，一些容器操作对元素类型还有特殊要求。如果元素类型不支持这些要求，则相关的容器操作就不能执行：我们可以定义该类型的容器，但不能使用某些特定的操作。

另外，旧版C++标准中，指定容器作为容器类型时，必须使用如下空格：

vector<vector<int> > myVec;  // the space required between close >

而在新版标准中，并无要求：

vector<vector<int> > myVec; // ok
vector<vector<int>> myVec;  // ok

2.顺序容器的操作

每种顺序容器都提供了一组有用的类型定义以及以下操作：

• 在容器中添加元素；
• 在容器中删除元素；
• 设置容器大小；
• （如果有的话）获取容器内的第一个和最后一个元素

（1）容器定义的类型别名

例如：

// iter is the iterator type defined by vector<string>
vector<string>::iterator iter;

// cnt is the difference_type type defined by vector<int> 
vector<int>::difference_type cnt;

（2）容器内元素操作

• begin和end成员

注意：
(a) 迭代器范围是左闭右开区间，标准表达方式为：

// includes the first and each element up to but not including last
[first, lase)

(b) 容器元素都是副本。在容器中添加元素时，系统是将元素值复制到容器里，被复制的原始值与新容器中的元素互不相关，此后，容器内元素值发生变化时，被复制的原值不会收到影响，反之亦然。

(c) 不要存储end操作返回的迭代器。添加或者删除vector或deque容器内的元素都会导致迭代器失效。

vector<int> v(42);
// cache begin and end iterator
vector<int>::iterator first = v.begin(), last = v.end();

while( first!= last ) // disaster: this loop is undefined
{
    // insert new value and reassign first, which otherwise would be invalid
    first = v.insert(++first, 2);
    ++ first; // advance first just past the element we added
}

• 添加元素

// add elements at the end of vector
vector<int> iVec;
for ( int idx=0; idx<4; ++ idx )
{
    iVec.push_back( idx );
}

// insert an element
vector<string> sVec;
string str("Insert");
// warning: inserting anywhere but at the end of a vector is an expensive operation
sVec.insert(sVec.begin(), str);

// insert some elements
sVec.insert(sVec.begin(), 10, "Anna");
string array[4] =  {"first", "second", "third", "forth"};
sVec.insert(sVec.end(), array, array+4);

• 容器大小的操作

vector<int> iVec(10, 1); // 10 ints, each has value 1
iVec.resize(15);     // adds 5 elements of value 0 to back of iVec
iVec.resize(25, -1); // adds 10 elements of value -1 to back of iVec
iVec.resize(5);      // erases 20 elements from the back of iVec

注意：resize操作可能会使迭代器失效。在vector或deque容器上做resize操作可能使其所有迭代器都失效。对于所有容器类型，如果resize操作压缩了容器，则指向已删除的元素的迭代器失效。

• 访问元素

注意：使用越界的下标，或调用空容器的front或back函数，都会导致程序出现 严重的错误。

• 删除元素：与插入元素对应容器类型提供了删除容器内元素的操作。

注意：
(a) pop_front操作通常与front操作配套使用，实现栈（先进先出）的方式处理：

while ( !vec.empty() )
{
    // do something with the current top of vec
    process(vec.front()); 
    // remove first element
    vec.pop_front();
}

(b)删除一个或一段元素更通用的方法是erase操作。erase操作不会检查它的参数，使用时必须确保用作参数的迭代器或迭代器范围是有效的。

(c) 寻找一个指定元素的最简单的方法是使用标准库的find算法（编程时需要添加头文件#include <algorithm>）。find函数需要一对标记查找范围的迭代器以及一个在该范围内查找的值作为参数。查找完成后，返回一个迭代器，它指向具有指定值的第一个元素或超出末端的下一位置。

string searchValue("find");
vector<std::string> vec(1, "find");
vector<string>::iterator iter = std::find(vec.begin(), vec.end(), searchValue);
if ( iter!= vec.end() )
    cout << *iter << endl;

(d) 删除所有元素，可以用clear或将begin和end迭代器传递给erase函数。

vec.clear(); // delete all the elements within the container
vec.erase(vec.begin(), vec.end()); // equivalent

• 赋值与swap

赋值操作中，首先删除其左操作数容器内的所有元素，然后将右操作数容器中的所有容器插入到左边容器中：

vec1 = vec2; // replace contents of vec1 with a copy of elements in vec2
// equivalent operation using erase and insert
vec1.erase(vec1.begin(), vec1.end()); // delete all elements in vec1
vec1.insert(vec2.begin(), vec2.end()); // insert vec2

注意：
(a) swap操作不会删除或插入任何元素，而且保证在常量的时间内刷新交换。由于容器内没有移动任何元素，因此迭代器不会失效。

(b) 在这里补充一点，vector容器大小有两个描述参数size和capacity。size前面已经讲述过，指容器中当前已存储元素的数目，而capacity存储的是容器所分配的存储空间可以存储的元素总数。一般来说capacity >= size。在clear, 赋值（c1 = c2），assign（不超过原容器大小）等操作中，并未改变容器的capacity，也就是说，只是把已经分配好的内存上写入的元素数据清掉或者重新赋值，但并未对存储空间进行变动；但是swap操作时，size和capacity都会改变。

vector<int> vec(100); // size: 100, capacity: 100;
vec.clear();          // size: 0, capacity: 100

vector<int> vec2(50);
vec = vec2;           // size: 50, capacity: 100

vector<int> vec3(30);
vec.assign(vec3.begin(), vec.end()); // size: 30, capacity: 100

vec.swap(vec3); // error!

vector<int> v1(30), v2(50);
v1.swap(v2); // v1: size 50, capacity 50; v2: size 30, capacity 30

基于此原因，有些时候，当我们想删除一个容器的所有元素的同时，又想把容器占用的内存释放掉时，clear并不能完全实现这一目的，但是可以通过swap:

vector<int> vec(100);      // size 100, capacity 100
vector<int>().swap( vec ); // size 0, capacity 0

(c) vector容器中有reserve操作，可以设定存储空间大小：

vector<int> vec(24);  // size 24, capacity 24
vec.reserve(50);      // size 24, capacity 50
cout<< "size" << vec.size() << endl << 
    "capacity" << vec.capacity() << endl;

3.结束语

我们很喜欢使用容器，因为确实很便捷，相比于数组，它可以很随意的实现元素的添加、删除等。我们也无需担心内存分配的问题，因为标准库会帮我们都搞定。但是我们最好还是了解一下。

以vector为例，为了支持快速的随机访问，vector容器的元素以连续的方式存放，即每一个元素都挨着前一个元素存储。当我们向容器中添加元素时，想想会发生什么：如果容器中已经没有空间容纳新元素，由于容器必须连续存储以便索引访问，所以不能在内存中随便找个地方来存储新元素，而是必须重新分配存储空间，存放在旧存储空间的元素被复制到新存储空间里，接着插入新元素，最后撤销旧的存储空间。如果vector容器在每次添加新元素时，都要这么分配和撤销内存空间，那么其性能将会非常慢！所以，标准库不会这么做，为了使vector容器实现快速的内存分配，其实际分配的容量要比当前所需的空间大一些，例如分配旧存储空间n倍（例如2倍）大小的新存储空间，这样的策略显著提高了其效率。

vector容器的内存分配策略是以最小的代价连续存储元素，通过访问上的便利弥补其存储代价，虽然list容器优于vector容器，但是大部分情况下人们还是觉得vector更好用。实际中vector的增长效率比起list和deque通常会更高。

参考文献：

• 《C++ Primer中文版（第四版）》，Stanley B.Lippman et al. 著， 人民邮电出版社，2013。

最后

以上就是自信宝贝为你收集整理的C++ 容器（一）：顺序容器简介的全部内容，希望文章能够帮你解决C++ 容器（一）：顺序容器简介所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。