顺序容器 vector介绍

vector是C++STL库中表示数组大小可以改变的序列容器，使用连续的存储位置来存储元素，这意味着也可以使用只想元素的常规指针上的偏移量来访问元素（eg：a[i])，与数组不同的是，vector的大小可以动态变化，存储用容器来自动处理。

vector(向量): C++中的一种数据结构,确切的说是一个类.它相当于一个动态的数组,当程序员无法知道自己需要的数组的规模多大时,用其来解决问题可以达到最大节约空间的目的.

在内部，vector使用动态分配的数组来存储它们的元素。这个数组可能需要重新分配，以便在插入新元素时增大大小，这意味着分配一个新数组并将所有元素移到该数组中。就处理时间而言，这是一项相对昂贵的任务，因此，vector不会在每次将元素添加到容器时重新分配。

相反，vector可以分配一些额外的存储以适应可能的增长，因此该容器的实际容量可能大于严格需要容纳其元素的存储容量（即其大小）。库可以实现不同的增长策略，以平衡内存使用和重新分配，但在任何情况下，重新分配只能以大小的对数增长间隔进行，以便在向量末尾插入单个元素时可以提供分摊的恒定时间复杂度。

因此，与阵列相比，向量消耗更多的内存，以换取高效地管理存储和动态增长的能力。

与其他动态序列容器（deques、list和forward\ u list）相比，vector非常有效地访问其元素（就像数组一样），并且相对有效地从其末端添加或删除元素。对于涉及在末端以外的位置插入或删除元素的操作，它们的性能比其他的容器差。

vector使用

使用vector，需在头文件中定义

#include <vector>
using namespace std; // vector属于std命名空间

vector初始化

vector<int> vec; 
vector<int> vec(n); //大小为n的vector
vector<int> vec(n, x);  // x个n
vector<int> b(vec); // 开一个vector名字为b的数组，并把vec的值复制给b
vector<int> b(vec.begin(), vec.end()); // 开一个vector名字为b的数组，并把vec的值复制给b
vector<int> b(&vec[0], &vec[1]);   // 开一个vector名字为b的数组，并把vec[0], vec[1],的值复制给b

vector成员函数

a[i];  //直接访问a中第i个元素
a.at(i);  // 得到编号位置的数据，直接访问a中第i个元素
a.empty();  //判断是否为空，是则返回true，否则返回false
a.size();  //返回a中的所存储元素的数量
a.push_back(x);  //将x压入a的末尾
a.pop_back();  //将a的末尾元素出栈(返回值为void类型)
a.front();  //返回第一个元素, 得到数组头的引用
a.back(); //  得到数组的最后一个单元的引用
a.clear();  //清除a中所有的元素
a.insert(it,x);  //在it前添加x
a.insert(it,n,x);  //在it前添加n个x
a.max_size();  //返回vector的最大容量
a.capacity();  //返回a所能容纳的最大元素值
a.erase(it);  //删除it这个迭代器所指向的值
a.erase(first,last);  //删除从[first，last)的值
a.resize(n);  //改变长度，超过的话则删除多余部分，少的话则增添默认值
a.resize(n,x);  //同上，默认值改为x
a.clear();  //删除所有的元素
a.assign(first,last);  //a中替换first，last，first到last这个区间的值不能为a
a.begin(); //  得到数组头的指针
a.end(); //  得到数组的最后一个单元+1的指针
a.rbegin(); // 将vector反转后的开始指针返回(其实就是原来的end-1)
a.rend(); // 将vector反转构的结束指针返回(其实就是原来的begin-1)
a.swap(); //与另一个vector交换数据

vector的迭代器

vector<int>::iterator it1;  //正向迭代器
vector<int>::reverse_iterator it2;  //反向迭代器
a.begin();  a.end();  //正向迭代器所用
a.rbegin();  a.rend();  //反向迭代器所用，rbegin()相当于end()-1,rend()相当于begin()+1
reverse(a.begin(),a.end());  //将a翻转
sort(a.begin(),a.end(),cmp);  //排序，cmp处可以不写，默认为正向,也可以自己写排序的函数，默认有less<int>()和greater<int>()

