------------------vector----------------

在最小二乘法多项式拟合的程序中http://blog.csdn.net/piaoxuezhong/article/details/54973750用到了vector,现对vector进行详解~

相应参考手册：http://www.cplusplus.com/reference/vector/vector/

向量 vector 简介：

vector 是一个线性顺序结构。相当于数组，但其大小可以不预先指定，并且可以自动扩展。它可以像数组一样被操作，可以将vector 当做一个动态数组。
在创建一个vector 后，它会自动在内存中分配一块连续的内存空间进行数据存储，初始的空间大小可以预先指定也可以由vector 默认指定，这个大小即capacity （）函数的返回值。当存储的数据超过分配的空间时vector 会重新分配一块内存块，但这样的分配是很耗时的，在重新分配空间时它会做这样的动作：
1. vector 会申请一块更大的内存块；
2. 将原来的数据拷贝到新的内存块中；
3. 销毁掉原内存块中的对象（调用对象的析构函数）；
4. 将原来的内存空间释放掉。
如果vector 保存的数据量很大时，这样的操作一定会导致糟糕的性能（这也是vector 被设计成比较容易拷贝的值类型的原因）。所以说vector 不是在什么情况下性能都好，只有在预先知道它大小的情况下vector 的性能才是最优的。

vector 的特点：

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

vector 的用法:

1.文件包含:

首先在程序开头处加上#include<vector>以包含所需要的类文件vector，还要加上using namespace std;
2.变量声明:
2.1 例:声明一个int向量以替代一维的数组:vector <int> a。
2.2 例:用vector代替二维数组.其实只要声明一个一维数组向量即可,而一个数组的名字其实代表的是它的首地址,所以只要声明一个地址的向量即可,即:vector <int *> a.同理想用向量代替三维数组也是一样,vector <int**>a;再往上面依此类推.

3.成员函数及实例用法:

vector<int> c.
c.clear()  //移除容器中所有数据。
c.empty() //判断容器是否为空。
c.erase(pos) //删除pos位置的数据
c.erase(beg,end) //删除[beg,end)区间的数据
c.front() //传回第一个数据。
c.insert(pos,elem)// 在pos位置插入一个elem拷贝
c.pop_back() //删除最后一个数据。
c.push_back(elem) //在尾部加入一个数据。
c.resize(num)//重新设置该容器的大小
c.size() //回容器中实际数据的个数。
c.begin() //返回指向容器第一个元素的迭代器
c.end() //返回指向容器最后一个元素的迭代器

程序实例：

#include<vector>  
#include<iostream>  
using namespace std;

int main()
{
int i = 0;
vector<int> vec;
for (i = 0; i < 10; i++)
{
vec.push_back(i);
}

cout << "初始化遍历：" << endl;
for (unsigned int i = 0; i < vec.size(); i++)
{
cout << vec[i] << " ";
}

cout << endl << "迭代遍历：" << endl;
vector<int>::iterator it;
for (it = vec.begin(); it != vec.end(); it++)
{
cout <<*it << " ";
}

cout << endl << "插入遍历：" << endl;
vec.insert(vec.begin() + 4, 0); 
for (unsigned int i = 0; i < vec.size(); i++)
{
cout<< vec[i] << " ";
}

cout << endl << "擦除遍历：" << endl;
vec.erase(vec.begin() + 2);
for (unsigned int i = 0; i < vec.size(); i++)
{
cout << vec[i] << " ";
}

cout << endl << "迭代遍历：" << endl;
vec.erase(vec.begin() + 3, vec.begin() + 5);
for (vector<int>::iterator it = vec.begin(); it != vec.end(); it++)
{
cout<< *it << " ";
}
cout << endl;
return 0;
}

--------------------list-------------------

链表 list 简介：

