vector、deque、stack、queue以及list的使用
注意：以下测试案例都要加上相应的头文件，必要时要加上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;
}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;
}
版权声明：本文为helloworldcode原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。