001_顺序性容器

Vector

 

特点:

      1. 指定一块如同数组一样的连续存储,但空间可以动态扩展。即它可以像数组一样操作,并且可以进行动态操作。通常体现在push_back() pop_back() 。
      2.  随机访问方便,它像数组一样被访问,即支持[ ] 操作符和vector.at()
      1. 节省空间,因为它是连续存储,在存储数据的区域都是没有被浪费的,但是要明确一点vector 大多情况下并不是满存的,在未存储的区域实际是浪费的。
      1. 在内部进行插入、删除操作效率非常低,这样的操作基本上是被禁止的。Vector 被设计成只能在后端进行追加和删除操作,其原因是vector 内部的实现是按照顺序表的原理。
      1. 只能在vector 的最后进行push 和pop ,不能在vector 的头进行push 和pop 。
      1. 当动态添加的数据超过vector 默认分配的大小时要进行内存的重新分配、拷贝与释放,这个操作非常消耗性      能。 所以要vector 达到最优的性能,最好在创建vector 时就指定其空间大小。

例子:

#include <iostream>

#include <vector>

using namespace std;

void main()

{

vector<int> vec1;//<>中可为其他类型,或者自定义的数据结构

for (int i = 0;i < 50;i++)

{

vec1.push_back(i);//加数据                

}

for (int i = (int)vec1.size();i>0;i--)

{

vec1.pop_back();//清数据

}

cout<<endl<<"the size of the vector is:"<<vec1.size()<<endl;

}

void main()

{

vector<int> vec1;

vec1.assign(50,1);//将50个1,赋值给vec1

for (int i = 0;i < 50;i++)

{

cout<<vec1.at(i)<<endl;                

}

cout<<endl<<"the size of the vector is:"<<vec1.size()<<endl;

}

//=======================================================================================================================================================

List

特点:

(1) 不使用连续的内存空间这样可以随意地进行动态操作;

(2) 可以在内部任何位置快速地插入或删除,当然也可以在两端进行push和pop 。

(3) 不能进行内部的随机访问,即不支持[ ] 操作符和vector.at();

          Lists将元素按顺序储存在链表中,与向量(vectors)相比,它允许快速的插入和删除,但是随机访问却比较慢.

例子:

#include <iostream>

#include <list>

using namespace std;

void main()

{

list<int> lst;

lst.assign(60,22);

for (int i = 0;i < 50;i++)

{

lst.push_back(i);                

}

for (int i = 0;i < lst.size();i++)

{

int j = lst.front();

lst.pop_front();

cout<<j<<endl;

lst.push_back(j);

}//遍历List结构中的所有元素

cout<<endl<<"the size of the list is:"<<lst.size()<<endl;

}

 

void main()

{

list<int> lst;

for (int i = 0;i < 10;i++)

{

lst.push_back(10 - i);                

}

for (int i = 0;i < lst.size();i++)

{

int j = lst.front();

lst.pop_front();

cout<< j <<endl;

lst.push_back(j);

}//遍历List结构中的所有元素

lst.sort();

cout<<j<<endl;

for (int i = 0;i < lst.size();i++)

{

int j = lst.front();

lst.pop_front();

cout<<j<<endl;

lst.push_back(j);

}//遍历List结构中的所有元素

cout<<endl<<"the size of the list is:"<<lst.size()<<endl;

}

 

//=======================================================================================================================================================

Deque

 

特点:

(1) 随机访问方便,即支持[ ] 操作符和vector.at() ,但性能没有vector 好;

(2) 可以在内部进行插入和删除操作,但性能不及list ;

(3) 可以在两端进行push 、pop ;

(4) 相对于verctor 占用更多的内存。

双向队列和向量很相似,但是它允许在容器头部快速插入和删除(就像在尾部一样)。

例子:

#include <iostream>

#include <deque>

using namespace std;

void main()

{

deque<int> que;

que.assign(10,1);

for (int i = 0;i < 10;i++)

{

que.push_back(10 - i);                

}

que.back() = 100;

for (int i = 0;i < que.size();i++)

{

cout<<que.at(i)<<" ";

}//遍历List结构中的所有元素

que.resize(10);

cout<<endl;

for (int i = 0;i < que.size();i++)

{                

cout<<que.at(i)<<" ";

}//遍历List结构中的所有元素

cout<<endl<<"the size of the list is:"<<que.size()<<endl;

}

三者比较:

vector 是一段连续的内存块,而deque 是多个连续的内存块, list 是所有数据元素分开保存,可以是任何两个元素没有连续。

vector 的查询性能最好,并且在末端增加数据也很好,除非它重新申请内存段;适合高效地随机存储。

list 是一个链表,任何一个元素都可以是不连续的,但它都有两个指向上一元素和下一元素的指针。所以它对插入、删除元素性能是最好的,而查询性能非常差;适合大量地插入和删除操作而不关心随机存取的需求。

deque 是介于两者之间,它兼顾了数组和链表的优点,它是分块的链表和多个数组的联合。所以它有被list好的查询性能,有被vector好的插入、删除性能。 如果你需要随即存取又关心两端数据的插入和删除,那么deque是最佳之选。

 

原文地址:https://www.cnblogs.com/OldGlory/p/3548197.html