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 ; }
输出结果:
实例二:
//实例二
#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 ;
}
输出结果:
C++ STL中deque的用法
1、常用函数
deque的实现比较复杂,内部会维护一个map(注意!不是STL中的map容器),即一小块连续的空间,该空间中每个元素都是指针,指向另一段(较大的)区域,这个区域称为缓冲区,缓冲区用来保存deque中的数据。因此deque在随机访问和遍历数据会比vector慢。具体的deque实现可以参考《STL源码剖析》。下面给出deque的结构图:
如下是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 ;
}
输出结果:
另外要注意一点。对于deque和vector来说,尽量少用erase(pos)和erase(beg,end)。因为这在中间删除数据后会导致后面的数据向前移动,从而使效率低下。
参考: