顺序容器

C++ Primer 笔记第九章

容器（Container）是 C++ 标准库提供的，用于存放一系列指定类型对象的数据结构。本章学习的顺序容器（Sequencial Container）指包含了以下特性的容器：

元素按顺序添加进容器
元素的添加顺序与其在容器里的位置一一对应

顺序容器概述

顺序容器主要按以下的两个方面来作出取舍：

添加/删除元素的花销
随机访问（非顺序访问）的花销

顺序容器的特性

根据不同存储的策略，不同的容器的特性也不同：

Vector & String 支持浮动的大小，但添加删除容器中间的元素会很慢
list / forward_list 支持快速添加删除元素，但舍弃了快速的随机访问。Forward_list 没有求 size 的操作。
Deque 支持快速随机访问。添删首尾元素快，中间元素慢
Array 是新标准的容器，不支持添删和改变容器大小。相较于 Build-in Aarray 更安全

<html>

</html>

新标准下的 STL 容器比旧版本下的快上许多，在可以使用的地方尽可能的使用。

顺序容器的选择

通常，选择顺序容器遵循以下的策略：

如果没有特殊需要，尽可能的选择 vector。
如果有很多小元素，而且空间的 overhead 很重要，那么请不要使用 list or forward_list。
如果容器要求大量的随机访问，使用 vector or deque。
如果需要经常在容器中部进行添删操作，请选择 list ro forward_list。
如果程序需要在容器前后进行添删操作，请选择 deque。
如果程序需要在输入数据的时候向容器中部插入数据，而后需要随机访问的话：
1. 首先，看是否真的需要容器中部添加元素。如果而只是想队列有序，使用 vector + sort() 函数排序是个很好的选择。
2. 其次，如果必须要在容器中间添加元素，可以考虑在用 list 做写入的载体，完成写入以后再把 list 拷贝到 vector 中。

总的来说，牵涉到复合要求的情况下，优先按主要操作的需求来选择容器。

如果你并不确定使用哪种容器，那么使用 iterator 来对容器进行操作。Iterator 作为顺序容器的公共操作，无论是在 vector 或 list 上使用都很方便。

标准库容器概况

STL 提供了一些泛型的操作供容器使用。总的来说：

某些操作可以用到所有容器上。
一些操作只能应用到顺序容器上，不能用于关联容器（Associative Container）和无序容器（Unordered Container）。
还有一些操作只适用于一小部分容器。

如果需要使用容器，只用包含名为容器名字的头文件就可以了。

操作的详细分类如下表：

<html>

</html> <html>

</html>

总的来说，容器都是类模板（Class templates），因此需要特别指定元素的类型：

list<Sales_data> // list that holds Sales_data objects
deque<double> // deque that holds doubles

容器对保存类型的限制

总的来说，基本所有的类型的对象都可以被顺序容器保存，容器的元素甚至可以是容器：

vector<vector<int>> vec_vi; // vector of vectors
vector<vector<int> > vec_vi; //old compiler requires a spece bewteen two angle bracket

但某些容器的操作会受到元素类型的限制。比如依靠默认初始化的初始化方法不能用于没有默认初始化的对象：

// assume noDefault is a type without a default constructor
vector<noDefault> v1(10, init); // ok: element initializer supplied
vector<noDefault> v2(10); // error: must supply an element initializer

迭代器

当应用于容器的时候，迭代器的操作是通用的
例外是 Forward list, 不能使用自减操作
以下的迭代器运算只能用于 string,vector, deque, array。
- iter ± n / iter ±= n
- iter1 - iter2
- >, >=, <, ⇐

迭代器的范围

迭代器的范围使用一对迭代器来表示的；begin 指向第一个元素，end 另外一个指向最后一个元素的后一位。总的说来，迭代器的范围可以用一个左闭右开的区间（Left-inclusive Interval）来表示：$$[begin, end)$$ 两点要求：

这两个迭代器必须指向同一个容器
end 可以等于 begin，但是不能在 begin 之前。

一些使用上述概念的假定

begin = end：容器为空
begin != end：容器不为空，begin 指向第一个元素
begin 可以通过自增最后与 end 相等。

遵循上述假定而写出来的循环是安全的：

while (begin != end) {
	*begin = val;
	++begin;
}

使用容器类型成员

前面介绍过几种容器的成员类型，其中：

大多数 iterator 都有自己的 reverse iterator
这些类型实际上都是 type alias

如果要显式的指定容器的成员类型：

container type<element type>::member_name;
//e.g.
vector<int>::difference_type count;

:: 指我们希望使用 iterator 成员及 vector<int> 中定义的 difference_type.

容器成员 begin & end

容器提供了两个成员函数 begin / end ，用于建立迭代的范围。同时提供的还有他们的 const / reverse 版本：

c 开头的是 const 版本，比如 cbegin()
r 开头的是 reverse 版本，比如 rbegin()

没有以 c 开头的版本均存在函数重载：

一个版本接收 const 对象，返回 const_iterator
另外一个版本接收 non-const 对象，返回 iterator

C++ 11 中提供了 auto 关键字，允许编译器对迭代器的类型进行推断：

auto it7 = a.begin(); // const_iterator only if a is const
auto it8 = a.cbegin(); // it8 is const_iterator

初始化 / 定义容器

除 array 以外，基本上所有的容器都拥有两个构造函数：

默认的构造函数，创建空的容器
带 size / 初始值的构造函数

容器的拷贝初始化

容器的拷贝初始化分为两种：

直接拷贝：要求容器与元素的类型必须一致
迭代器拷贝：对容器的类型没有要求。允许使用存在隐式转换的元素进行初始化

// each container has three elements, initialized from the given initializers
list<string> authors = {"Milton", "Shakespeare", "Austen"};
vector<const char*> articles = {"a", "an", "the"};

list<string> list2(authors); // ok: types match
deque<string> authList(authors); // error: container types don't match
vector<string> words(articles); // error: element types must match

// ok: converts const char* elements to string
forward_list<string> words(articles.begin(), articles.end());

鉴于迭代器初始化是通过指定范围实现的，使用迭代器拷贝可以初始化源容器的子集：

// copies up to but not including the element denoted by it
deque<string> authList(authors.begin(), it);

容器的列表初始化

C++ 11 的新标准允许列表初始化容器：

list<string> authors = {"Milton", "Shakespeare", "Austen"};

该方法在显式指定元素的同时，也隐含了容器的 size 信息。

指定大小的初始化

顺序容器 可以通过指定 size 和默认值来进行初始化。初始化会得到与 size 相同数量的元素，每个元素的值都是初始值：

list<string> svec(10, "hi!"); // ten strings; each element is "hi!"

如果不指定初始值，则初始值会进行值初始化：

forward_list<int> ivec(10); // ten elements, each initialized to 0
deque<string> svec(10); // ten elements, each an empty string

需要注意的是，这种初始方法要求元素是 build-in tpye，或者拥有默认构造函数。

该初始化方法只适用于顺序容器，不支持关系容器。

标准库 array 类型

和 build-in array 相同，STL array 也是 Fixed-size 的类型。因此定义 array 需要同时指定大小和类型：

array<int, 10>; // array that holds 10 ints
array<int>::size_type i; // error, array<int> is not a type.

为什么 array 不能使用指定 size 的容器构造函数？

因为大小是 array 类型的一部分。指定 size 的容器构造函数会隐式或者显式的决定容器的大小；允许用户决定 array 的大小可能会有很多潜在的问题。

array 的特性带来了什么影响？

array 的固定大小导致其初始化会受到一些限制：

array 的默认初始化并不会创造一个空的容器。
默认初始化中，元素个数与 array 的 size 相同，所有元素都将进行默认初始化。
如果初始化元素个数小于 array size, 那没有对应初始值的元素会进行值初始化。

array<int, 10> ia1; // ten default-initialized ints
array<int, 10> ia2 = {0,1,2,3,4,5,6,7,8,9}; // list initialization
array<int, 10> ia3 = {42}; // ia3[0] is 42, remaining elements are 0

STL array 与 built-in array 的区别？

STL array 可以进行直接拷贝和赋值，只要 size 和 type 都匹配即可：

int digs[10] = {0,1,2,3,4,5,6,7,8,9};
int cpy[10] = digs; // error: no copy or assignment for built-in arrays
array<int, 10> digits = {0,1,2,3,4,5,6,7,8,9};
array<int, 10> copy = digits; // ok: so long as array types match

赋值与 swap

容器的赋值分为三个类型的操作。具体操作可以参考下图：

<html>

</html>

使用 assign operator 赋值

赋值操作符 =：该操作会直接将右边的容器的整个范围和元素赋值给左边，是替换（replace）的操作。如果左右容器大小不匹配，最后结果以右边容器为准：

c1 = c2; // replace the contents of c1 with a copy of the elements in c2
c1 = {a,b,c}; // after the assignment c1 has size 3

使用 = 对 STL array 赋值，需要匹配容器类型（再次提醒：对于 array, 大小是类型的一部分）：

array<int, 10> a1 = {0,1,2,3,4,5,6,7,8,9};
array<int, 10> a2 = {0}; // elements all have value 0
a1 = a2; // replaces elements in a1
a2 = {0}; // error: cannot assign to an array from a braced list

使用 assign 函数赋值

该种方法是 = 方式的另外一种版本，通过指定元素的个数与元素的初始值来替换原有的容器内容：

list<string> slist1(1); // one element, which is the empty string
slist1.assign(10, "Hiya!"); // ten elements; each one is Hiya

使用 swap 函数赋值

swap 函数用于交换（Exchange）两个同类型容器的内容：

vector<string> svec1(10); // vector with ten elements
vector<string> svec2(24); // vector with 24 
//now svec1 has size 24, svc2 has size 10.
elementsswap(svec1, svec2);

