注意：以下测试案例都要加上相应的头文件，必要时要加上algorithm文件。
1、vector
连续存储结构，每个元素在内存上是连续的；支持高效的随机访问和在尾端插入/删除操作，但其他位置的插入/删除操作效率低下；相当于一个数组，但是与数组的区别为：内存空间的扩展。vector的初始化操作
int main(){
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
vector<int> v2=v1;
vector<int> v3(10); //必须提前把内存大小写出(初始化元素默认值是0，即10个0）
for (int i = 0; i < 10; i++) {
v3[i]=(i+1);
}
printV(v3);
cout<<endl;
vector<int> v4{1,2,3,6};
printV(v4);
return 0;
}
元素的插入与删除
int main()
{
vector<int> v1;
cout<<"Initial size of vector: "<<v1.size()<<endl;
//push_back操作是将一个元素插入vector的末尾。
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
cout<<"size of vector(push): "<<v1.size()<<endl;
//获取头部元素
cout<<"the head element of vector: "<<v1.front()<<endl;
//循环打印尾部元素
while (v1.size() > 0) {
cout<<v1.back()<<" ";
v1.pop_back(); //删除vector的尾部元素，此函数返回值为空(void)
}
return 0;
}
随机访问并修改元素
int main(){
vector<int> v1;
cout<<"Initial size of vector: "<<v1.size()<<endl;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
//此时若想修改头部元素
v1.front()=50; //函数返回值当左值，应该返回一个引用，对此的理解参考下面的案例
//2011/12/14/2286908.html
v1.back()=20;
printV(v1);
return 0;
}
在以上案例中，函数返回值当左值的案例理解如下
int& abc(int a, int b, int c, int& result)
{
result = a + b + c;
return result;
}
int main(){
int result=0;
abc(1,2,3,result)=2;
cout<<result<<endl;
return 0;
}
顺向迭代与逆向迭代访问
int main(){
vector<int> v(10);
for (int i = 0; i < 10; ++i) {
v[i]=i+1;
}
//利用顺向迭代器去遍历
for(vector<int>::iterator it=v.begin();it!=v.end();it++){
cout<<*it<<" ";
}
cout<<endl;
//利用迭代器逆向遍历
for(vector<int>::reverse_iterator rit=v.rbegin(); rit != v.rend(); rit++){
cout<<*rit<<" ";
}
cout<<endl;
return 0;
}
元素的删除和插入
int main(){
vector<int> v(10);
for (int i = 0; i < 10; ++i) {
v[i]=i+1;
}
//vector的删除
v.erase(v.begin(),v.begin()+3);
printV(v);
//删除指定元素
v.erase(v.end()-1); //注意v.end()指向的位置在vector最后元素的下一个
printV(v);
v.insert(v.begin(),11);
v[1]=2;
v[3]=2;
v[5]=2;
printV(v);
for(vector<int>::iterator it =v.begin(); it != v.end(); ){
if(*it ==2 ){
it=v.erase(it); //删除某位值后，其后元素会自动前移
}else{
it++;
}
}
printV(v);
//插入
v.insert(v.begin(),100);
v.insert(v.end(),200);
printV(v);
return 0;
}
2、deque
连续存储结构，即其每个元素在内存上也是连续的，类似于vector，不同之处在于，deque提供了两级数组结构， 第一级完全类似于vector，代表实际容器；另一级维护容器的首位地址。这样，deque除了具有vector的所有功能外，还支持高效的首/尾端插入/删除操作。
#include<iostream>
#include<deque>
#include<algorithm>
using namespace std; void print(deque<int> &d){
for(deque<int>::iterator it=d.begin();it !=d.end();it++){
cout<<*it<<" ";
}
cout<<endl;
} int main(){
deque<int> d;
d.push_back(1);
d.push_back(3);
d.push_back(5);
d.push_back(100);
//deque的动态数组头尾都开放，因此能在头尾两端进行快速安插和删除。
d.push_front(0);
print(d); //查找
deque<int>::iterator it=find(d.begin(),d.end(),3);
if(it!=d.end()){
cout<<"已成功找到："<<*it<<"其下标地址是："<<distance(d.begin(),it)<<endl; //通过distance()可以获得相应的下标地址
}else{
cout<<"未找到！"<<endl;
}
return 0;
}
3、栈和队列
与数据结构的操作一样，较简单。
//测试程序
int main1(){
stack<int> s;
//入栈
for (int i = 0; i < 10; ++i) {
s.push(i+1);
}
//出栈
while ( !s.empty()) {
int tmp = s.top();
cout<<tmp<<" ";
s.pop();
}
cout<<endl;
return 0;
} int main2(){
queue<int> q;
q.push(1);
q.push(2);
q.push(3);
cout<<"头元素: "<<q.front()<<endl;
cout<<"尾元素: "<<q.back()<<endl;
cout<<"队列大小: "<<q.size()<<endl; while ( ! q.empty() ) {
int tmp=q.front();
cout<<tmp<<" ";
q.pop();
}
cout<<endl;
return 0;
}
4、list
非连续存储结构，具有双链表结构，每个元素维护一对前向和后向指针，因此支持前向/后向遍历。支持高效的随机插入/删除操作，但随机访问效率低下，且由于需要额外维护指针，开销也比较大。每一个结点都包括一个信息快Info、一个前驱指针Pre、一个后驱指针Post。可以不分配必须的内存大小方便的进行添加和删除操作。使用的是非连续的内存空间进行存储。
void print(list<int> &l){
for ( list<int>::iterator it = l.begin(); it != l.end(); it++) {
cout<<*it<<" ";
}
cout<<endl;
}
int main(){
list<int> l;
cout<<"list的大小："<<l.size()<<endl;
for (int i = 0; i < 10; ++i) {
l.push_back(i+1);
}
cout<<"list的大小："<<l.size()<<endl;
list<int>::iterator it=l.begin();
while (it != l.end() ) {
cout<<*it<<" ";
it++;
}
cout<<endl;
//list不能随机访问
it=l.begin();
it++; //语法正确
//it=it+2; //编译不通过，即不支持访问
//元素的插入
l.insert(l.end(),100);
l.insert(l.end(),100);
l.insert(l.end(),100);
print(l);
//元素的删除
list<int>::iterator left=l.begin();
list<int>::iterator right=l.begin();
right++; //因为没有办法it=it+2,只能一个一个移动
right++;
l.erase(left,right); //区间删除
print(l);
list<int>::iterator pos=l.begin();
pos++;
pos++;
l.erase(pos); //直接删除某个位置
print(l);
l.remove(100); //删除值为100的元素
print(l);
l.clear(); //删除所有元素
cout<<"list的大小："<<l.size()<<endl;
return 0;
}
4、set
set也是STL中比较常见的容器。set集合容器实现了红黑树的平衡二叉检索树的数据结构，它会自动调整二叉树的排列，把元素放到适当的位置。set容器所包含的元素的值是唯一的，集合中的元素按一定的顺序排列。
set集合的常用操作如下（注意要引入set头文件）：
//集合测试
int main(){
set<int> s;
set<int,greater<int>> ss; //从大到小存储
int tmp;
for (int i = 0; i < 5; ++i) {
tmp=rand()/10000000;
s.insert(tmp); //往集合中插入元素
ss.insert(tmp);
} s.insert(100);
s.insert(100);
s.insert(100); //set集合中的元素是唯一的，虽然插入这么多等值元素，但最终只会显示一个元素
ss.insert(100); //打印输出
for(set<int>::iterator it=s.begin(); it!=s.end(); it++){
cout<<*it<<" "; //依次输出84 100 168 171 180 195
} //即默认集合中的元素是从小到大排序的
cout<<endl;
for(set<int,greater<int>>::iterator it=ss.begin(); it!=ss.end(); it++){
cout<<*it<<" "; //从大到小打印d
}
cout<<endl; set<int>::iterator ir=s.begin();
//ir=ir+3; //错误，不支持随机访问
//删除集合
while ( !s.empty() ) {
set<int>::iterator it=s.begin();
s.erase(it);
}
cout<<endl;
cout<<s.size()<<endl;
return 0;
}
以上案例中set存放的是简单的整数，如果是复杂的对象，我们要指定集合中存放元素比较的依据属性，利用仿函数去实现（上述中的set集合ss的声明中的greater<int>也是用仿函数实现的），如下案例：
class Student{
public:
Student(int age,char *name){
this->age=age;
strcpy(this->name,name);
}
/*
* error: passing 'const Student' as 'this' argument discards qualifiers
* getXXX()函数一般最好加上const，
*/
const char* getName() const{
return this->name;
}
const int getAge() const {
return this->age;
}
public:
char name[20];
int age;
};
//仿函数
struct FuncStudent
{
bool operator()(const Student &left,const Student &right) const
{
if( left.getAge() < right.getAge() ){
return true; //如果左边的student的age小于右边，即从小到大排序
}
else{
return false;
}
}
};
int main(){
set<Student,FuncStudent> s;
Student s1(20,"张三");
Student s2(50,"李四");
Student s3(24,"王五");
Student s4(32,"老六");
s.insert(s1);
s.insert(s2);
s.insert(s3);
s.insert(s4);
for(set<Student,FuncStudent>::iterator it=s.begin(); it !=s.end(); it++){
cout<<it->getName()<<"\t"<<it->getAge()<<endl;
}
return 0;
}
此时又有一个问题，如果插入的元素是一个年龄相同，但姓名不同的对象的时候（测试可以通过，但结果中没有该元素），这个时候需要注意insert()的返回值了，可以用返回值来检测，具体操作如下：
int main(){
set<Student,FuncStudent> s;
Student s1(20,"张三");
Student s2(50,"李四");
Student s3(24,"王五");
Student s4(32,"老六");
//insert()函数的返回值 typedef pair<iterator,bool> _Pairib
pair<set<Student,FuncStudent>::iterator,bool> pair1=s.insert(s1);
//对插入检查是否成功
if ( pair1.second ==true ) {
cout<<"s1插入成功"<<endl;
}else{
cout<<"s1插入失败"<<endl;
}
s.insert(s2);
s.insert(s3);
s.insert(s4);
//如果插入一个年龄相同的数据
Student s5(20,"test");
pair<set<Student,FuncStudent>::iterator,bool> pair2=s.insert(s5); //插入不成功
if ( pair2.second ==true ) {
cout<<"s5插入成功"<<endl;
}else{
cout<<"s5插入失败"<<endl;
}
for(set<Student,FuncStudent>::iterator it=s.begin(); it !=s.end(); it++){
cout<<it->getName()<<"\t"<<it->getAge()<<endl;
}
return 0;
}
结果如下所示：
s1插入成功
s5插入失败
张三 20
王五 24
老六 32
李四 50
set中还有其他一些便于查找元素的方法，如下：
int main(){
set<int> s;
for (int i = 0; i < 5; ++i) {
s.insert(i+3);
}
for(set<int>::iterator it=s.begin(); it!=s.end(); it++ ){
cout<<*it<<" ";
}
cout<<endl;
//查找5的位置
set<int>::iterator it0=s.find(6);
cout<<"*it0 : "<<*it0<<endl;
int count=s.count(5);
cout<<"count "<<count<<endl;
set<int>::iterator it1=s.lower_bound(6); //返回小于等于6的元素的iterator位置
cout<<"*it1 : "<<*it1<<endl;
set<int>::iterator it2=s.upper_bound(6); //返回大于6的元素的iterator位置
cout<<"*it2 : "<<*it2<<endl;
//如果想把iterator位置接过来
/*
* typedef pair<iterator,bool> _Pairib
* typedef pair<iterator,iterator> _Pairii;
* typedef pair<const_iterator,const_iterator> _Paircc;
*/
pair<set<int>::iterator,set<int>::iterator> myPair=s.equal_range(6);
set<int>::iterator ip0=myPair.first;
cout<<"ip0 : "<<*ip0<<endl;
set<int>::iterator ip1=myPair.second;
cout<<"ip1 : "<<*ip1<<endl;
return 0;
}
还有一个问题是如果确实想在set集合中插入具有被排序元素值相同的元素，这个时候就可以考虑使用multiset，如下：
int main(){
multiset<int> s;
//与set相比特点是可以放多个相同的元素
s.insert(66);
s.insert(21);
s.insert(8);
s.insert(21);
s.insert(21);
//打印元素
for(multiset<int>::iterator it=s.begin(); it!=s.end(); it++){
cout<<"\t"<<*it;
}
cout<<endl;
//删除元素
while( !s.empty() ){
multiset<int>::iterator it=s.begin();
cout<<"\t"<<*it;
s.erase(it);
}
cout<<endl;
return 0;
}
此时结果如下：
8 21 21 21 66
8 21 21 21 66