【转】STL中vector、list、deque和map的区别

时间:2023-03-08 17:10:23
【转】STL中vector、list、deque和map的区别

1、vector

向量 相当于一个数组

在内存中分配一块连续的内容空间进行存储。支持不指定vector大小的存储。STL内部实现时,首先分配一个非常大的内存空间预备进行存储,即capacity()函数返回的大小,当超过此分配的空间时,再整体重新分配一块内存存储,这给人以vector为一个连续内存的感觉。通常此默认的内存分配能完成大部分情况下的存储。

优点

(1)不指定一块内存大小的数组的连续存储,即可以像数组一样操作,但可以对此数字进行动态操作。

(2)随机访问方便,即支持[ ]操作符和vector.at()

(3)节省空间。

缺点

(1)在内部进行插入删除操作效率低。

(2)只能在vector的最后进行push和pop,不能再vector的头进行push和pop。

(3)当动态添加的数据超过vector默认分配的大小时,要进行整体的重新分配、拷贝与释放

2、list

双向链表

每一个结点都包括一个信息块Info、一个前驱指针Pre、一个后驱指针Post。可以不分配必须的内存大小,方便地进行添加和删除操作。使用的是非连续的内存空间进行存储。

优点

(1)不使用连续内存完成动态操作。

(2)在内部方便的进行插入和删除操作。

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

缺点

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

(2)相对于vector占用内存多

3、deque

双端队列 double-end queue

deque是在功能上合并了vector和list

优点

(1)随机访问方便,即支持[ ]操作符和vector.at()

(2)可在内部方便的进行插入和删除操作

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

缺点

(1)占用内存多

使用区别

1、如果你需要高效地随机存取,而不在乎插入和删除的效率,使用vector

2、如果你需要大量地插入和删除,而不关心随机存取,则应使用list

3、如果你需要随机存取,而且关心两端数据的插入和删除,则应使用deque

C++ STL中vector容器的用法

vector是C++标准模板库中的部分内容,它是一个多功能的,能够操作多种数据结构和算法的模板类和函数库。vector之所以被认为是一个容器,是因为它能够像容器一样存放各种类型的对象,简单地说vector是一个能够存放任意类型的动态数组,能够增加和压缩数据。为了可以使用vector,必须在你的头文件中包含下面的代码:

#include<vector>

vector属于std命名域,因此需要通过命名限定,如下完成你的代码:

using std::vector;
vector<int> v;

或者连在一起,使用全名:

std::vector<int> v;

建议使用全局的命名域方式:

using namespace std;

1、vector的声明

vector<ElemType> c;//创建一个空的vector

vector<ElemType> c1(c2);//创建一个vector c1,并用c2去初始化c1

vector<ElemType> c(n);//创建一个含有n个ElemType类型数据的vector

vector<ElemType> c(n,elem);//创建一个含有n个ElemType类型数据的vector,并全部初始化为elem
c.~vector<ElemType>();//销毁所有数据,释放资源

2、vector容器中常用的函数。(c为一个容器对象)


c.push_back(elem);   在容器最后位置添加一个元素elem

c.pop_back();            删除容器最后位置处的元素

c.at(index);                返回指定index位置处的元素

c.begin();                   返回指向容器最开始位置数据的指针

c.end();                      返回指向容器最后一个数据单元的指针+1

c.front();                     返回容器最开始单元数据的引用

c.back();                     返回容器最后一个数据的引用

c.max_size();              返回容器的最大容量

c.size();                      返回当前容器中实际存放元素的个数

c.capacity();               同c.size()

c.resize();                   重新设置vector的容量

c.reserve();                同c.resize()

c.erase(p);               删除指针p指向位置的数据,返回下指向下一个数据位置的指针(迭代器)

c.erase(begin,end)     删除begin,end区间的数据,返回指向下一个数据位置的指针(迭代器)

c.clear();                    清除所有数据

c.rbegin();                  将vector反转后的开始指针返回(其实就是原来的end-1)

c.rend();                     将vector反转后的结束指针返回(其实就是原来的begin-1)

c.empty();                   判断容器是否为空,若为空返回true,否则返回false