使用 sawp 的要求是什么？

swap 要求进行交换的两个容器必须类型相同。

使用 sawp 进行交换以后，发生了什么样的变化？

swap 对容器内的内容进行了交换。内部的迭代器、引用和指针等等均指向原来的元素：

<html>

</html>

哪些容器有例外？

在使用 swap 交换 string 的时候可能会使迭代器、引用或者指针无效。
在使用 sawp 交换 array 的时候，规则有些不同：
1. 与其他 contianer 不同，交换 array 同时也交换了他们的元素；因此交换 array 所需时间与其元素数量成正比。
2. 这些元素对应的指针、应用或迭代器不会发生交换。他们依然指向原来的位置，只是内容已经发生了变化。

Swap 没有像 copy assignment 一样复制、删除或者插入任何元素。因此，swap 的执行速度非常快（可以在常数时间完成）。

swap 的成员函数形式 a.swap(b) 是 C++11 的新标准。为了向前兼容，请尽量使用非成员版本的 swap。

容器大小操作

除了一个例外，每个容器都有三个与大小相关的操作：

c.size(); // return the number of elements in container
c.empty(); // return true if there are no elements in container
c.max_size(); //return a value that greater or equal the maximum number of elements that container can hold

需要注意的是，forward_list 不提供 size()。

关系运算符

所有容器类型都支持 == 和 != 两种相等性运算符。除了无序关联容器（unordered associative containers）以外，其他容器还支持 >, ≥, ≤, < 这四种关系运算符：

比较的前提：
- 如果使用关系运算符，容器的元素必须定义了相应的关系运算符。
- 容器必须是相同类型，元素也必须是相同类型。

如果满足比较的条件，则通过以下的策略进行比较：

相等性：如果容器大小相等，且对应元素一一相等，那么两个容器相等，否则不等。
大小性：
- 如果容器 A 是容器 B 的子序列，那么 A < B.
- 否则，A 和 B 的大小取决于他们第一个不相等元素的比较结果。

顺序容器的操作

容器相关操作总览

除了 array, 所有的 STL 容器都提供了 Run-time 期间的容器元素操作机制。当然，根据容器的实现方式不同，不同的操作在不同的容器上的效率也不同：

<html>

</html>

需要注意的是，使用对象初始化容器、添加、插入对象到容器这些操作，都是拷贝操作。实际对容器产生影响的不是原来的对象，而是它的拷贝。因此，之后对容器的任何操作不会影响原本的对象。

向容器首尾添加元素

使用 push_back()

使用限制：不能应用于 array, forward_list。
使用方法：

string word;
while (cin >> word)
    container.push_back(word)

使用 push_front()

使用限制：push_front 可用于 for_ward list。
使用方法：

list<int> ilist;
// add elements to the start of ilist
for (size_t ix = 0; ix != 4; ++ix)
ilist.push_front(ix);

由于 push_front() 的机制类似于 stack，因此越靠后被操作的元素越处于容器的前部。比如上例中，操作的顺序是 0-1-2-3 ，而最后在 List 中呈现的结构是 3-2-1-0。

插入元素

对指定位置使用 insert()

对容器指定位置添加元素可以使用 insert 成员。 insert 操作适合除了 forward_list 以外的各种容器（forward_list 有自己单独的一套插入操作。）

insert 接收一个 iterator p 作为插入的位置，该迭代器可以指代容器中任意元素的位置（包括c.end()）。
insert 的插入位置总是在 p 指向的元素之前（因为 insert 可能会插入头元素）
insert 的返回值是一个 iterator, 指向的新增元素序列的第一个元素。
insert 插入值为空的时候，返回 p。

一般的使用方式：

slist.insert(iter, "Hello!"); // insert "Hello!" just before iter

值得注意的是，insert 在对 vector、string 和 deque 中部进行元素插入时，效率很低，需要谨慎使用。

使用 insert() 插入范围内的元素

insert() 有两个重载版本提供了插入范围内元素的功能：

指定元素个数的插入形式：

container.insert(p, element_quantity, value);

这个版本往迭代器 p 指代元素之后插入拥有相同值的，指定数量的元素，比如：

svec.insert(svec.end(), 10, "Anna"); //adding 10 element "Anna" at the end of svec

使用迭代器指定范围的插入形式：

第二个版本接收一对表示范围的迭代器，或者一个初始化列表，并将其插入到迭代器指定的位置之后：

vector<string> v = {"quasi", "simba", "frollo", "scar"};
// insert the last two elements of v at the beginning of slist
slist.insert(slist.begin(), v.end() - 2, v.end());
slist.insert(slist.end(), {"these", "words", "will","go", "at", "the", "end"});

需要注意的是，传入的，表示范围的一对迭代器不能指向正在被添加元素的容器：

// run-time error: iterators denoting the range to copy from
// must not refer to the same container as the one we are changing
slist.insert(slist.begin(), slist.begin(), slist.end());

