本篇隶属C++ Primer中C++标准库专题，当前集中于顺序容器。

容器是：一些特定类型对象的集合。顺序容器提供控制元素存储和访问顺序的能力。

顺序容器概述

标准库中有以下顺序容器：

顺序容器类型 数据结构 访问模式 插入/删除元素
vector 可变大小数组 随机访问 尾部插入/删除
Deque 双端队列 随机访问 头/尾插入/删除
List 双向链表 双向顺序访问 任何位置插入/删除
forward_list 单向链表 单向顺序访问 任何位置插入/删除
Array 固定大小数组 随机访问 不能插入/删除
String 可变大小 随机访问 尾部插入/删除

String, vector：将元素保存在连续内存空间：随机访问快；插入/删除慢（需要移动之后的所有元素）

List, forward_list：插入/删除快；不支持随机访问（访问一个元素，需要遍历整个容器），开销大

Deque:随机访问快；在两端插入/删除快，在中间插入/删除慢

array：不支持插入/删除元素和改变容器大小（相较于内置数组）

容器使用准则

  • 随机访问元素：vector, deque
  • 在容器中间插入/删除元素：list, forward_list
  • 头尾插入/删除元素：deque

容器库概览

迭代器

begin, end成员

Begin，end：生成指向容器第一个元素，尾元素之后位置的迭代器，从而形成一个包含容器中所有元素的迭代器范围。

1
2
3
4
5
list<string>a={"Anne","Jane"};
auto it1=a.begin();		// list<string>::iterator
auto it2=a.rbegin();		// list<string>::reverse_iterator
auto it3=a.cbegin();		// list<string>::const_iterator
auto it4=a.crbegin();		// list<string>::const_reverse_iterator

当不需要写访问时，应使用cbegin, cend.

容器定义和初始化

每个容器类型都定义了一个默认构造函数：除array外，每个容器的默认构造函数都创建一个指定类型的空容器，接受指定大小和元素初始值的参数。

一个容器初始化为：另一个容器的拷贝

  • 一个容器初始化为另一个容器的拷贝时：两个容器的容器类型、元素类型必须相同；
  • 当传递迭代器参数来拷贝范围时，不要求容器类型、元素类型相同。
1
2
3
4
5
6
list<string>a={"Anne","Jane"};

list<string>list2(a);	// 正确：类型匹配
deque<string> aList(a);	// 错误：容器类型不匹配

forward_list<string> a2(a.begin(),a.end());	// 正确：传入迭代器参数时，可以类型不匹配，只要能转化即可

列表初始化

1
list<string>a={"Anne","Jane"};

与顺序容器大小相关的构造函数

构造函数接受：一个容器大小初始值，一个（可选的）元素初始值

1
2
vector<int> ivec(10,-1);
forward_list<int> ivec(10);		// 10个元素，每个初始化为0

  • 如果元素类型是内置类型/具有默认构造函数的类类型：可以只提供大小参数；

  • 如果没有元素类型没有默认构造函数：必须指定一个显式的元素初始值。

只有顺序容器的构造函数才接受大小参数；关联容器不支持。

array有固定大小

  • array可执行数组拷贝
1
2
3
4
int digs[10]={0,1,2};
int cpy[10]=digs;		// 错误：内置数组不支持拷贝/赋值
array<int, 10>digits={0,1,2,3,4,5,6,7,8,9};
array<int, 10>copy=digits;	// 正确：只要数组类型匹配，即合法

赋值和swap

使用assign（仅顺序容器）

assign运算符：要求左边、右边的运算对象具备相同的类型；将右边运算对象中的所有元素，拷贝到左边运算对象中。

1
2
3
4
5
6
7
list<string> names;
vector<const char*> oldstyle;
names=oldstyle;		// 错误：容器类型不匹配
names.assign(oldstyle.cbegin(), oldstyle.cend()); // 正确：将names中元素替换为迭代器指定范围中，元素的拷贝

list<string>slist1(1);	// 1个元素，为空string
slist1.assign(10, "Hiya!");	// 10个元素，每个都是"Hiya!"

使用swap

swap交换两个相同类型容器的内容

除array外：swap不执行对任何元素的拷贝、删除和插入操作，元素本身未交换，只交换两个容器内部的数据结构，因此：swap在常数时间内完成；

  • 元素不会移动：除string外，指向容器的迭代器、引用和指针都不会失效。

array：swap会真正交换元素，所需时间与array中元素数目成正比。

1
2
3
vector<string> svec1(10);	
vector<string> svec2(24);	
swap(svec1, svec2);