c1.swap(c2);               交换两个容器中的数据

c.insert(p,elem);          在指针p指向的位置插入数据elem,返回指向elem位置的指针

c.insert(p,n,elem);      在位置p插入n个elem数据,无返回值

c.insert(p,begin,end) 在位置p插入在区间[begin,end)的数据,无返回值


C++ STL中List的用法

1、常用函数


assign()                       给list赋值 
back()                         返回最后一个元素 
begin()                        返回指向第一个元素的迭代器 
clear()                         删除所有元素 
empty()                       如果list是空的则返回true 
end()                           返回末尾的迭代器 
erase()                        删除一个元素 
front()                          返回第一个元素 
get_allocator()            返回list的配置器 
insert()                        插入一个元素到list中 
max_size()                  返回list能容纳的最大元素数量 
merge()                       合并两个list 
pop_back()                  删除最后一个元素 
pop_front()                  删除第一个元素 
push_back()                在list的末尾添加一个元素 
push_front()                在list的头部添加一个元素 
rbegin()                       返回指向第一个元素的逆向迭代器 
remove()                     从list删除元素 
remove_if()                 按指定条件删除元素 
rend()                         指向list末尾的逆向迭代器 
resize()                       改变list的大小 
reverse()                    把list的元素倒转 
size()                          返回list中的元素个数 
sort()                          给list排序 
splice()                       合并两个list 
swap()                        交换两个list 
unique()                      删除list中重复的元素


2、实例

实例一:

/**
* File name: main.cpp
* Date: 2017.10.12
* Description:Example of using List
*/ #include <iostream>
#include <list>
#include <numeric>
#include <algorithm>
using namespace std; //创建一个list容器的实例LISTINT
typedef list<int> LISTINT;
//创建一个list容器的实例LISTCHAR
typedef list<char> LISTCHAR; int main()
{
//用list容器处理整型数据
LISTINT listOne;
//声明i为迭代器
LISTINT::iterator i; //从前面向listOne容器中添加数据
listOne.push_front();
listOne.push_front(); //从后面向listOne容器中添加数据
listOne.push_back();
listOne.push_back(); //从前向后显示listOne中的数据
cout << "listOne.begin() --- listOne.end():" << endl;
for (i = listOne.begin(); i != listOne.end(); ++i)
cout << *i << " ";
cout << endl; //从后向前显示listOne中的数据
LISTINT::reverse_iterator ir;
cout << "listOne.rbegin() --- listOne.rend():" << endl;
for (ir = listOne.rbegin(); ir != listOne.rend(); ir++)
cout << *ir << " ";
cout << endl; //使用STL的accumulate(累加)算法
int result = accumulate(listOne.begin(), listOne.end(), );
cout << "Sum=" << result << endl;
cout << "-------------------------" << endl; //-----------------------------
//用list容器处理字符型数据
//----------------------------- //用LISTCHAR创建一个名为listTwo的list对象
LISTCHAR listTwo;
//声明j为迭代器
LISTCHAR::iterator j; //从前面向listTwo容器中添加数据
listTwo.push_front('B');
listTwo.push_front('A'); //从后面向listTwo容器中添加数据
listTwo.push_back('x');
listTwo.push_back('y'); //从前向后显示listTwo中的数据
cout << "listTwo.begin() --- listTwo.end():" << endl;
for (j = listTwo.begin(); j != listTwo.end(); j++)
cout << *j << " ";
cout << endl; //使用STL的max_element算法求listTwo中的最大元素并显示
j = max_element(listTwo.begin(), listTwo.end());
cout << "The maximum element in listTwo is: " << *j << endl;
return ; }

输出结果:

【转】STL中vector、list、deque和map的区别

实例二:

//实例二
#include <iostream>
#include <list> using namespace std;
typedef list<int> INTLIST; //从前向后显示list队列的全部元素
void put_list(INTLIST list, char *name)
{
INTLIST::iterator plist; cout << "The contents of " << name << " : ";
for (plist = list.begin(); plist != list.end(); plist++)
cout << *plist << " ";
cout << endl;
} //测试list容器的功能
int main(void)
{
//list1对象初始为空
INTLIST list1;
//list2对象最初有10个值为6的元素
INTLIST list2(, ); //声明一个名为i的双向迭代器
INTLIST::iterator i; //从前向后显示各list对象的元素
put_list(list1, "list1");
put_list(list2, "list2"); //从list1序列后面添加两个元素
list1.push_back();
list1.push_back();
cout << "list1.push_back(2) and list1.push_back(4):" << endl;
put_list(list1, "list1"); //从list1序列前面添加两个元素
list1.push_front();
list1.push_front();
cout << "list1.push_front(5) and list1.push_front(7):" << endl;
put_list(list1, "list1"); //在list1序列中间插入数据
list1.insert(++list1.begin(), , );
cout << "list1.insert(list1.begin()+1,3,9):" << endl;
put_list(list1, "list1"); //测试引用类函数
cout << "list1.front()=" << list1.front() << endl;
cout << "list1.back()=" << list1.back() << endl; //从list1序列的前后各移去一个元素
list1.pop_front();
list1.pop_back();
cout << "list1.pop_front() and list1.pop_back():" << endl;
put_list(list1, "list1"); //清除list1中的第2个元素
list1.erase(++list1.begin());
cout << "list1.erase(++list1.begin()):" << endl;
put_list(list1, "list1"); //对list2赋值并显示
list2.assign(, );
cout << "list2.assign(8,1):" << endl;
put_list(list2, "list2"); //显示序列的状态信息
cout << "list1.max_size(): " << list1.max_size() << endl;
cout << "list1.size(): " << list1.size() << endl;
cout << "list1.empty(): " << list1.empty() << endl; //对list1容器排序
list1.sort();
put_list(list1, "list1"); return ;
}

输出结果:

【转】STL中vector、list、deque和map的区别

C++ STL中deque的用法

1、常用函数

【转】STL中vector、list、deque和map的区别

deque的实现比较复杂,内部会维护一个map(注意!不是STL中的map容器),即一小块连续的空间,该空间中每个元素都是指针,指向另一段(较大的)区域,这个区域称为缓冲区,缓冲区用来保存deque中的数据。因此deque在随机访问和遍历数据会比vector慢。具体的deque实现可以参考《STL源码剖析》。下面给出deque的结构图:

【转】STL中vector、list、deque和map的区别

如下是deque的使用范例:

//双向队列 deque
//by MoreWindows http://blog.csdn.net/morewindows
#include <deque>
#include <cstdio>
#include <algorithm>
using namespace std;
int main()
{
deque<int> ideq(); //Create a deque ideq with 20 elements of default value 0
deque<int>::iterator pos;
int i; //使用assign()赋值 assign在计算机中就是赋值的意思
for (i = ; i < ; ++i)
ideq[i] = i; //输出deque
printf("输出deque中数据:\n");
for (i = ; i < ; ++i)
printf("%d ", ideq[i]);
putchar('\n'); //在头尾加入新数据
printf("\n在头尾加入新数据...\n");
ideq.push_back();
ideq.push_front(i); //输出deque
printf("\n输出deque中数据:\n");
for (pos = ideq.begin(); pos != ideq.end(); pos++)
printf("%d ", *pos);
putchar('\n'); //查找
const int FINDNUMBER = ;
printf("\n查找%d\n", FINDNUMBER);
pos = find(ideq.begin(), ideq.end(), FINDNUMBER);
if (pos != ideq.end())
printf("find %d success\n", *pos);
else
printf("find failed\n"); //在头尾删除数据
printf("\n在头尾删除数据...\n");
ideq.pop_back();
ideq.pop_front(); //输出deque
printf("\n输出deque中数据:\n");
for (pos = ideq.begin(); pos != ideq.end(); pos++)
printf("%d ", *pos);
putchar('\n');
return ;
}

输出结果:

【转】STL中vector、list、deque和map的区别

另外要注意一点。对于deque和vector来说,尽量少用erase(pos)和erase(beg,end)。因为这在中间删除数据后会导致后面的数据向前移动,从而使效率低下。

参考

1、STL中vector、list、deque和map的区别

2、STL系列之一 deque双向队列