vector(动态数组)

基本操作

#include<iostream>
#include<vector>
using namespace std;
template<class T>
void PrintVector(T s,T e){for(;s!=e;s++){cout<<*s<<" ";}cout<<endl;
}
int main(){int a[5]={1,2,3,4,5};vector<int> v(a,a+5);cout<<v.end()-v.begin()<<endl;//随机访问迭代器可以相减，此处输出的是vector元素个数v.insert(v.begin()+2,13);//如果用insert插入，需要标明（插入位置，插入内容）v.erase(v.begin()+2);//删除位于begin()+2的元素vector<int> v2(4,100);//新的初始化，v2有4个元素，都是100v2.insert(v2.begin(),v.begin()+1,v.begin()+3);//insert（插入位置，插入区间起点，插入区间重点）v.erase(v.begin()+1,v.begin()+3);//删除一整段区间PrintVector(v2.begin(),v2.end());
}

vector构建二维数组

#include<iostream>
#include<vector>
using namespace std;
int main(){vector<vector<int> > v(3);//v有3个元素，每个元素都是vector<int> 容器for(int i=0;i<v.size();i++){for(int j=0;j<4;j++){v[i].push_back(j);}}for(int i=0;i<v.size();i++){for(int j=0;j<v[i].size();j++){cout<<v[i][j]<<" ";}cout<<endl;/*输出0 1 2 30 1 2 30 1 2 3*/}
}

外层循环都是小于v.size();内层的读入和输出都需要额外注意

deque(双向队列)

所有适用于vector的操作都适用于duque

• deque还有push_front（将元素插入到前面）
• 还有pop_front（删除最前面的元素）
• 复杂度均为常数时间O(1)

list(双向链表)

• 在任何位置插入删除都是常数时间

• 不支持随机存取

• 除具有所有顺序容器都有的成员函数以外，还支持8个成员函数

/*push_front:在前面插入
pop_front:删除前面的元素
sort:排序（list不支持STL的算法sort）
remove:删除和指定值相等的所有元素
unique:删除所有和前一个元素相同的元素要做到元素不重复，则unique之前还需要sort
merge:合并两个链表，并清空被合并那个
reverse:颠倒链表
splice:在指定位置前面插入另一链表中的一个或多个元素，并在另一链表中删除被插入元素*/

操作实例

#include<iostream>
#include<list>
#include<algorithm>
using namespace std;
class A{private:int n;public :A(int n_){n=n_;}friend bool operator<(const A & a1,const A & a2);friend bool operator==(const A & a1, const A & a2);friend ostream & operator <<( ostream & o,const A & a);
};
bool operator<(const A & a1,const A & a2){return a1.n<a2.n;
}
bool operator==(const A & a1, const A & a2){return a1.n==a2.n;
}
ostream & operator <<( ostream & o,const A & a){o<<a.n;return o;
}
template <class T>
void PrintList(const list<T> & lst){//这里的参数是不推荐的写法，模板里引入list——还是传入两个迭代器，一个起点，一个终点作为参数更好typename list<T>::const_iterator i;i=lst.begin();for(i=lst.begin();i!=lst.end();i++){cout<<*i<<",";}
}//typename用来说明list<T>::const_iterator是个类型，在vs中不写也可以
int main(){list<A> lst1,lst2;lst1.push_back(1);lst1.push_back(2);lst1.push_back(3);lst1.push_back(3);lst1.push_back(4);lst1.push_back(2);//此处，每个list都是classA对象，但是可以push_back一个常数//是因为 class里面写了自动转换类型的函数，可以将整数转换成classA对象lst2.push_back(10);lst2.push_back(20);lst2.push_back(50);lst2.push_back(30);lst2.push_back(30);lst2.push_back(40);lst2.push_back(40);//后置插入cout<<"1.";PrintList(lst1);cout<<endl;cout<<"1.";PrintList(lst2);cout<<endl;lst2.sort();//排序！(list的排序，不可以使用STL的sort()函数)cout<<"1)";PrintList(lst2);cout<<endl;lst2.pop_front();//删除最前面的元素cout<<"2)";PrintList(lst2);cout<<endl;lst2.reverse();//反转链表成员函数cout<<"3)";PrintList(lst2);cout<<endl;lst2.remove(30);//删除所有和A(2)相等的元素cout<<"4)";PrintList(lst2);cout<<endl;lst2.unique();//删除所有和前一个元素相等的元素cout<<"5)";PrintList(lst2);cout<<endl;lst1.merge(lst2);//合并lst2到lst1，并且会清空lst2cout<<"6)";PrintList(lst1);cout<<endl;lst2.push_back(100);lst2.push_back(200);lst2.push_back(300);lst2.push_back(400);list<A>::iterator p1,p2,p3;p1=find(lst1.begin(),lst1.end(),3);p2=find(lst2.begin(),lst2.end(),200);p3=find(lst2.begin(),lst2.end(),400);//find()是algorithm的函数，返回的是指向找到元素的迭代器lst1.splice(p1,lst2,p2,p3);//将lst2的[p2,p3)插入到p1之前，并从lst2中删除[p2,p3);cout<<"7)";PrintList(lst1);cout<<endl;cout<<"8)";PrintList(lst2);cout<<endl;return 0;
}