9.1 顺序容器概述
容器是容纳特定类型对象的集合,每种容器都是性能和功能的权衡
C++ 容器分为顺序容器,关联容器
顺序容器的元素排列由元素添加到容器的次序决定
若不确定使用哪种容器,可在程序中只使用 vector 和 list 的共同操作:使用迭代器,不使用下标,避免随机访问,这样在必要时替换很方便
9.2 容器库概览
容器类型上的操作形成了一种层次:
某些操作是所有容器类型都支持的,另外一些操作仅针对顺序容器,关联容器或无序容器,还有一些仅适用于小部分容器
容器均定义为模板类,容器也可以装容器
//假定 noDefualt 是一个无默认构造函数的类型 vector<noDefualt> v1(10,init);//正确,提供了元素初始化器 vector<noDefualt> v1(10);//错误,无元素初始化器 //这个例子更好理解 class A{ public: A(string b) {a=b;} private: string a; } int main(){ string AA("HI"); vector<A> v1(100,AA);//这里隐式的调用了A的构造 //如果构造是explicit,那么可以显式的调用 vector<A> v1(100,A(AA)); }
迭代器
iterator 所有容器都支持
1、访问元素(使用解引用实现)
2、递增运算符(从当前元素移动到下一个元素)
迭代器的范围由一对迭代器表示:( [ begin , end ) 左闭右开区间 )
while(begin != end){ //相等时,begin 即为尾后迭代器,容器为空 *begin = val; //修改容器的值 ++begin; //移动迭代器到下一个元素 }
每个容器都定义的很多类型,为了使用这些类型,必须显式使用其类型
list<string>::iterator iter vector<int>::difference_type cout;//表示两个迭代器之间的距离,此处为INT
begin 和 end 有多个版本:带 r 的返回反向迭代器,以 c 开头的返回 const 迭代器
list<string>::iterator iter = {“A”,“B”,"C"}; auto it1 = iter.begin(); //list<string>::iterator auto it2 = iter.rbegin(); //list<string>::reverse_iterator auto it3 = iter.cbegin(); //list<string>::cosnt_iterator auto it4 = iter.crbegin(); //list<string>::cosnt_reverse_iterator it1 = it3;//错误,理同常量指针可以赋值给指针常量,但不能反过来 it3 = it1;//正确
容器实际上有两个 begin 成员函数,返回 const_iterator 类型,另一个返回 iterator
//并不是只有调用 cbegin() 才会返回 const_iterator iterator begin(){...} const_iterator begin() const{...} const list<string>::iterator iter = {“A”,“B”,"C"}; list<string>::iterator c1 = iter.begin();//错误,和上同理 list<string>::const_iterator c2 = iter.begin();//正确
容器定义和初始化
容器拷贝另一个容器
对于array类型,初始化隐含了容器大小(等同于数组)
std::list<std::string> letter = { "A", "B", "C" }; std::vector<const char*> letter1 = { "A", "B", "C" }; //一个容器为另一个容器拷贝时,两个容器及元素类型必须一致 std::list<std::string> letter2(letter); //正确:类型匹配 //std::deque<std::string> letter3(letter); 错误:容器类型不匹配 //两个迭代器表示一个范围,拷贝元素,直到(但不包括)it指向元素 //将 const char* 转换为 std::string std::forward_list<std::string> letter3(letter1.begin(), letter1.end()); std::list<std::string>::iterator it = letter.end(); std::deque<std::string> letter4(letter.begin(), it);
与顺序容器大小相关的构造函数
//除array外提供了一个构造 std::vector<int> v1(10, -1); //10个int元素,每个都是-1 std::list<std::string> l1(10, "HI"); //10个string,每个都是HI std::forward_list<int> l2(10); //10个int元素,每个都是0 std::deque<std::string> d1(10); //10个string,每个都是空string
标准库 array 具有固定大小
标准库array的大小是类型的一部分
std::array<int, 5> a1; //5个默认初始化的int std::array<int, 5> a2 = {0,1,2,3,4}; std::array<int, 5> a3 = { 42 }; //剩余元素为0 //内置数组类型不能进行拷贝,或对象赋值操作,但array无此限制 int digs[5] = { 0, 1, 2, 3, 4 }; int cpy[5] = digs;//错误,内置数组类型不支持拷贝和赋值 std::array<int, 5> a4 = a2;
容器赋值运算
赋值运算会导致左边容器的迭代器,引用和指针失效
swap 操作将容器内容交换不会导致容器的迭代器,引用和指针失效(类型为 array 和string 的情况除外,原因如下)
std::array<int, 5> c1; //5个默认初始化的int std::array<int, 5> c2 = { 0, 1, 2, 3, 4 }; //赋值运算后,两者的大小都与后边容器原大小相同 c1 = c2; //将 c1 内容替换为 c2 拷贝(如果是array类型其容器大小需一致) c1 = { 0, 1, 2 }; //赋值后, c1大小为3(array类型不支持)
由于右边运算对象的大小可能与左边不同,所以 array 不支持 assign,也不支持花括值列表进行赋值
assign 允许从一个不同但相容的类型赋值,或是从容器的一个子序列赋值
std::list<std::string> names ; std::vector<const char*> oldstyle ; names = oldstyle; //错误,容器类型不匹配 names.assign(oldstyle.cbegin(), oldstyle.cend()); //正确 将 const char* 转换为 std::string std::list<std::string> ls1(1); ls1.assign(10, "HI"); // 等价于 ls1.clear() , 后跟 ls1.insert(ls1.begin(),10,"HI");
swap 操作交换两个相同类型容器内容
std::vector<std::string> svec1(10); std::vector<std::string> svec2(24); std::swap(svec1, svec2); //调用完成后 svec1 包含24个 string 元素
容器大小操作
std::vector<int> vec1 = { 1, 3, 5, 7, 9, 12 }; std::vector<int> vec2 = { 1, 3, 9 }; std::vector<int> vec3 = { 1, 3, 5, 7 }; std::vector<int> vec4 = { 1, 3, 5, 7, 9, 12 }; //关系运算符两边类型必须一致 vec1 < vec2; //true vec1 < vec3; //false vec1 == vec4; //true vec1 == vec2; //false //只有当元素类型也定义了相应的比较运算符时 //才可以使用关系运算符来比较两个容器 std::vector<Sales_data> storeA,storeB; if(storeA < storeB) //错误:Sales_data没有 < 运算符
9.3 顺序容器操作
array 不支持以下添加元素操作
forward_list 不支持 push_back 和 emplace_back ,有特有 insert 和 emplace
vector 和 string 不支持头插
int number; std::vector<int> container; while (std::cin >> number){ container.push_back(number); //容器内的元素是拷贝 } std::string str; str.push_back('s'); //等价于 str +='s'
list,forward_list 和 deque 容器支持将元素插入到容器头部
std::list<int> list; //将元素添加到list开头 for (size_t i =0; i !=4; ++i){ list.push_front(i); }
Insert 提供通用功能
Insert 函数可利用迭代器插入到其指向任意位置前
将元素插入到 vector(不尾后插入) ,deque(不前后) 和 string(不尾后) 任意位置均合法,不合理的使用会很耗时
//vector不支持push_front.但可以插入到begin()之前 std::vector<std::string> svec; std::list<std::string> slist; //等价于调用 slist.push_front("HI"); slist.insert(slist.begin(), "HI"); svec.insert(svec.begin(), "HI");
插入范围内元素
//将 10 个元素插入到 svec 末尾,并初始化为 HI svec.insert(svec.end(), 10, "HI"); //接受一对迭代器,或一个初始化列表 std::vector<std::string> v = { "A", "B", "C" }; //将 v 最后两个元素添加到 slist 的起始位置 slist.insert(slist.begin, v.end -2, v.end); slist.insert(slist.end, { "A", "B", "C" }); //运行时错误:迭代器表示要拷贝范围,不能指向与目的位置相同内容 slist.insert(slist.begin(), slist.begin(),slist.end());
使用 Insert 返回值
//C++11,insert 返回新加入元素的迭代器,如果不插入任何元素,返回第一个参数 int number1; std::list<int> slist1; auto iter = slist1.begin(); while (std::cin >> number1) { //等价于调用 push_front iter = slist1.insert(iter, number); }