容器大小操作

  • size：容器中元素数目

  • empty：size为0时返回true；否则返回false

  • max_size：返回大于或等于该类型容器，所能容纳的最大元素值

关系运算符

关系运算符左右两侧：相同类型的容器和元素

逐元素比较：取决于第一个不相等元素的比较结果；若一个容器是另一个容器的前缀子序列，则较小容器小于较大容器。

使用容器关系运算符时，元素必须完成关系运算符的定义：

1
2
vector<Sales_data> storeA, storeB;
if(storeA<storeB)		// 错误：Sales_data没有<运算符

顺序容器操作

添加元素

push_back

除array和forward_list外，每个顺序容器（包括string）支持push_back.

使用对象初始化容器/将对象插入到容器，放入的是对象值的一个拷贝，而非对象本身。

push_front

list, forward_list, deque支持push_front。将元素插入到容器头部：

insert

Vector, deque, list, string 支持insert（forward_list提供特殊版的insert）

  • insert接受一个迭代器作为第一个参数：插入到该迭代器所指位置的前面（迭代器可以指向容器尾部不存在的位置）

    1
    2
    vector<string>svec;
    svec.insert(svec.begin(),"hello!");	// vector不支持push_front操作，使用insert代替

  • insert接受一个元素数目、一个值：将指定数量的元素，添加到指定位置之前

    1
    svec.insert(svec.end(),10,"Lisa");

  • insert接受一对迭代器/一个初始化列表：将给定范围的元素，添加到指定位置之前

    1
    2
    3
    vector<string> c={"Anne","Jane","Mike"};
    slist.insert(s.end(),c.end()-2,c.end());
    slist.insert(s.end(),{"Jack"});

    传递的迭代器不能指向添加元素的目标容器：

    1
    slist.insert(slist.begin(),slist.begin(),slist.end());	//运行时错误
insert返回值

insert返回的迭代器，指向插入的新元素：

1
2
3
list<string> lst;
auto iter=lst.begin();
while(cin>>word) iter=lst.insert(iter, word);	// 每次循环将一个新元素插入到list首元素之前的位置

emplace

三个操作：emplace_front, emplace, emplace_back，分别将元素放在容器头部、一个指定位置之前、容器尾部。

  • emplace函数在容器中直接构造元素；参数必须与元素类型的构造函数匹配。

    1
    2
    3
    c.emplace_back("978-0590", 25, 6=5.99);
    // 等价于：
    c.push_back(Sales_data("978-0590", 25, 6=5.99));

  • push或insert会创建一个局部临时对象，再压入容器。

访问元素：front和end

  • front：每个顺序容器都有，返回首元素的引用
  • end：除forward_list之外，每个顺序容器都有，返回尾元素的引用
1
2
3
4
5
if(!c.empty()){
  auto val=*c.begin(), val2=c.front();	// val, val2是第一个元素值的拷贝
  auto last=c.end();
  auto val3=*(--last), val4=c.back();
}

访问成员函数返回的是引用

容器中访问元素的成员函数（front, back, 下标, at）返回的都是引用。

若要改变元素的值，需要将变量定义为引用类型。

1
2
3
4
5
6
7
if(!c.empty()){
  c.front()=42;
  auto &v=c.back();	// 获取引用
  v=1024;		// 才能改变值
  auto v2=c.back();	// 获取拷贝
  v2=0;			// 未改变c中的元素
}

删除元素

pop_front, pop_back

vector, string不支持push_front和pop_front；forward_list不支持pop_back.

erase

删除一个/多个元素

特殊的forward_list操作

forward_list是单向链表，删除元素时需关注两个迭代器：一个指向待处理的元素，另一个指向其前驱。

改变容器大小

使迭代器失效的容器操作

添加元素：

  • Vector, string：
    • 存储空间重新分配：指向容器的迭代器、指针、引用都失效；
    • 存储空间未重新分配：插入位置之前的有效，插入位置之后的失效。
  • deque：
    • 插入首尾位置之外的任何位置：都失效；
    • 插入首尾位置：迭代器失效，指针、引用有效。
  • list, forward_list：迭代器、指针、引用都有效。

删除元素：

  • Vector, string：被删元素之前的迭代器、指针、引用都有效；
    • 尾后迭代器一定失效。
  • deque：
    • 删除首尾位置之外的任何位置：都失效；
    • 删除尾元素：尾后迭代器失效，其他不受影响；
    • 删除首元素：都不受影响。
  • list, forward_list：迭代器、指针、引用都有效（包括首前迭代器、尾后迭代器）

使用失效的迭代器、指针、引用，是严重的运行时错误。

不要缓存end返回的迭代器

1
2
3
4
5
6
auto begin=v.begin(),end=v.end();
while(begin!=end){
  ++begin;
  begin=v.insert(begin, 4);
  ++begin;
}

将end返回的迭代器，保存在一个名为end的局部变量中。在添加元素时，保存在end中的迭代器将失效，不再指向任何位置，导致未定义的行为。应该修改为：

1
2
3
while(begin!=v.end()){
  // 每次插入操作后，重新计算end
}

vector容器实现与扩充

vector中元素存储在连续内存空间，容器大小可变。其分配策略为：通常分配比心的空间需求大的内存空间，作为备用。

三个迭代器

  • first：指向vector对象的起始字节位置
  • last：指向当前最后一个元素的末尾字节
  • end：指向整个vector容器所用内存空间的末尾字节

扩容过程

如果集合已满，在新增数据的时候，就要分配⼀块更⼤的内存，将原来的数据复制过来，释放之前的内存，在插⼊新增的元素 。

所以对vector的任何操作，⼀旦引起空间的新配置，指向原vector的所有迭代器就都失效了。

管理容器的成员函数

capacity 和 size

  • size：已经保存的元素数量
  • capacity：不重新分配内存空间的前提下，最多可以保存的元素数量

恒有capacity>size；capacity--size时，vector扩容，capacity变大（翻倍）

扩容机制

固定扩容

每次扩容的时候在原 capacity 的基础上加上固定的容ᰁ，⽐如初始 capacity 为100，扩容⼀次为 capacity + 20，再扩容仍然为 capacity + 20;

  • 缺点：考虑⼀种极端的情况，vector每次添加的元素数量刚好等于每次扩容固定增加的容量+1，就会造成⼀种情况：每添加⼀次元素就需要扩容⼀次，⽽扩容的时间花费⼗分⾼昂。所以固定扩容可能会⾯临多次扩容的情况，时间复杂度较⾼;
  • 优点：固定扩容方式，空间利用率高。
加倍扩容

每次扩容的时候原 capacity 翻倍，⽐如初始capcity = 100, 扩容⼀次变为 200, 再扩容变为 400;

  • 缺点：因为每次扩容空间翻倍，⽽很多空间没有利⽤上，空间利⽤率不如固定扩容。
  • 优点：
  • ⼀次扩容 capacity 翻倍的⽅式使得正常情况下添加元素需要扩容的次数⼤⼤减少（预留空间较多），时间复杂度较低。

resize和reserve

resize：只改变容器中元素数目，不改变容器的容量。

  • 当resize(len)中len>v.capacity()，数组中的size和capacity均设置为len；
  • 当resize(len)中len<=v.capacity()，则数组中的size设置为len，⽽capacity不变;

reserve：不改变容器中元素数量，只影响vector预先分配的内存空间大小。

  • 如果reserve(len)的值 > 当前的capacity()，那么会᯿新分配⼀块能存len个对象的空间，然后把之前的对象通过copy construtor复制过来，销毁之前的内存;
  • 当reserve(len)中len<=当前的capacity()，则数组中的capacity不变，size不变，即不对容器做任何改变。

额外的string操作

string构造函数

如果pos大于size，抛出out_of_range异常。

substr操作

Append, replace函数

1
2
3
4
s.insert(s.size(),"hello");
s.append("hello");		// 等价

s2.replace(11,3,"fifth");		// 删除了3个字符，在其位置插入了5个新字符

string搜索

compare函数

数值转换

1
2
3
4
5
6
7
int i=42;
string s=to_string(i);
double d=stod(s);

string s2="pi=3.14";
// 转换s中以数字开始的第一个子串，结果d=3.14
d=stod(s2.substr(s2.find_first_of("+-.0123456789")));

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

容器适配器

三个顺序容器适配器：stack, queue, priority_queue

默认情况下：stack, queue基于deque实现；priority_queue基于vector实现。

定义一个适配器

默认构造函数：创建一个空对象，接受一个容器的构造函数，拷贝该容器来初始化适配器。

1
stack<int> stk(deq);	// 从deq拷贝元素到stk

栈适配器

stack要求：push_back,pop_back,back

  • 可以使用除array, forward_list的任何容器类型，来构造适配器

队列适配器

queue要求：back, push_back, front, push_front

  • 可以使用list, deque,不能使用vector（不支持front相关操作）

priority_queue要求：front, push_back, pop_back，随机访问能力

  • 可以使用vector,deque,不能使用list