vector查找指定元素并删除

查找时可以使用find函数，此时必须将algorithm头文件包含进去。
查找完成后，如果vector中包含该元素，则返回第一个元素，或者超出末端的下一个位置，返回的是迭代器。
删除元素之前，必须确保返回的不是end迭代器。

#include <iostream>  
#include <vector>  
#include <algorithm>  
 
using namespace std;  
 
void print(vector<int> v){  
    vector<int>::iterator iter=v.begin();  
    while(iter!=v.end())  
        cout<<*iter++<<" ";  
    cout<<endl;  
}  
 
int main(int argc,char** argv){  
    int arr[]={1,2,3,4,5,6,7,8,9};  
 
    //vector初始化  
    vector<int> v(arr,arr+sizeof(arr)/sizeof(*arr));  
    print(v);  
 
    //在vector中查找指定元素  
    vector<int>::iterator iter=find(v.begin(),v.end(),5);  
 
    //删除指定元素  
    if(iter!=v.end())v.erase(iter);  
 
    print(v);  
 
    return 0;  
}  

在vector中查找元素及其位置

#include <iostream>  
#include <vector>  
#include <algorithm>  
 
using namespace std;  
int _tmain()  
{  
     vector <int> vecIntegerArray;  
     vecIntegerArray.push_back(50);  
     vecIntegerArray.push_back(222);  
     vecIntegerArray.push_back(3);  
     vecIntegerArray.push_back(44);  
 
     cout<< "the contents of the vector are: " << endl;  
     vector <int>::iterator iArrayWalker = vecIntegerArray.begin();  
     while(iArrayWalker != vecIntegerArray.end())  
     {     
          cout << *iArrayWalker << endl;  
          iArrayWalker++;  
     }  
     vector <int>::iterator iElement = find(vecIntegerArray.begin(),  
                           vecIntegerArray.end(),3);  
     if( iElement != vecIntegerArray.end() )  
     {  
          int nPosition = distance(vecIntegerArray.begin(),iElement);  
          cout << "Value  "<< *iElement;  
          cout <<"  find in the vector at position: " <<nPosition + 1 <<endl;  
     }  
     getchar();  
     return 0 ;  
}  

C++ Vector 最大 最小值 索引 位置

使用STL的Vector时，利用函数 max_element，min_element，distance可以获取Vector中最大、最小值的值和位置索引：
参考：http://stackoverflow.com/questions/2953491/finding-the-position-of-the-max-element

#include <vector>  
#include <algorithm>  
#include <iostream>  
 
int main()  
{  
    std::vector<double> v {1.0, 2.0, 3.0, 4.0, 5.0, 1.0, 2.0, 3.0, 4.0, 5.0};  
 
    std::vector<double>::iterator biggest = std::max_element(std::begin(v), std::end(v));  
    std::cout << "Max element is " << *biggest<< " at position " << std::distance(std::begin(v), biggest) << std::endl;  
 
    auto smallest = std::min_element(std::begin(v), std::end(v));  
    std::cout << "min element is " << *smallest<< " at position " << std::distance(std::begin(v), smallest) << std::endl;  
}  
 
 
输出：  
 
Max element is 5 at position 4  
min element is 1 at position 0  

#include <vector>  
#include <algorithm>  
class student  
{  
    int NO;  
    AnsiString strName;  
    int grade;  
    public:  
    student(int NO,AnsiString strName,int grade)  
    {  
       this->NO = NO;  
       this->strName = strName;  
       this->grade   = grade;  
    }  
    bool operator==(AnsiString strName)  
    {  
       return this->strName == strName;  
    }  
};  

上面这个类，在STL中叫函数对象，重载运算符==，当执行Count函数时，会比较[v.begin,v.end]中的各
student对象是否与“张三”相等

void __fastcall TForm1::Button11Click(TObject *Sender)  
{  
    vector<student> v;  
    student s1(1000,AnsiString("张三"),90);  
    student s2(1001,AnsiString("张三"),91);  
    student s3(1002,AnsiString("王五"),90);  
    student s4(1003,AnsiString("赵六"),90);  
    v.push_back(s1);  
    v.push_back(s2);  
    v.push_back(s3);  
    v.push_back(s4);  
    int nCount = count(v.begin(),v.end(),"张三");  
    ShowMessage(nCount);  
 
}  

二维vector数组

vector<vector<int> > a;  //初始化二维数组
vector<vector<int> > a(10,vector<int> (10,0));  //创建一个10行10列的数组

对二维数组进行赋值，用push_back去压入一维vector

vector<vector<int> > a;
for(int i=0;i<10;i++)
{
	vector<int> b;
	for(int j=0;j<10;j++)
	{
		int t;
		cin>>t;
		b.push_back(t);
	}
	a.push_back(b);  //将b压入a中
}

如果想获得a中i行j列的值

cout  << a[i][j];

如果想获得i行的值

cout  <<  a[i]； // 代表一维的vector

vector的元素-结构体

vector的元素不仅仅可以使int,double,string,还可以是结构体，但是要注意：结构体要定义为全局的，否则会出错。下面是一段简短的程序代码：

#include<stdio.h>
#include<algorithm>
#include<vector>
#include<iostream>
using namespace std;

typedef struct rect
{
    int id;
    int length;
    int width;

　　//对于向量元素是结构体的，可在结构体内部定义比较函数，下面按照id,length,width升序排序。
　　bool operator< (const rect &a)  const
    {
        if(id!=a.id)
            return id<a.id;
        else
        {
            if(length!=a.length)
                return length<a.length;
            else
                return width<a.width;
        }
    }
}Rect;

int main()
{
    vector<Rect> vec;
    Rect rect;
    rect.id=1;
    rect.length=2;
    rect.width=3;
    vec.push_back(rect);
    vector<Rect>::iterator it=vec.begin();
    cout<<(*it).id<<' '<<(*it).length<<' '<<(*it).width<<endl;    

return 0;

}

算法

(1) 使用reverse将元素翻转：需要头文件#include

reverse(vec.begin(),vec.end());将元素翻转(在vector中，如果一个函数中需要两个迭代器，一般后一个都不包含.)

(2)使用sort排序：需要头文件#include，

sort(vec.begin(),vec.end());(默认是按升序排列,即从小到大).可以通过重写排序比较函数按照降序比较，如下：

定义排序比较函数：

bool Comp(const int &a,const int &b)
{
return a>b;
}
调用时:sort(vec.begin(),vec.end(),Comp)，这样就降序排序。

顺序容器 List

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

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中重复的元素
非连续存储结构，具有双链表结构，每个元素维护一对前向和后向指针，因此支持前向/后向遍历。 支持高效的随机插入/删除操作，但随机访问效率低下，且由于需要额外维护指针 ，开销也比较大。每一个结点都包括一个信息快Info、一个前驱指针Pre、一个后驱指针Post。可以不分配必须的内存大小方便的进行添加和删除操作。使用的是非连续的内存空间进行存储。
优点：(1) 不使用连续内存完成动态操作。
(2) 在内部方便的进行插入和删除操作
(3) 可在两端进行push、pop
缺点：(1) 不能进行内部的随机访问，即不支持[ ]操作符和vector.at()
(2) 相对于verctor占用内存多
使用区别：
（1）如果你需要高效的随即存取，而不在乎插入和删除的效率，使用vector
（2）如果你需要大量的插入和删除，而不关心随机存取，则应使用list
（3）如果你需要随机存取，而且关心两端数据的插入和删除，则应使用deque

deque

连续存储结构，即其每个元素在内存上也是连续的，类似于vector，不同之处在于， deque提供了两级数组结构， 第一级完全类似于vector，代表实际容器；另一级维护容器的首位地址。这样，deque除了具有vector的所有功能外， 还支持高效的首/尾端插入/删除操作。
deque 双端队列 double-end queue
deque是在功能上合并了vector和list。
优点：(1) 随机访问方便，即支持[ ]操作符和vector.at()
(2) 在内部方便的进行插入和删除操作
(3) 可在两端进行push、pop
缺点：占用内存多
使用区别：
（1）如果你需要高效的随即存取，而不在乎插入和删除的效率，使用vector
（2）如果你需要大量的插入和删除，而不关心随机存取，则应使用list
（3）如果你需要随机存取，而且关心两端数据的插入和删除，则应使用deque

