What & How & Why

顺序容器

C++ Primer 笔记 第九章


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

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

顺序容器概述

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

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

顺序容器的特性

根据不同存储的策略,不同的容器的特性也不同:

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



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

顺序容器的选择

通常,选择顺序容器遵循以下的策略:

  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 中。

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

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

标准库容器概况

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

容器提供了两个成员函数 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 可以进行直接拷贝和赋值,只要 sizetype 都匹配即可:

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

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



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



哪些容器有例外?

  1. 在使用 swap 交换 string 的时候可能会使 迭代器、引用或者指针无效。
  2. 在使用 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.
    • 否则,AB 的大小取决于他们第一个不相等元素的比较结果

顺序容器的操作

容器相关操作总览

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



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

向容器首尾添加元素

使用 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 在对 vectorstringdeque 中部进行元素插入时,效率很低,需要谨慎使用。

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



使用 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):

这些成员不会检测其 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 指向的元素;该成员返回一个迭代器,指向被删除元素所在位置的下一个元素:



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



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



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



基于上面的原因, forward_list 没有通用的 insertemplace 或者 erase 成员。取而代之的是其自身的配套成员:



可以看出来的是,如果需要添加 / 删除某一个元素,我们必须先获取其前置节点的位置。因此,上面所有的成员函数,操作的都是迭代器 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 操作也将导致被删除元素对应的迭代器、引用和指针失效。对 vectorstringdequeresize 可能会导致所有迭代器、引用或指针失效。

容器与迭代器的失效

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

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


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




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

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

循环中迭代器的维护

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

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



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

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



也就是:
p = insert(p, N);
p += 2;
添删操作中,避免使用缓存过的 end() 迭代器

该点在对 vectorstringdeque 进行添删操作的时候尤其要注意,因为对以上所有容器的添删操作都会导致 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++ 为 vectorstring 提供了一些函数来供他们申请空间:

/* 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 的增长策略是怎样的?

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



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

额外的 String 操作

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

string 的创建

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



使用字符串进行初始化时的注意事项
  • 使用 const char*std::string 进行初始化时,初始化的内容会复制到 /0 标记为止。有两种情况会导致该操作 Undefined:
    • const char* 字符串不带 /0 结束标记,且没有指定拷贝的长度 n
    • const char* 字符串不带 /0 结束标记,指定了拷贝长度 n,但 n 的大小超出了字符数组的大小
  • 使用 std::stringstd::string 初始化时,如果提供的拷贝起始位置不在被拷贝的 string 之内,构造函数会抛出 out_of_range 异常。 其自带的 len 参数作用范围只在 poss.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 类同时也支持一些额外的修改操作。某些操作还支持不同的重载版本:



几个比较重要的概念:

  • 牵涉到插入和替换的操作,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 的多种重载形式

尽管 appendassigninsertreplace 的重载形式很多,但这些成员共享一个接口:

  • 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。因为 nposunsigned 类型,所以 npos 等于任何 string 最大可能的大小。



所有上述函数返回的都是位置(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,如果前者大于后者返回正数反之返回负数

一些常用的参数组合:



String 的数字转换

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

00110001 00110101 // string "15"
而对应的数值 15 则是以 int 的形式存储的:
00000000 00001111 //int 15
C++11中,string 类提供了对应的成员函数,使得这两者可以相互转换:



这些成员函数分为三类:

  • 从数值转换为 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, 小数点) 开头,同时也支持 eE (科学计数法中的指数)

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

容器适配器

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

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



容器适配器的定义

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

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

比如定义一个基于 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);

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

  • 适配器要求可以添删 & 尾部元素修改,因此不能使用 arrayforward_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 中, 包含如下几种额外的操作:



一个实例:
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

相关的操作: