第9章 顺序容器
顺序容器为程序员提供了控制元素存储和访问顺序的能力。这种顺序不依赖于元素的值，而是与元素加入容器时的未知相对应。
9.1 顺序容器概述
一个容器就是一些特定类型对象的集合
forward_list和array是新C++标准增加的类型
与内置数组类似，array对象的大小是固定的，array不支持添加和删除元素以及改变容器大小的操作
forward_list没有size操作
9.2 容器库概述
特定类型数据注意初始值
//假定noDefault是一个没有默认构造函数的类型 vector<noDefault> v1(10, init); //正确：提供了元素初始化器 vector<noDefault> v2(10); //错误：必须提供一个元素初始化器
迭代器
迭代器范围：[begin, end），称为左闭合区间
end是尾元素后一个位置
可以通过迭代器给元素赋值
while(begin != end){ *begin = val; ++begin; }
9.2.2 容器类型成员
对一个反向迭代器执行++操作，会得到上一个元素。
size_type：索引的类型
list<string>::iterator iter; list<string>::const_iterator iter1; vector<int>::difference_type count;
9.2.3 begin和end成员
以c开头的版本是C++新标准引入的
vector<int> v1; const vector<int> v2; vector<int>::iterator it1 = v1.begin(); vector<int>::const_iterator it2 = v2.begin(); vector<int>::const_iterator it3 = v1.cbegin(); vector<int>::const_iterator it4 = v2.cbegin();
9.2.4 容器定义和初始化
拷贝初始化必须类型匹配：
也可以列表初始化，C++11新特性
顺序容器的构造函数能接受大小参数，关联容器并不支持
定义array时，除了需要指定元素类型，还需要指定容器大小：
array<int, 42> array<string, 10>
使用：
array<int, 10>::size_type i; array<int>::size_type j; //错误，没有指定大小
可知array是一个大小固定的容器
初始化问题：
array<int, 10> ia1; //10个默认初始化的int array<int, 10> ia2 = {0,1,2,3,4,5,6,7,8,9}; //列表初始化 array<int, 10> ia3 = {42}; //ia3[0]为42，其他为0
array和内置数组的区别：
int digs[10] = {0,1,2,3,4,5,6,7,8,9}; int cpy[10] = digs; //错误：内置数组不支持拷贝或赋值 array<int, 10> digits = {0,1,2,3,4,5,6,7,8,9}; array<int, 10> copy = digits; //正确：只要数组类型匹配即合法
该节习题：
9.11
vector<int> vec; // 0 vector<int> vec(10); //10个0 vector<int> vec(10, 1); //10个1 vector<int> vec = {1,2,3,4,5}; // 1,2,3,4,5 vector<int> vec(other_vec); // same as other_vec vector<int> vec(other_vec.begin(), other_vec.end()); // same as other_vec
9.13
list<int> l1= {1,2,3}; vector<double> v1(l1.begin(), l1.end());
9.2.5 赋值和swap
assign成员仅在顺序容器中有
list<string> names; vector<const char*> oldstyle; names = oldstyle; //错误 names.assign(oldstyle.cbegin(), oldstyle.cend()); //正确 list<string> slist(1); //一个元素 slist1.assign(10, "Hiya!"); //10个元素
swap有成员版本和非成员版本，使用非成员版本是一个好习惯
9.3 顺序容器操作
9.3.1 向顺序容器添加元素
C++11新标准：emplace_front、emplace和emplace_back
这些操作构造而不是拷贝元素
9.2.7 关系运算符
emplace函数的参数根据元素类型而变化，参数必须与元素类型的构造函数相匹配
9.3.2 访问元素
注意：
- 迭代器end指向的是容器尾元素之后的（不存在的）元素。为了获取尾元素，必须首先递减此迭代器。
- 在调用front和back（或者解引用begin和end）之前，要确保容器非空。
注意索引越界问题：
vector<string> strv; cout << strv[0]; //错误 cout << strv.at(0); //错误
9.3.1 删除元素
erase是删除指定迭代器的元素
9.3.4 特殊的forward_list操作
注意：多了一个before_begin迭代器
实例：删除单项列表中的奇数元素
forward_list<int> flst = {0,1,2,3,4,5,6,7,8,9}; auto prev = flst.before_begin(); //虚拟的“首前元素” auto curr = flst.begin(); while(curr != flst.end()){ if(*curr % 2){ //若为奇数，删除 curr = flst.erase_after(prev); } else{ //跳过偶函数 prev = curr; ++curr; } }
9.3.5 改变容器大小
练习9.29：vec包含25个元素，vec.resize(100)会追加75个0；vec.resize(10)之后只剩下10个元素
练习9.30：resize之后如果大于原来的size，则追加0；如果小于原来的size，则删除元素直到容器size为resize的size
9.4 vector对象是如何增长的
管理容量的成员函数：
shrink_to_fit是新特性；调用它可以要求容器将超出当前大小的多余内存退回给系统；调用它只是一个请求，标准库并不保证退还内存。
容器的size是指它已经保存的元素的数目；而capacity则是在不分配新的内存空间的前提下它最多可以保存多少元素。
9.5 额外的string操作
9.5.1 构造string的其他方法
初始化实例如下：
substr操作：
实例：
9.5.2 改变string的其他方法
string类型支持顺序容器的赋值运算符以及assign、insert和erase操作。除此之外，它还定义了额外的insert和erase版本。
s.insert(s.size(), 5, '!'); //末尾插入5个感叹号 s.erase(s.size()-5, 5); //删除最后5个字符
const char *cp = "Stately, plump Buck"; s.assign(cp, 7); //"Stately" s.insert(s.size(), cp+7); //"Stately, plump Buck"
string s = "some string", s2 = "Some other string"; s.insert(0, s2); //在s中位置0之前插入s2的拷贝 s.insert(0, s2, 0, s2.size()); //在s[0]之前插入s2[0]开始的s2.size()个字符
append和replace函数
string类型的额外成员函数
append操作是在string末尾进行插入操作的一种简写形式：
string s("C++ Primer"), s2 = s; s.insert(s.size(), " 4th Ed"); //s == "C++ Primer 4th Ed" s2.append(" 4th Ed"); //与上面等价
replace操作是调用erase和insert的一种简写形式：
s.erase(11, 3); //s == "C++ Primer Ed" s.insert(11, "5th"); //s=="C++ Primer 5th Ed" //从位置11开始，删除3个，并插入"5th" s2.replace(11, 3, "5th"); //与上面等价 //也可以插入更长的 s.replace(11, 3, "Fifth"); //s=="C++ Primer Fifth Ed"
9.5.3 string搜索操作
string name("AnnBelle"); auto pos1 = name.find("Anna"); //pos1==0
区分大小写：
string name("annbelle"); auto pos2 = name.find("Anna"); //pos1==npos
查找与给定字符串中任何一个字符匹配的位置。
string numbers("0123456789"), name("r2d2"); auto pos = name.find_first_of(numbers); //pos==1 string dept("03714d3"); auto pos2 = dept.find_first_not_of(numbers); //pos2==5 "d"的索引
string::size_type pos = 0; while ((pos=name.find_first_of(numbers, pos)) != string::npos){ cout << "found number at index: " << pos << "element is " << name[pos] <<endl; ++pos; //移动到下一个字符 }
逆向搜索
string river("Mississippi"); auto first_pos = river.find("is"); // first_pos==1 auto last_pos = river.rfind("is"); //last_pos==4
9.5.4 compare函数
详细介绍查看：https://blog.csdn.net/qq_39236499/article/details/120637202
9.5.5 数值转换
int i = 42; string s = to_string(i); //int->string double d = stod(s); //string->double
string s2 = "pi = 3.14"; //转换s中以数字开始的第一个子串，结果d=3.14 d = stod(s2.substr(s2.find_first_of("+-.0123456789")));
9.6 容器适配器
除了顺序容器外，标准库还定义了三个顺序容器适配器：stack、queue、priority_queue
本质上，一个适配器是一种机制，能使某种事物的行为看起来像另外一种事物一样。
每个适配器都定义两个构造函数：
- 默认构造函数创建一个空对象
- 接受一个容器的构造函数拷贝该容器来初始化适配器
栈适配器
每个容器适配器都基于底层容器类型的操作定义了自己的特殊操作，我们只可以使用适配器操作，而不能使用底层容器类型的操作。
队列适配器
queue和priority_queue适配器定义在queue头文件中