list是一个线性双向链表结构，它的数据由若干个节点构成，每一个节点都包括一个信息块（即实际存储的数据）、一个前驱指针和一个后驱指针。它无需分配指定的内存大小且可以任意伸缩，这是因为它存储在非连续的内存空间中，并且由指针将有序的元素链接起来。由于其结构的原因，list 随机检索的性能非常不好，它不像vector 那样直接找到元素的地址，而是要从头一个一个的顺序查找，这样目标元素越靠后，它的检索时间就越长。检索时间与目标元素的位置成正比。虽然随机检索的速度不够快，但是它可以迅速地在任何节点进行插入和删除操作。因为list 的每个节点保存着它在链表中的位置，插入或删除一个元素仅对最多三个元素有所影响，不像vector 会对操作点之后的所有元素的存储地址都有所影响，这一点是vector 不可比拟的。

vector，list，deque对比介绍及c++ 实例

list 的特点：

(1) 不使用连续的内存空间，可以随意地进行动态操作；
(2) 可以在内部任何位置快速地插入或删除，也可以在两端进行push 和pop ；
(3) 不能进行内部的随机访问，即不支持[ ] 操作符和vector.at() ；
(4) 相对于verctor 占用更多的内存。

list 的学习要点：

(1)定义一个list
(2)向list中加入元素
(3)如何知道list是否为空
(4)使用for循环来遍历一个list
(5)使用STL的通用算法for_each来遍历list
(6)list成员函数以及它们的意义
(7)iterator范围的概念，一个范围的最后一个位置并不被处理

list 成员函数及实例用法:

1. list中的构造函数：

list() 声明一个空列表；
list(n) 声明一个有n个元素的列表，每个元素都是由其默认构造函数T()构造出来的
list(n,val) 声明一个由n个元素的列表，每个元素都是由其复制构造函数T(val)得来的
list(n,val) 声明一个和上面一样的列表
list(first,last) 声明一个列表，其元素的初始值来源于由区间所指定的序列中的元素

2. begin()和end()：

通过调用list容器的成员函数begin()得到一个指向容器起始位置的iterator，可以调用list容器的 end() 函数来得到list末端下一位置，相当于：int a[n]中的第n+1个位置a[n]，实际上是不存在的，不能访问，经常作为循环结束判断结束条件使用。
3. push_back() 和push_front()：

使用list的成员函数push_back和push_front插入一个元素到list中。其中push_back()从list的末端插入，而 push_front()实现的从list的头部插入。
4. empty()：利用empty() 判断list是否为空。
5. resize()：

如果调用resize(n)将list的长度改为只容纳n个元素，超出的元素将被删除，如果需要扩展那么调用默认构造函数T()将元素加到list末端。如果调用resize(n,val)，则扩展元素要调用构造函数T(val)函数进行元素构造，其余部分相同。
6. clear()：清空list中的所有元素。
7. front()和back()：

通过front()可以获得list容器中的头部元素，通过back()可以获得list容器的最后一个元素。但是有一点要注意，就是list中元素是空的时候，这时候调用front()和back()会发生什么呢？实际上会发生不能正常读取数据的情况，但是这并不报错，那我们编程序时就要注意了，个人觉得在使用之前最好先调用empty()函数判断list是否为空。
8. pop_back和pop_front()：通过删除最后一个元素，通过pop_front()删除第一个元素；序列必须不为空，如果当list为空的时候调用pop_back()和pop_front()会使程序崩掉。
9. assign()：

