C++学习笔记--顺序容器

容器是一种模版类型，可以容纳某种指定的类型。顺序容器是指，容器中的元素是按元素加入容器的顺序存储的。 常用的顺序容器有vector、(string)、list、deque，以及C++11新增的forward_list和array。string的定义是“typedef basic_string<char> string;”，它虽然不是容器，但是提供了很多类似容器的操作。 1、不同容器的特点 以上容器虽然都是顺序容器，但是在插入（删除）元素、随机访问元素的代价方面有所不同。 （1）vector和string将元素保存在连续的存储空间中，类似数组，随机访问很快，但插入（删除）元素需要移动元素。vector和string虽然是类似数组的连续存储，但是支持尾部动态高效增长，因为它们通常会分配比实际元素个数更大的空间，多余空间作为备用空间，用于高效添加元素，只有当前空间不足时，才重新分配更大的空间。常用的内存大小分配策略是当前容量翻倍，使用v.capacity()查看当前空间大小，使用v.reverse(n)显式分配大小为n的空间； （2）list就是数据结构中的双向链表，任何位置插入（删除）元素很快，但不支持随机访问； （3）deque是双端队列，两端插入（删除）元素很快，但是在中间位置操作需要移动元素，支持随机访问； （4）forward_list是单向链表； （5）array其实就是vector的弱化版本，不支持动态增长，是内置数组的强化版本，多了容器相关的操作。个人认为能使用array的地方就能用vector，用vector并不会有多大的性能损失，所以此处不介绍array，用vector即可。 2、容器选择原则 （1）处理字符串用string； （2）除非有很明确的理由选择其他容器，否则默认使用vector； （3）要求随机访问用vector和deque，经常在头尾位置但不会在中间插入用deque，经常在中间位置插入用list； （4）某一阶段需要随机访问，但另一阶段不再需要，却要中间插入，则进行不同容器间的拷贝以适应不同操作； 尽量使用迭代器，不要使用下标，这样在必要的时候切换vector或list都比较方便。 3、容器通用操作（以vector为例） （1）构造函数 vector<T> v1;                v1是一个空vector，它潜在的元素是T类型的，执行默认初始化 vector<T> v2(v1);            v2中包含有v1所有元素的副本，v2与v1的T必须相同 vector<T> v2 = v1;            等价于v2(v1)，复制初始化 vector<T> v3(n, val);        v3包含了n个重复的元素，每个元素的值都是val vector<T> v4(n);            v4包含了n个重复的已默认初始化的对象 vector<T> v5{a,b,c...};        v5包含了右边列表中的元素 vector<T> v5 = {a,b,c...};    等价于v5{a,b,c...}，复制初始化 vector<T> v6(b,e);            将迭代器b、e指定范围内的元素拷贝到v6 （2）访问 range for语句        迭代访问p92（C++11新增）； 迭代器                迭代器首次定义在p95，类似于链表中的指针，二分查找的实例在p100； 下标v[i]            p92，下标可以访问任意一个vector对象中存在的元素，下标是由vector定义的size_type类型，因为vector对象的类型总是包含着元素的类型，如vector<int>::size_type，最好的办法是使用decltype(v.size())自动推断下标的类型（p166）。注意vector的长度是可变的，使用下标访问vector一定要注意下标是否越界； 下标v.at(i)            p310，at(i)更安全，如果i超出有效范围，将会抛出out_of_range异常； v.front()            返回首元素引用 v.back()            返回尾元素引用 （3）插入（forward_list不支持） v.push_back(t)        尾部添加元素t，调用拷贝构造函数 v.emplace_back(t)    尾部添加元素t，调用构造函数 seq.push_front(t)    头部添加元素t，调用拷贝构造函数（vector和string不支持） seq.emplace_front(t)头部添加元素t，调用构造函数（vector和string不支持） v.insert(p,t)        在迭代器p指向的元素之前插入元素t v.insert(p,n,t)        在迭代器p指向的元素之前插入n个值为t的元素 v.insert(p,b,e)        在迭代器p指向的元素之前插入迭代器b和e指定的范围内的元素 v.insert(p,i1)        在迭代器p指向的元素之前插入花括号列表i1 （4）删除 v.pop_back()        删除尾元素（forward_list不支持） v.pop_front()        删除头元素（vector和string不支持） v.earse(p)            删除迭代器p指向的元素 v.earse(b,e)        删除迭代器b和e所指定范围的元素 v.clear()            清空容器 （5）赋值和swap v=v1；                将v中的元素替换为v1中的拷贝 v={a,b,c...}        将v中的元素替换为初始化列表中元素的拷贝 v.swap(v1)            交换v和v1中的元素，两者必须有相同的类型，交换比v1拷贝到v要快很多 v.assign(b,e)        将v中的元素替换为迭代器b和e所表示的范围中的元素 v.assign(i1)        将v中的元素替换为初始化列表中元素 v.assign(n,t)        将v中的元素替换为n个值为t的元素 （6）获取迭代器 begin()、end()、cbegin()、cend()、rbegin()、rend()、crbegin()、crend()（c表示const迭代器，r表示反向迭代器） （7）类型别名 iterator、const_iterator、reverse_iterator、const_reverse_iterator、 size_type、difference_type、value_type、reference、const_reference 4、例外的forward_list插入/删除操作 由于forward_list是单向链表，无法获取前驱，所以单向链表的插入/删除操作都是针对指向的元素之后的元素，例如a1、a2、a3是单向列表中的元素，为了删除a3，应该使用指向a2的迭代器调用earse_after。 lst.before_begin() lst.cbefore_begin() lst.insert_after(p,t) lst.insert_after(p,n,t) lst.insert_after(p,b,e) lst.insert_after(p,i1) lst.emplace_after(p,args) lst.erase_after(p) lst.erase_after(b,e) 5、额外的string操作 额外的string操作提供了string类和C风格数组之间的相互转换，也提供了使用下标替代迭代器的版本。 （1）构造函数 string s(cp,n)            s是cp指向的数组中前n个字符的拷贝 string s(s2,pos2)        s是string s2从下标pos2开始的字符的拷贝 string s(s2,pos2,len2)    s是string s2从下标pos2开始的len2个字符的拷贝 （2）插入/删除/替换 s.insert(pos,args)        在pos之前插入args指定的字符，pos可以是下标或迭代器 s.earse(pos,len)        删除从位置pos开始的len个字符 s.assign(args)            将s中的字符替换为args指定的字符 s.append(args)            在s末尾添加args指定的字符 s.replace(range,args)    将range范围内的字符替换为args指定的字符 agrs可以是这些形式：str、str,pos,len、cp,len、cp、n,c、b,e、初始化列表 （3）搜索子字符串 s.find(agrs)            查找s中args第一次出现的位置 s.rfind(args)            查找s中args最后一次出现的位置 s.find_first_of(args)    在S中查找args中任何一个字符第一次出现的位置 s.find_last_of(args)    在S中查找args中任何一个字符最后一次出现的位置 s.find_first_not_of(args)在S中查找第一个不在args中的字符 s.find_last_not_of(args)在S中查找最后一个不在args中的字符 s.substr(pos,n)            返回一个string，包含s中从pos开始的n个字符的拷贝 agrs可以是这些形式：c,pos、s2,pos、cp,pos、cs,pos,n （4）数值转换 tostring(val)            将数值类型val转换成string stoi(s,p,b)                p是size_t指针，b表示转换所用的基数，默认值为10，即十进制。将s中p位置开始的字串转换为数值 stol(s,p,b) stoul(s,p,b) stoll(s,p,b) stoull(s,p,b) stof(s,p)                p是size_t指针，将s中p位置开始的字串转换为浮点值 stod(s,p) stold(s,p) 6、顺序容器适配器 （1）stack stack默认基于deque实现，也可以在list或vector上实现。用户可以在初始化stack时，显示地指定一个顺序容器作为第二个类型参数，来重载默认容器类型，如stack<string> str_stk是默认基于deque实现的，而stack<string, vector<string>> str_stk是基于vector实现的。大多数情况下使用默认的实现即可。支持的操作如下： s.pop()            删除栈顶元素 s.push(item)    拷贝item构建一个新元素压入栈顶 s.emplace(args)    直接构建一个新元素压入栈顶 s.top()            返回栈顶元素，但不出栈 （2）queue、priority_queue queue默认基于deque实现、priority_queue默认基于vector实现 q.pop()            返回queue的首元素或priority_queue的最高优先级的元素，但不删除该元素 q.front()        返回首元素或尾元素，但不删除此元素 q.back()        只适用于queue q.top()            返回最高优先级元素，但不删除该元素，只适用于priority_queue q.push(item)    在queue末尾或priority_queue中恰当的位置拷贝构造一个元素 q.emplace()        在queue末尾或priority_queue中恰当的位置直接构造一个元素