利用 insert() 范围版本的返回值

C++ 11 中， insert() 会返回一个迭代器，该迭代器指向被插入序列的第一个元素在容器中的位置。利用这个返回值，我们可以写出如下的循环：

list<string> 1st;
auto iter = 1st.begin();
while (cin >> word)
iter = 1st.insert(iter, word); // same as calling push_front

每次插入操作完成后，都会得到一个迭代器指向新元素所在的位置。下次循环使用该迭代器作为新的初始位置；由于 insert() 的插入位置是在迭代器指向位置之前，因此新的元素为以 “push” 的方式添加到之前添加的元素之前。因此，该循环实际上实现了 push_front() 的效果。

使用 emplace 进行操作

C++ 11 中提供了新的 emplace 系列成员来进行元素的插入。与之前提到的插入操作不同，emplace 使用构造的方法在容器中直接产生新的元素。由于这样的方式，emplace 的大部分 parameter 取决于当前容器元素的构造函数需要什么样 parameter。也就是说，emplace 实际上是在容器内指定的位置调用构造函数。

emplace 成员有三个版本：

emplace(iter, arg)：在指定位置生成新的元素，arg 为元素的构造函数所需要的 arguments，可根据构造函数的重载进行变换
emplace_back(arg)
emplace_front(arg)

一些例子：

c.emplace_back(); // using defualt constructor
c.emplace(iter, "999999"); // using Sales_data(string)
c.emplace_front("999999", 25, 15.99); //using Sale_data(isbn, count, price)

访问元素

C++ 提供了四种访问顺序容器元素的操作：

<html>

</html>

使用 back() 、 front() 成员的之前应该确保容器是非空的：

// check that there are elements before dereferencing an iterator or calling front or back
if (!c.empty()) {
	// val and val2 are copies of the value of the first element in c
	auto val = *c.begin(), val2 = c.front();
	// val3 and val4 are copies of the of the last element in c
	auto last = c.end();
	auto val3 = *(--last); // can't decrement forward_list iterators
	auto val4 = c.back(); // not supported by forward_list
}

访问元素的成员返回引用

上述的访问操作均返回绑定指定元素的引用。引用的 const 根据容器是否是 const 决定。

除此之外，如果希望得到正确的返回值（引用），需要显式的定义引用（包括 auto）：

if (!c.empty()) {
c.front() = 42; // assigns 42 to the first element in c
auto &v = c.back(); // get a reference to the last element
v = 1024; // changes the element in c
auto v2 = c.back(); // v2 is not a reference; it's a copy of c.back()
v2 = 0; // no change to the element in c
}

如果没有显式的应用，那么实际完成的是拷贝赋值，得到的是引用绑定元素的副本。

下标访问与安全的随机访问

另外两种访问方式是使用下标访问的方式。这两种方式都要求 index 必须在容器的范围内。但通常，使用下标操作符的方式不会检测 Index 是否在范围内。

如果希望确保 index 是有效的，使用 at() 成员函数。当 index 无效时，该函数会抛出 out_of_range 类型的异常。

删除元素

C++ 也提供了几种方法用于删除容器内删除元素（不适用于 array）：

<html>

</html>

这些成员不会检测其 arugments，删除前必须确保被删除的元素存在。

pop_front() / pop_back()

pop_front() 和 pop_back() 用于删除容器首尾的元素：

类似 push_front()， vector & string 没有 pop_front() 的成员。
类似 push_back(), forward_list 没有 pop_back() 的成员。
这两个成员返回 void。如果需要保存被删除的元素，需要在删除之前存储：

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

删除容器中指定的元素

使用 erase(p) 的重载版本可以删除 p 指向的元素；该成员返回一个迭代器，指向被删除元素所在位置的下一个元素：

<html>

</html>

一个简单的应用 erase() 返回值的实例：

list<int> lst = {0,1,2,3,4,5,6,7,8,9};
auto it = lst.begin();
while (it != lst.end())
	if (*it % 2) // if the element is odd
		it = lst.erase(it); // erase this element
	else
		++it;

删除容器中多个元素

接收双迭代器版本的 erase(b, e) 允许我们删除范围内的元素：

// delete the range of elements between two iterators
// returns an iterator to the element just after the last removed element
elem1 = slist.erase(elem1, elem2); // after the call elem1 == elem2

指定的区间依然是左闭右开的区间，因此这里的 elem2 指向的元素不会被删除。

如果需要清空所有元素，可以使用 clear()

slist.clear(); // delete all the elements within the container

等同于：

slist.erase(slist.begin(), slist.end());

forward_list 的特殊操作

为什么 forward_list 需要单独的一套成员？

之所以这样做事因为 forward_list 特殊的机制。简单来说，forward_list 一个单向的链表数据结构，每一个节点都承担着指向后方节点的任务：

<html>

</html>

由于其单向性，如果按照先断开链接，再添加或删除元素的顺序来操作是行不通的。断开链接后，被添删的元素之前的节点的指向信息无法更新，不知道新的节点在哪里：

<html>

</html>

因此，我们必须通过先建立链接，再添加删除元素的方式，来确保被操作元素之前的节点能够正确的指向新的节点：

<html>

</html>

基于上面的原因， forward_list 没有通用的 insert、emplace 或者 erase 成员。取而代之的是其自身的配套成员：

<html>

</html>

可以看出来的是，如果需要添加 / 删除某一个元素，我们必须先获取其前置节点的位置。因此，上面所有的成员函数，操作的都是迭代器 parameter p 之后的元素。同时，为了方便操作容器的头元素，需要定义一个 off-the-beginning 的迭代器。这就是为什么有 before_begin() 成员的原因。

一些注意事项：

insert_after 函数返回一个指向被插入元素的迭代器。
erase_after 函数返回的是一个指向被删除元素后一位的迭代器。
before_begin() 不能解引用，因为该迭代器指向的是一个不存在的元素。

由于所有的 forward_list 成员函数都需要指向被操作元素之前位置的迭代器，因此在实际应用中需要同时维护两个迭代器：

forward_list<int> flst = {0,1,2,3,4,5,6,7,8,9};
auto prev = flst.before_begin(); // denotes element "off the start" of flst
auto curr = flst.begin(); // denotes the first element in flst
	while (curr != flst.end()) { // while there are still elements to process
		if (*curr % 2) // if the element is odd
			curr = flst.erase_after(prev); // erase it and move curr
		else {
			prev = curr; // move the iterators to denote the next
			++curr; // element and one before the next element
		}
	}

两个迭代器，前置的用于操作当前的元素，后置的用于循环和判断。

改变容器大小

C++中给我们提供一种改变容器大小的成员函数：resize。这个函数有两个版本：

c.reszie(n); // change the size of c to n;
c.resize(n,t); // change the size c to n, initial all new element with value t

当 n 与容器大小不等时：

如果 n < c.size()，那么容器尾部的元素被删除。
如果 n > c.size()，那么会把新元素附加到容器尾部。此情况下要么给元素提供初始值，要么提供默认构造函数。

注意：对容器的 resize 操作也将导致被删除元素对应的迭代器、引用和指针失效。对 vector、string 和 deque 的 resize 可能会导致所有迭代器、引用或指针失效。

容器与迭代器的失效

总结一下容器操作对迭代器、指针和引用产生的影响：

添加元素后：
- 容器是 Vector & String：
  - 存储空间被重新分配：所有指向容器的指针，引用，迭代器均失效。
  - 存储空间没有被重新分配：插入位置之前的指针，引用，迭代器不失效。
- 容器是 Deque:
  - 任何插入到不是首尾位置的元素都会导致所有迭代器，指针，引用失效。
  - 在首尾添加元素，则只有迭代器失效。
- 容器是 List & Forward_List：所有指针，引用，迭代器均有效。

<html>

</html>

删除元素后：
- 指向被删除元素的所有指针，引用，迭代器都将失效。
- 容器是 Vector & String：被删除元素位置之前的指针，引用，迭代器都有效。
- 容器是 Deque：
  - 如果是除首尾之外删除任何元素，那么所有指针，引用，迭代器都会失效。
  - 如果删除尾部元素，尾部迭代器失效。
- 容器是 List & Forward_List 所有指针，引用，迭代器均有效。

<html>

</html>

如何正确的应对迭代器失效的问题？

最小化影响范围：尽量减少需要迭代器必须有效的判定。
及时更新迭代器：使用某些受改变容器大小影响非常大的容器时（比如 vector、deque & string）尤其要注意。

循环中迭代器的维护

使用 erase(p) 的时候不需要手动对迭代器移位。

erase(p) 本身的效果是移除当前元素，并返回一个指向下个元素的迭代器。如果将该返回值交予控制循环的迭代器，那么达到的效果就是删除以后自动将循环迭代器移动到了下一位，因此不需要再添加任何手动的位移。

<html>

</html>

使用 insert(p,N) 需要手动对迭代器向右移两位。

insert(p,t) 往 p 指代元素之前插入元素，并返回指向插入的第一个元素的迭代器。因此 p = insert(p,N) 的效果相当于将循环迭代器往左移动了一位。为了从下一个新元素开始，需要跳过插入的元素，以及之前指向的元素。因此需要右移两位：

<html>

</html>

也就是：

p = insert(p, N);
p += 2；

添删操作中，避免使用缓存过的 end() 迭代器

该点在对 vector、string 和 deque 进行添删操作的时候尤其要注意，因为对以上所有容器的添删操作都会导致 c.end() 返回的迭代器失效。如果将其缓存起来使用，结果会是 Undefined。比如下面的代码：