push_back(); //在队列末尾增加一个元素， 参数为拷贝或移动的元素
push_front(); //在队列头部增加一个元素，参数可以是拷贝或移动的元素
emplace(); //在队列指定的元素位置前插入新的元素
emplace_back(); //在队列尾部增加新的元素
emplace_front();// 在队列头部增加新的元素
insert(); //在队列莫一元素前增加新的元素

对比

vector VS. list VS. deque：
a、若需要随机访问操作，则选择vector；
b、若已经知道需要存储元素的数目，则选择vector；
c、若需要随机插入/删除（不仅仅在两端），则选择list
d、只有需要在首端进行插入/删除操作的时候，还要兼顾随机访问效率，才选择deque，否则都选择vector。
e、若既需要随机插入/删除，又需要随机访问，则需要在vector与list间做个折中-deque。
f、当要存储的是大型负责类对象时，list要优于vector；当然这时候也可以用vector来存储指向对象的指针，
同样会取得较高的效率，但是指针的维护非常容易出错，因此不推荐使用。

list和vector的区别

（1）vector为存储的对象分配一块连续的地址空间 ，随机访问效率很高。但是 插入和删除需要移动大量的数据，效率较低。尤其当vector中存储
的对象较大，或者构造函数复杂，则在对现有的元素进行拷贝的时候会执行拷贝构造函数。
（2）list中的对象是离散的，随机访问需要遍历整个链表， 访问效率比vector低。但是在list中插入元素，尤其在首尾 插入，效率很高，只需要改变元素的指针。
（3）vector是单向的，而list是双向的；

（4）向量中的iterator在使用后就释放了，但是链表list不同，它的迭代器在使用后还可以继续用；链表特有的；

使用原则：
（1）如果需要高效的随机存取，而不在乎插入和删除的效率，使用vector；
（2）如果需要大量高效的删除插入，而不在乎存取时间，则使用list；
（3）如果需要搞笑的随机存取，还要大量的首尾的插入删除则建议使用deque，它是list和vector的折中；

常量容器const

const vector vec(10);//这个容器里 capacity和size和值都是不能改变的， const修饰的是vector；
迭代器：const vector::const_iterrator ite; //常量迭代器；
注：const vector vec(10) —— 与const int a[10]是一回事，意思是vec只有10个元素，不能增加了，里面的元素也是不能变化的

vector<int> a(10);
const vector<int> b(10);
a[1]=10;//正确
b[1]=10;//错误
a.resize(20);//正确
b.resize(20);//错误

vector <const int> vec(10);  //目前没有这种用法;这样写后也是当作vector <int>vec来用的；
关于vector<const int> ，在GCC下是没有这种用法的,编译不过
在VS2008是把它当作vector<int>这种类型来处理的；

capacity V.S size

a、capacity是容器需要增长之前，能够盛的元素总数； 只有连续存储的容器才有capacity的概念（例如vector，deque，string），list不需要capacity。
b、size是容器当前存储的元素的数目。
c、vector默认的容量初始值，以及增长规则是依赖于编译器的。

迭代器iterator

a、vector与deque的迭代器支持算术运算，list的迭代器只能进行++/–操作，不支持普通的算术运算。
b .向量中的iterator在使用后就释放了，但是链表list不同，它的迭代器在使用后还可以继续用；链表特有的；

     ite=find(vec.begin(),vec.end(),88);
     vec.insert(ite,2,77);  //迭代器标记的位置前，插入数据；
     cout<<*ite<<endl;  //会崩溃，因为迭代器在使用后就释放了，*ite的时候就找不到它的地址了；

参考
C++知识碎片整理（9）——Vector&List
C++ vector常用方法总结 个人整理
c++ vector使用 最全整理
C++11 deque用法总结（整理）