一、顺序容器概述
顺序容器提供了控制元素存储和访问顺序的能力，顺序与元素加入容器时的位置相对应。
1、常见的顺序容器类型：
vector：可变大小的数组。支持快速随机访问，在尾部之外的位置插入或者删除元素可能很慢。
deque：双端队列。支持快速随机访问。在头尾位置插入/删除速度很快。
只支持双向顺序访问。在list任何位置插入/删除速度很快。
forward_list：单向链表。只支持单向顺序访问。在forward_list任何位置插入/删除速度很快。
array ：固定大小的数组。支持快速随机访问。不能添加或者删除元素。
string：与vector相似的容器，专门存储字符。随机访问快。在尾位置插入/删除速度很快。
支持随机访问的容器：vector、deque、array 、string。
支持在任意位置插入/删除元素：list、forward_list。
在尾部插入元素：vector、string、deque（头部也可以）。
现代C++程序应该使用标准容器库。
二、容器库概览
1、迭代器：用于访问容器的元素。[begin,end)，分别表示指向首元素的迭代器和指向尾元素之后位置的迭代器，使用解引用即可得到容器的元素，显然不能对end迭代器进行解引用。
#include <iostream>
#include <vector>//容器。
#include <list>//双向链表。
#include <deque>//双端队列。
#include <array>//具有固定大小的数组。
using namespace std;
using v_int = vector<int>;//使用类型别名。
using v_str = vector<string>;//vector支持下标访问，但是list不支持,vector中建议使用.at(num)方式进行下标访问。
using v_const_char = vector<const char *>;
using l_str = list<string>;
using d_str = deque<string>;
using a_int10 = array<int,10>;//array数组必须指定大小。
using a_st10 = array<int,10>::size_type;//array的元素类型。
v_int vec{0,1,4,3,4,5,6};//列表初始化。
v_str vec2;//一个空的vector,元素类型为string。
v_int vec3(10);//所有元素都初始化为0。
v_int::iterator it1 = vec.begin();//指向容器首元素的迭代器。
auto it2 = vec.cend();//指向尾元素之后的迭代器,只读迭代器。
int flag=0;
while(it1 != it2)
{
if(*it1 == 3)//匹配给定的元素。
{
flag=1;
cout << *it1 << endl;//解引用。
}
++it1;//迭代器移动。
}
if(!flag)
{
cout << "can't find it" << endl;
}2、容器的定义和初始化：
【Note】：
拷贝时，两个容器的容器类型和元素类型都必须相同。
只有顺序容器的构造函数才接受大小参数，关联容器不允许。
array无此限制。
l_str list1{"abc","cde"};//列表初始化
v_str vec_str={"A","B","C","D","E"};//list1初始化为列表元素的拷贝。
l_str list2(list1);//拷贝初始化，两个容器的类型和元素类型必须相同。
d_str deque1(vec_str.begin(),vec_str.begin()+3);//初始化为两个迭代器指定范围中的元素。
for (const auto s : deque1)
{
cout << s << " ";
}
cout << endl;
a_int10 arr1 = {0,1,2,3,4,5,6,7,8,9};
a_st10 st;
for (st=0 ; st<10 ; ++st)//遍历访问元素。
{
cout << arr1[st] << " ";
}
cout << endl;3、赋值、swap、容器大小操作：
【Note】：
swap不对任何元素进行拷贝、删除和插入操作，因此可以在常数时间内完成。
2）建议使用非成员版本的swap。
定义了相应的比较运算符时，我们才可以使用关系运算符来比较两个容器。
v_const_char old_style{"哈哈","呵呵"};
vec2.assign(old_style.cbegin(),old_style.cend());
for (const auto s : vec2)
{
cout <<s << " ";
}
cout << endl;
vec2.assign(5,"MMP");//assign的第二个版本接受一个整型值和一个元素值。
for (const auto s : vec2)
{
cout <<s << " ";
}
swap(vec,vec3);//交换两个容器，内部数据结构都会交换，在常数时间内完成（除array外）。
cout << endl;
for (const auto s : vec3)//vec3原来为空，现在把vec中的六个元素交换过来了。
{
cout <<s << " ";
}
cout<<endl;
if(!vec.empty() && vec<vec3)//只有当元素类型也定义了比较运算时，才能使用关系运算符比较两个容器。
{
cout << "vec<vec3 " << vec.size() << " " << vec3.size() << endl;
} 上述代码的运行结果如下：
三、顺序容器的操作
1、向顺序容器添加元素（push_back、push_front、insert、emplace）：实际上添加的是对象值的拷贝（除了emplace）。
【Note】：
在vector或者string的尾部之外的任何位置，或者deque的首尾之外的位置添加元素，会使指向容器的迭代器、引用和指针失效。
实际上放入到容器中的是对象值的拷贝。
3）emplace直接构造元素而不是拷贝。
insert返回指向第一个新加入元素的迭代器。
int a;
string word;
v_int vec_int;
while(cin >> a)
{
vec_int.push_back(a);//在容器末尾添加元素，除了array和forward_list，其它容器都支持push_back。
}
for (const auto s : vec_int)
{
cout << s << " ";
}
cout << endl;
/* 不建议在一个vector、string的尾部之外或者deque的首尾之外的位置添加元素，否则会非常耗时。*/
d_int deq_int;
for (size_t i=0 ; i<4 ; ++i)
{
deq_int.push_front(i);//将元素插入到容器头部，保存的序列是输入序列的逆序。
}
for (const auto s : deq_int)
{
cout << s << " ";
}
cout << endl;
v_str vec_str{"A","B","C","D"};//定义一个vector<string>类型
l_str list1;
list1.insert(list1.begin(),"Hello");//在迭代器指向的元素之前插入元素。
list1.insert(list1.begin(),2,"Hello");//指定元素的个数。
list1.insert(list1.begin(),vec_str.end()-2,vec_str.end());//接受一对迭代器指定元素的范围。
auto iter = list1.begin();
cin.clear();//输入数字后保留有换行符,要清除掉。
while(getline(cin,word))
{
iter=list1.insert(iter,word);//insert返回指向第一个新加入元素的迭代器。
}
for (const auto s : list1)
{
cout << s << " ";
}
cout << endl;
v_int vec_int2={1,3,4};
vec_int2.emplace(vec_int2.begin()+1,2);//直接构造元素而不是拷贝，适合用对象初始化容器。
for (const auto s : vec_int2)
{
cout << s << " ";
}
cout << endl;2、访问元素（
front、back、下标访问、at）。
【Note】：
不要对空容器进行访问，也要防止下标越界。
if(!vec_int2.empty())
{
vec_int2.front()=4;//返回首元素的引用。
vec_int2.back()=1;//返回尾元素的引用。
vec_int2.at(2)=2;//返回下标为n的引用。
vec_int2[1]=3;//返回下标为n的引用。
}
for (const auto s : vec_int2)
{
cout << s << " ";
}
cout << endl;3、删除元素（pop_front、pop_back、erase、clear）。
【Note】：
vector和string不支持pop_front。
erase返回指向删除的元素之后位置的迭代器。
int i=0;
if(!list1.empty())
{
while(++i<=3)
{
list1.pop_back();//删除尾部三个元素。
}
i=0;
}
list1.clear();//删除所有元素。
list1={"a","b","c","d","e","f","g","h"};//重新初始化。
auto it = list1.begin();
while(it != list1.end())
{
if(++i % 2 ==0)//如果元素的下标为偶数
{
it = list1.erase(it);//删除此元素，erase返回指向删除的元素之后位置的迭代器。
}
else
{
++it;
}
}
for (const auto s : list1)
{
cout << s << " ";
}
cout << endl;
//erase删除多个元素。
v_int vec_int3;
for (int i=0 ; i<10 ; ++i)
{
vec_int3.push_back(i);
}
vec_int3.erase(vec_int3.begin(),vec_int3.begin()+5);//删除前五个元素。
for (const auto s : vec_int3)
{
cout << s << " ";
}
cout << endl;4、特殊的forward_list操作（
before_begin、begin、insert_after、erase_after）。
before_begin()表示首前元素，begin()表示第一个元素，也是当前要处理的元素。
fl_str flist = {"AB","EF"};
const string str1("GH");
const string str2("CD");
find_string(flist,str1,str2);
for (const auto s : flist)
{
cout << s << " ";
}
cout << endl;
fl_int flint = {0,1,2,3,4,5,6};
erase_int(flint);
for (const auto s : flint)
{
cout << s << " ";
}
cout << endl;
void find_string(fl_str &flist,const string &str1,const string &str2)//容器作为函数参数
{
int flag=0;
auto prev = flist.before_begin();//表示首前元素。
auto curr = flist.begin();//表示flist中的第一个元素，也是当前要处理的元素。
while(curr != flist.end())
{
if(*curr == str1)//查找字符串。
{
curr = flist.insert_after(curr,str2);//如果找到，则将str2插入到str1的后面。
flag=1;
}
else
{
prev = curr;//prev指向curr之前的元素。
}
++curr;//移动curr。
}
if(!flag)
{
flist.insert_after(prev,str2);//没找到str1，就将str2插入到flist的尾部。
}
}
void erase_int(fl_int &flint)
{
auto prev = flint.before_begin();
auto curr = flint.begin();
while(curr != flint.end())
{
if(*curr % 2)
{
curr = flint.erase_after(prev);//删除元素并移动。
}
else
{
prev = curr;
++curr;
}
}
}5、改变容器大小（
resize）。
list<int> lst(10,1)//十个int，每个都是1。
lst.resize(20,0)//将十个（20-10）0添加到容器末尾。6、容器操作可能使迭代器失效，尤其是对vector、string或者deque进行插入和删除操作（
insert、erase）。
v_int vec_int4 = {0,1,2,3,4,5,6,7,8,9};
auto vi4 = vec_int4.begin();
while(vi4 != vec_int4.end())
{
if(*vi4 % 2)
{
vi4 = vec_int4.insert(vi4,*vi4);//复制当前元素，更新迭代器，返回新插入元素的迭代器。
vi4+=2;
}
else
{
vi4 = vec_int4.erase(vi4);
}
}
for (const auto s : vec_int4)
{
cout << s << " ";
}
cout << endl; 上述代码的运行结果如下：
四、vector对象是如何增长的
为了支持快速随机访问，vector将元素连续存储，所以如果没有空间容纳新元素，将无法添加元素。如果将已有元素移动到新空间，然后添加新元素，释放旧空间，性能会非常慢。
当不得不获取新的内存空间时，vector和string的实现通常会分配比新的空间需求更大的内存空间，容器预留这些空间作为备用，可以保存更多的新元素。
#include <iostream>
#include <vector>
using namespace std;
using v_int = vector<int>;
int main()
{
v_int vec;
//capacity表示不分配新空间的情况下最多可以保存多少元素，size是指已经保存的元素数量。
cout << "vec size : " << vec.size() << " capacity : " << vec.capacity()<< endl;
for (int i=0 ; i<24 ; ++i)
{
vec.push_back(i);
}
cout << "vec size : " << vec.size() << " capacity : " << vec.capacity()<< endl;
vec.reserve(50);//预留更大的空间，不改变vector中的元素。
cout << "vec size : " << vec.size() << " capacity : " << vec.capacity()<< endl;
vec.shrink_to_fit();//要求归还内存。
cout << "vec size : " << vec.size() << " capacity : " << vec.capacity()<< endl;
system("pause");
return 0;
}
上述代码的运行结果如下：
五、额外的string操作
1、构造string的其他方法（拷贝、substr（常用））。
string str1(cp+6,5);//从cp[6]开始拷贝5个字符。
cout << str1 << endl;
string str2(str,2,3);//从str[2]开始拷贝3个字符。
cout << str2 << endl;
//从str[2]开始拷贝5个字符，省略前一个参数则默认从0位置开始，省略后面一个参数,则默认拷贝到末尾。
string str3 = str.substr(2,5);
cout << str3 << endl;2、改变string的其他方法（
insert、replace、append（常用））。
string str4 = str.insert(0,cp);//在str的0位置之前插入一个字符串。
cout << str4 << endl;
str4.replace(11,3,"???");//从位置11开始，删除三个字符并替换为指定的字符，返回引用。
cout << str4 << endl;
str4.append("LMN");//将新字符追加到字符串末尾，返回引用。
cout << str4 << endl;3、string的搜索操作（
find（常用）、find_first_of（常用）、find_first_not_of、find_last_of）。
auto pos1 = str4.find("???");//返回指定字符串第一次出现的位置。
cout << pos1 << endl;
auto pos2 = str4.find_first_of('A');//返回指定字符第一次出现的位置。
cout << pos2 << endl;
string numbers("0123456789"),phone("ab2c3d7R");
string::size_type pos = 0;
//查找与给定字符串中任何一个字符匹配的位置。
while((pos = phone.find_first_of(numbers,pos)) != string::npos)//从pos位置开始查找。
{
cout << phone[pos] << " ";
++pos;
}
cout << endl;
pos=0;
//搜索第一个不在参数中的字符。
while((pos = phone.find_first_not_of(numbers,pos)) != string::npos)
{
cout << phone[pos] << " ";
++pos;
}
cout << endl;4、string的比较操作（
compare）。
string str5 ("green apple");
string str6 ("red apple");
if(str5.compare(str6) != 0)//比较str5和str6。
{
cout << str5 << " is not " << str6 << endl;
}
//将str5从第6个位置开始的5个字符与指定字符串比较。
if(str5.compare(6,5,"apple") == 0)
{
cout << "still, " << str5 << " is an apple\n";
}
if(str6.compare(str6.size()-5,5,"apple") == 0)
{
cout << "and " << str6 << " is also an apple\n";
}
//str5从第6个位置开始的5个字符与str6的第4个位置开始的5个字符比较。
if (str5.compare(6,5,str6,4,5) == 0)
{
cout << "therefore, both are apples\n";
}5、数值转换（
stoi、to_string）。
v_int vec;
string str7;
while(getline(cin,str7))
{
int str_to_int = stoi(str7);//把string转换为int类型，还要其他类型（stod、stoul、stof等）。
vec.push_back(str_to_int);
}
int count=0;
for (const auto &s : vec)
{
count+=s;
}
cout << count <<endl;
string str8 = to_string(count);//转换为string。
cout << str8 <<endl; 上述代码运行结果如下：
六、容器适配器
1、stack栈适配器（push、empty、top、pop、size），标准库stack使用一种后进先出（LIFO）的存储和访问策略。
stack<int> stack_test;//创建一个空栈。
for (size_t i=0 ; i!=5 ; ++i)
{
stack_test.push(i);//压入栈顶。
}
while(!stack_test.empty())
{
int value = stack_test.top();//获取栈顶元素。
cout << value << " ";
stack_test.pop();//删除栈顶元素，但不返回元素值。
}
cout << endl;2、queue队列适配器（ push、empty、front、pop、back、top(优先队列使用)），标准库queue使用一种先进先出（FIFO）的存储和访问策略。
queue<int> queue_test;
for (size_t i=0 ; i!=5 ; ++i)
{
queue_test.push(i);//压入队列。
}
while(!queue_test.empty())
{
int value = queue_test.front();//获取队列首元素。
cout << value << " ";
value = queue_test.back();//获取队列尾元素。
cout << value << " ";
queue_test.pop();//弹出队列首元素，但不返回元素值。
}
cout << endl;
priority_queue<int> mypq;//优先队列，为队列中的元素建立优先级。
mypq.push(30);
mypq.push(100);
mypq.push(25);
mypq.push(40);
while(!mypq.empty())
{
cout << ' ' << mypq.top();
mypq.pop();
}
cout << endl; 上述代码运行结果如下：