// disaster: the behavior of this loop is undefined
auto begin = v.begin(),
end = v.end(); // bad idea, saving the value of the end iterator
	while (begin != end) {
		// do some processing
		// insert the new value and reassign begin, which otherwise would be invalid
		++begin; // advance begin because we want to insert after this element
		begin = v.insert(begin, 42); // insert the new value
		++begin; // advance begin past the element we just added
}

当 insert() 被调用以后，end 变量中存储的迭代器就失效了，继续使用该迭代器将会导致 Undefined。正确的做法应该是以循环为单位重新计算 c.end()：

// safer: recalculate end on each trip whenever the loop adds/erases elements
while (begin != v.end()) {
	// do some processing
	++begin; // advance begin because we want to insert after this element
	begin = v.insert(begin, 42); // insert the new value
	++begin; // advance begin past the element we just added
}

Vector是如何增长的

Vector 是一种大小可变的容器。当自身元素超过容器大小时，Vector 会进行自身的扩容。由于 Vector 中元素的存储是连续的，通常的策略是到别的地方申请一块更大的空间，然后将已有的 Vector 内容复制过去，再添加新的元素。这整个过程被称为 Reallocate。

但这个过程有一个问题： Reallocate 需要拷贝整个 Vector，对性能的影响很大。如果严格控制 Vector 的大小，那么理论上每一次插入操作都会使 Vector 进行 Rellocate。

为了尽量减少上述的开销，Vector 被设计成容量远高于其实际的需要的容器。通过这种方式，可以尽量避免 Reallocate 的发生，从而提高 Vector 的性能。

管理容量的成员函数

C++ 为 vector 和 string 提供了一些函数来供他们申请空间：

/* only for vector、string and dqeue */
c.shrink_to_fit(); // request to reduce capacity() to equal size()        

/* only for vector and string */    
c.capacity(); // number of element that c can have before reallocation is necessary  
c.reserve(n); // allocate space for at least n elements

有几点要注意的是：

reserve.(n) 代表申请的空间至少是 n 个元素那么大；但如果请求的 n 小于现有的 capacity, 则什么都不做。
reserve.(n) 申请的空间是为 reallocate 准备的，并不是改变现有的 Vector 元素数量。
shrink_to_fit() 并不一定起作用，返还内存的请求很可能会被忽略。

c.resize() 改变的是容器元素的数量，但并不提升容器的上限；而 c.reserve() 做的事正好相反。

capacity 和 size

Capacity 与 Size 的区别是什么？

Capacity：代表了在不分配新的内存空间的情况下，可容纳最大元素的数量
size 则代表了容器现有元素的数量

Capacity 的增长策略是怎样的？

Vector 的 Capacity 增长策略是将当前的 Capacity 翻倍。但进行 Reallocate 的前提是当前的 size 已经超过了 capacity。比如容器中元素个数与 capacity 的大小均为 4，如果再往容器中添加一个元素，则 capacity 就会翻倍变为 8：

<html>

</html>

通过这样的策略，使用 push_back() 创建 n 个元素的时间复杂度度可以控制在常数 $n$ 之内。

额外的 String 操作

除了一些容器通用的函数以外，string 类本身还提供了一些其专属的操作。这些操作包括创建、修改、搜索、比较，以及类型转换等等。

string 的创建

string 支持三种专属的初始化方式：

<html>

</html>

使用字符串进行初始化时的注意事项

使用 const char* 对 std::string 进行初始化时，初始化的内容会复制到 /0 标记为止。有两种情况会导致该操作 Undefined:
- const char* 字符串不带 /0 结束标记，且没有指定拷贝的长度 n。
- const char* 字符串不带 /0 结束标记，指定了拷贝长度 n，但 n 的大小超出了字符数组的大小。
使用 std::string 对 std::string 初始化时，如果提供的拷贝起始位置不在被拷贝的 string 之内，构造函数会抛出 out_of_range 异常。其自带的 len 参数作用范围只在 pos 到 s.size() 之间。

const char *cp = "Hello World!!!"; // null-terminated array
char noNull[] = {'H', 'i'};        // not null terminated
string s1(cp);  // copy up to the null in cp; s1 == "Hello World!!!"
string s2(noNull,2); // copy two characters from no_null; s2 == "Hi"
string s3(noNull);   // undefined: noNull not null terminated
string s4(cp + 6, 5);// copy 5 characters starting at cp[6]; s4 == "World"
string s5(s1, 6, 5); // copy 5 characters starting at s1[6]; s5 == "World"
string s6(s1, 6);    // copy from s1 [6] to end of s1; s6 == "World!!!"
string s7(s1,6,20);  // ok, copies only to end of s1; s7 == "World!!!"
string s8(s1, 16);   // throws an out_of_range exception

使用 sutstr() 构造子字符串

通过 sutstr() 成员可以以某个 string 的一部分构造一个新的 string：

//Return a string contains n characters from a staring at pos.
//pos default to 0
//n defaults to a value that cause the library to copy all the characters in a starting from pos.
s.substr(pos, n);