具体和vector中的操作类似，第一种：list1.assign(n,val)将 list1中元素变为n个T(val）。第二种:list1.assign(list1.begin(),list1.end())将list1中的从list1.begin()到list1.end()之间的数值赋值给list1。
10. swap()：交换两个链表(两个重载)，一个是list1.swap(list2); 另外一个是swap(list1,list2)，都可能完成连个链表的交换。
11. reverse()：通过reverse()完成list的逆置。
12. merge()：合并两个链表并使之默认升序(也可改)，list1.merge(list2，greater<int>()); 调用结束后list2变为空，list1中元素包含原来list1和list2中的元素，并且排好序，默认是升序，greater<int>()可以省略，另外greater<int>()是可以变的，也可以不按升序排列。

//list实例程序  
#include <iostream>     
#include <list>     
#include <numeric>     
#include <algorithm>     
using namespace std;

typedef list<int> LISTINT;
typedef list<int> LISTCHAR;

void main()
{
//用LISTINT创建一个名为listOne的list对象     
LISTINT listOne;
//声明i为迭代器     
LISTINT::iterator i;

cout << "------int------" << endl;
//从前面向listOne容器中添加数据     
listOne.push_front(2);
listOne.push_front(1);//push_front后操作的在前面

//从后面向listOne容器中添加数据     
listOne.push_back(4);
listOne.push_back(3); //push_back后操作的在后面

//从前向后显示listOne中的数据     
cout << "print listOne.begin() to listOne.end():" << endl;
for (i = listOne.begin(); i != listOne.end(); ++i)
cout << *i << " ";
cout << endl;

//从后向后显示listOne中的数据     
LISTINT::reverse_iterator ir;
cout << "print listOne.rbegin() to listOne.rend():" << endl;
for (ir = listOne.rbegin(); ir != listOne.rend(); ir++) {
cout << *ir << " ";
}
cout << endl;

//使用STL的accumulate(累加),头文件#include <numeric>     
int result = accumulate(listOne.begin(), listOne.end(), 0);
cout << "Sum of listOne is:" << result << endl;
cout << "------char------" << endl;

//用list容器处理字符型数据    
LISTCHAR listTwo;
LISTCHAR::iterator j;
listTwo.push_front('A');
listTwo.push_front('B');

listTwo.push_back('x');
listTwo.push_back('y');

//从前向后显示listTwo中的数据     
cout << "print listTwo.begin() to listTwo.end():" << endl;
for (j = listTwo.begin(); j != listTwo.end(); ++j)
cout << char(*j) << " ";
cout << endl;

//使用STL的max_element,求listTwo中的最大元素并显示,头文件#include <algorithm>       
j = max_element(listTwo.begin(), listTwo.end());
cout << "The maximum element in listTwo is: " << char(*j) << endl;
}

------------------deque----------------

队列deque简介：

双端队列deque 是一种优化了的、对序列两端元素进行添加和删除操作的基本序列容器。它允许较为快速地随机访问，但它不像vector 把所有的对象保存在一块连续的内存块，而是采用多个连续的存储块，并且在一个映射结构中保存对这些块及其顺序的跟踪。向deque 两端添加或删除元素的开销很小。它不需要重新分配空间，所以向末端增加元素比vector 更有效。
deque 是对vector 和list 优缺点的结合，它是处于两者之间的一种容器。

deque 的特点：

(1) 随机访问方便，即支持[ ] 操作符和vector.at() ，但性能没有vector 好；
(2) 可以在内部进行插入和删除操作，但性能不及list ；
(3) 可以在两端进行push 、pop ；

deque成员函数及实例用法:

1.创建一个新双向队列
deque();//创建一个空双向队列
deque( size_type size ); // 创建一个大小为size的双向队列
deque( size_type num, const TYPE &val ); //放置num个val的拷贝到队列中
deque( const deque &from ); // 从from创建一个内容一样的双向队列
deque( input_iterator start, input_iterator end ); //start和end指示的范围为双向队列赋值

2.Operators 比较和赋值双向队列
//可以使用[]操作符访问双向队列中单个的元素
3.assign() 设置双向队列的值
void assign( input_iterator start, input_iterator end);//start和end指示的范围为双向队列赋值
void assign( Size num, const TYPE &val ); //设置成num个val。
4.at() 返回指定的元素
reference at( size_type pos ); //返回一个引用，指向双向队列中位置pos上的元素
5.back() //返回最后一个元素
reference back();//返回一个引用，指向双向队列中最后一个元素
6.begin() //返回指向第一个元素的迭代器
iterator begin();//返回一个迭代器，指向双向队列的第一个元素
7.clear() //删除所有元素
8.empty() //返回真如果双向队列为空
9.end() //返回指向尾部的迭代器
10.erase() //删除一个元素
iterator erase( iterator pos ); //删除pos位置上的元素
iterator erase( iterator start, iterator end ); //删除start和end之间的所有元素
11.front() //返回第一个元素的引用
12.get_allocator() //返回双向队列的配置器
13.insert() //插入一个元素到双向队列中
iterator insert( iterator pos, size_type num, const TYPE &val ); //pos前插入num个val值
void insert( iterator pos, input_iterator start, input_iterator end ); //插入从start到end范围内的元素到pos前面
14.max_size() //返回双向队列能容纳的最大元素个数
15.pop_back() //删除尾部的元素
16.pop_front() //删除头部的元素
17.push_back() //在尾部加入一个元素
18.push_front() //在头部加入一个元素
19.rbegin() //返回指向尾部的逆向迭代器
20.rend() //返回指向头部的逆向迭代器
21.resize() //改变双向队列的大小
22.size() //返回双向队列中元素的个数
23.swap() //和另一个双向队列交换元素

//双向队列 deque 实例
#include <deque>  
#include <iostream>  
#include <algorithm>  
using namespace std;

int main()
{
deque<int> ideq(20); //Create a deque ideq with 20 elements of default value 0  
deque<int>::iterator pos;

//赋值 
int i;
for (i = 0; i < 20; ++i)
ideq[i] = i;

//输出 
cout<<"输出deque中数据:"<<endl;
for (i = 0; i < 20; ++i)
cout<<ideq[i]<<" ";
//在头尾加入新数据
ideq.push_back(100);
ideq.push_front(20);

//输出deque  
cout << endl << "在头尾加入新数据后显示:" << endl;
for (pos = ideq.begin(); pos != ideq.end(); pos++)
cout<<*pos<<" ";

//查找  
const int FINDNUMBER = 19;
cout << endl << "请查找 " <<FINDNUMBER;
cout << "，if find,print 'find it success'; else print 'find failed'：" << endl;

pos = find(ideq.begin(), ideq.end(), FINDNUMBER);
if (pos != ideq.end())
cout<<"find "<<FINDNUMBER<<" success"<<endl;
else
cout << "find " << FINDNUMBER << " failed" << endl;

//在头尾删除数据  
ideq.pop_back();
ideq.pop_front();
//输出deque  
cout<< "在头尾删除数据后显示:" << endl;
for (pos = ideq.begin(); pos != ideq.end(); pos++)
cout<<*pos<<" ";
return 0;
}

------------------三者比较-----------------

vector 是一段连续的内存块，而deque 是多个连续的内存块， list 是所有数据元素分开保存，可以是任何两个元素没有连续。
vector 的查询性能最好，并且在末端增加数据也很好，除非它重新申请内存段；适合高效地随机存储。
list 是一个链表，任何一个元素都可以是不连续的，但它都有两个指向上一元素和下一元素的指针。所以它对插入、删除元素性能是最好的，而查询性能非常差；适合大量地插入和删除操作而不关心随机存取的需求。
deque 是介于两者之间，它兼顾了数组和链表的优点，它是分块的链表和多个数组的联合。所以它有被list 好的查询性能，有被vector 好的插入、删除性能。如果你需要随即存取又关心两端数据的插入和删除，那么deque 是最佳之选。

参考：

http://blog.csdn.net/hancunai0017/article/details/7032383

http://blog.csdn.net/xfortius/article/details/7760490/

http://blog.csdn.net/lskyne/article/details/10418823

http://www.cppblog.com/wanghaiguang/archive/2012/06/04/177477.html

http://blog.csdn.net/morewindows/article/details/6946811

秒客网