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;

容器提供了两个成员函数 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 相同数量的元素，每个元素的值都是初始值：

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 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 的特性带来了什么影响？

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

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

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

所有容器类型都支持 == 和 != 两种相等性运算符。除了无序关联容器（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);

对容器指定位置添加元素可以使用 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() 有两个重载版本提供了插入范围内元素的功能：

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

container.insert(p, element_quantity, value);

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

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

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

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；

// 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
}

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

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)

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

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

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

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

一些常用的参数组合：

<html>

</html>

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

00110001 00110101 // string "15"

00000000 00001111 //int 15

</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")));

• 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
}

标准库中：

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

相关的操作：

<html>

</html>