如果 pos 超出被拷贝 string 的范围，该成员同样会抛出 out_of_range 的异常。如果 n 超出了 string 的 size 范围，拷贝的内容同样只拷贝到 string 的结束位置。

string 的修改

string 类同时也支持一些额外的修改操作。某些操作还支持不同的重载版本：

<html>

</html>

几个比较重要的概念：

牵涉到插入和替换的操作，range 分为 [index + length] 和 [iter.begin, iter.end] 两种表现形式。
某些成员支持对 c-style string 进行操作。这些操作通过指向对应C 字符串的 cp 指针实现。
argument 形式中可能会出现两个字符串：被修改的 s 和用于 str：
- str 与 s 不能是同一个 string
- 如果是迭代器 (b,e) 形式的 args，b,e 不能指向 s

append() & replace()

string 额外拥有两个成员：append() 与 replace()。append() 将对应内容添加到目标 string 的末尾，而 replace() 类似于 insert + erase 的组合，用于将目标 string 中的某段内容替换为指定内容：

string s("C++ Primer"), s2 = s; 
s.insert(s.size(), " 4th Ed."); //s == "C++ Primer 4th Ed."
s2.append(" 4th Ed."); // s2 == "C++ Primer 4th Ed."

s.erase(11, 3); //s == "C++ Primer Ed."
s.insert(11, "5th"); // s == "C++ Primer 5th Ed."
s2.replace(11, 3, "5th"); // s2 == "C++ Primer 5th Ed."

用于修改 string 的多种重载形式

尽管 append、assign、insert 和 replace 的重载形式很多，但这些成员共享一个接口：

assgin & append 不需要指定 目标 string 需要被修改的 range，因为 assign 是对 string 做整体替换，而 append 总是将内容全加到 string 的末尾。
replace 与 insert 都通过两种 range 形式来指定替换区域和插入位置。 insert 的插入位置总是在 range 之前。
往目标 string 中添加字符的来源有多种：另一个 string, c-string（的指针），初始化列表，或者指定个数的同一个字符。来源是 string / c-string 的时候，会提供额外的控制参数。
不是所有的 args 都是通用的。

string 的搜索

String 类提供了六种函数用于搜索 string 或者字符。当这些函数找不到匹配结果的时候，会返回一个 static 的成员 string::npos。这个成员的类型是 const string::size_type, 初始值是 -1。因为 npos 是 unsigned 类型，所以 npos 等于任何 string 最大可能的大小。

<html>

</html>

所有上述函数返回的都是位置(index，std::string::size_type 类型)，或者是 npos，所有的搜索函数均区分大小写。

搜寻不是数字的字符

通过创建字符白名单，再利用 find_first_not_of 的特性可达到此效果：

string numbers("0123456789")；
string dept("03714p3");
// returns 5, which is the index to the character 'p'
auto pos = dept.find_first_not_of(numbers);

利用 find 返回的位置指定搜索点

find 系列函数会返回对应的 index. 一个应用是利用该 index 与 npos 配合使用实现循环查找：

string::size_type pos = 0;
//refresh and matching number at current position, if match then move to the next loop
while ((pos = name.find_first_of(number, pos) !=  string::npos) {
    cout <<  name[pos] << endl;
    ++pos; //move to the next character
}

这里利用了

pos = name.find_first_of(number, pos)

这个表达式来刷新当前的 index. 该 index 是基于之前的位置刷新的，即找到匹配的字符以后，就把该字符位置作为当前的起始点，接着向下查找。需要注意 ++pos，如果是按段落查找，可以考虑改变移动的大小到 args.size()；这样会更加效率。

从右向左查找

find 系列函数同时提供了从右向左查找的选项：

string river("Mississippi");
auto first_pos = river.find("is"); // returns 1
auto last_pos = river.rfind("is"); // returns 4

这里 rfind 找到的是右边第一个匹配的 is ，因此返回 4。同时，find_last 系列函数也能达到相似的效果：

find_last_of：寻找最后一个匹配的字符
find_last_not_of: 寻找最后一个不匹配字符

string 的比较

compare 函数和 C 语言的 strcmp 很像，用于比较 string 的大小：如果相等返回 0，如果前者大于后者返回正数，反之返回负数。

一些常用的参数组合：

<html>

</html>

String 的数字转换

String 的中往往会出现数字，但这些数字存储的方式是以 Latin-1 编码的字符来存储的，比如字符串 15，实际上是以两个字符的形式存储的，每个字符分别占 8 个字节的空间：

00110001 00110101 // string "15"

而对应的数值 15 则是以 int 的形式存储的：

00000000 00001111 //int 15

C++11中，string 类提供了对应的成员函数，使得这两者可以相互转换：

<html>

</html>

这些成员函数分为三类：

从数值转换为 string
string 转换为整型
string 转换为浮点型

string s2 = "pi = 3.14";
// convert the first substring in s that starts with a digit,  d = 3.14
d = stod(s2.substr(s2.find_first_of("+-.0123456789")));

上面的例子中，s2.find_first_of() 将返回第一个是数字的迭代器，并依据此创建出一个 string。而 stod() 将读取该 string，并转换为 double，并将在遇到 string 中下一个不是 Number 的位置停止。

可以转换成数字的 string 需要满足以下要求：

string 首个 non-whitespece 的字符必须是正负符号（+ 或 -），或者是数字。
如果 b 设置为了 16 进制，可以以 0x 开头。
如果是浮点数，可以以 . (decimal point, 小数点）开头，同时也支持 e 或 E （科学计数法中的指数）

如果 string 不能转换为一个数值，则会抛出 invalid_argument 异常。如果转换得到的数值不能用任何类型表示，则抛出 out_of_range 异常。

容器适配器

适配器（Adaptor） 是 C++ STL 中的一个概念。适配器是一种机制，它基于某种容器、迭代器或者函数类型，然后像另外一种类型一样使用这些类型。

容器适配器（Container Adapter）则是基于某种容器，然后使该容器可以像另外一种类型的容器一样使用。一些适配器通用的类型与操作如下：

<html>

</html>

容器适配器的定义

容器适配器拥有两个构造函数：

默认构造函数，创造空的对象
初始化是适配器的构造函数，接收一个容器，将其以复制的形式初始化适配器：

比如定义一个基于 deque<int> 的 stack：

stack<int> stk(deq); //copy init from deq

不仅如此，在定义适配器的时候可以指定其使用的容器：

// empty stack implemented on top of vector
stack<string, vector<string>> str_stk;
// str_stk2 is implemented on top of vector and initially holds a copy of svec
stack<string, vector<string>> str_stk2(svec);

当然，每种适配器必须选择合适的容器来进行初始化。一些限制：

适配器要求可以添删 & 尾部元素修改，因此不能使用 array 和 forward_list。
stack 要求 push_back, pop_back, 和 back 操作，所以可以用除前两种以外的所有容器。
queue 要求 back, push_back / push_front, front, 所以可以用 list, deque, 但是不能使用 vector。
priority_queue 相比 queue 不需要 push_front，但需要 random access，所以不能使用 list。

stack 适配器

stack 适配器定义在 <stack> header 中, 包含如下几种额外的操作：

<html>

</html>

一个实例：

stack<int> intStack; //empty stack
//fill up the stack
for (size_t ix = 0; ix != 10; ++ix) {
    intStack.push(ix); //insStack holds [0...9]
}
whlie(!intStack.empty()) {
    int value = intStack.top(); //show the top elmenet
    intStack.pop(); //remove the top element
}

注意这里，即便 stack 是基于 deque 实现的，我们也不能使用 push_back() 来操作 stack。

适配器应该使用适配器定义的操作，不能使用底层容器的操作来操作适配器。

queue 适配器

标准库中：

queue 是一种访问策略为先进先出（FIFO）的类型；这意味着进入 queue 的元素都会在队尾添加，而离开 queue 的元素都会从队首删除。默认使用 deque 实现，但也可以用 list & vector。
priority_queue 按照优先级来排序。先加入的元素会排在所有比它优先级低的元素之前（使用 < 运算符进行排位）。比如饭店按预约的时间来分配座位，而不是按先来后到分配。默认使用 vector 实现，但也可以用 deque。

What & How & Why

[ About ]

[ My Links ]

[ Notice ]

页面工具

站点工具

用户工具

目录

顺序容器

顺序容器概述

顺序容器的特性

顺序容器的选择

标准库容器概况

容器对保存类型的限制

迭代器

迭代器的范围

一些使用上述概念的假定

使用容器类型成员

容器成员 begin & end

初始化 / 定义容器

容器的拷贝初始化

容器的列表初始化

指定大小的初始化

标准库 array 类型

赋值与 swap

使用 assign operator 赋值

使用 assign 函数赋值

使用 swap 函数赋值

容器大小操作

关系运算符

顺序容器的操作

容器相关操作总览

向容器首尾添加元素

使用 push_back()

使用 push_front()

插入元素

对指定位置使用 insert()

使用 insert() 插入范围内的元素

利用 insert() 范围版本的返回值

使用 emplace 进行操作

访问元素

访问元素的成员返回引用

下标访问与安全的随机访问

删除元素

pop_front() / pop_back()

删除容器中指定的元素

删除容器中多个元素

forward_list 的特殊操作

改变容器大小

容器与迭代器的失效

循环中迭代器的维护

Vector是如何增长的

管理容量的成员函数

capacity 和 size

额外的 String 操作

string 的创建

使用字符串进行初始化时的注意事项

使用 sutstr() 构造子字符串

string 的修改

append() & replace()

用于修改 string 的多种重载形式

string 的搜索

搜寻不是数字的字符

利用 find 返回的位置指定搜索点

从右向左查找

string 的比较

String 的数字转换

容器适配器

容器适配器的定义

stack 适配器

queue 适配器