顺序容器

C++ Primer 笔记 第九章

---

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

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

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

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

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

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

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

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

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

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

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

操作的详细分类如下表：



总的来说，容器都是类模板（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 ，用于建立迭代的范围。同时提供的还有他们的 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，或者拥有默认构造函数。

和 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

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

赋值操作符 =：该操作会直接将右边的容器的整个范围和元素赋值给左边，是替换（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

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

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

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 对容器内的内容进行了交换。内部的迭代器、引用和指针等等均指向原来的元素：



哪些容器有例外？

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

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

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 期间的容器元素操作机制。当然，根据容器的实现方式不同，不同的操作在不同的容器上的效率也不同：

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

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

• 使用限制：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 操作适合除了 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() 有两个重载版本提供了插入范围内元素的功能：

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

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());

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() 的效果。

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++ 提供了四种访问顺序容器元素的操作：



使用 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）：

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 一个单向的链表数据结构，每一个节点都承担着指向后方节点的任务：

<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 与容器大小不等时：

1. 如果 n < c.size()，那么容器尾部的元素被删除。
2. 如果 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 内容复制过去，再添加新的元素。这整个过程被称为 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() 并不一定起作用，返还内存的请求很可能会被忽略。

Capacity 与 Size 的区别是什么？

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

Capacity 的增长策略是怎样的？

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

<html>

</html>

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

除了一些容器通用的函数以外，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() 成员可以以某个 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 类同时也支持一些额外的修改操作。某些操作还支持不同的重载版本：

<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

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."

尽管 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 或者 字符。当这些函数找不到匹配结果的时候，会返回一个 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 系列函数会返回对应的 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: 寻找最后一个不匹配字符

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

一些常用的参数组合：

<html>

</html>

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

相关的操作：

<html>

</html>