数据结构详解之向量vector_vector数据结构

1. vector简介

vector 实现了一个动态数组，是可实现自动增长的对象数组；
vector是一种顺序容器，支持随机访问；
vector和数组不同之处在于：数组是静态分配空间，一旦分配了空间的大小，就不可再改变了；而vector是动态分配空间，随着元素的不断插入，它会按照自身的一套机制不断扩充自身的容量。

2. vector用法

头文件：

#include<vector>//vector的头文件
1

声明方法：

//定义一维数组
vector<int> vec;//创建一个空的vector
vector<int> vec1(vec);//创建一个vector vec1,并用vec去初始化vec1
vector<int> vec2(n);//创建一个含有n个数据的vector
vector<int> vec3(10,0);//创建含有10个数据的vector，并全初始化为0
//定义m*n的二维数组
vector<vector<int> > array(m); //这个m一定不能少，m行
for(int i=0;i<m;i++) //n列
{
    array[i].resize(n);
}
for(i = 0; i < array.size(); i++)//遍历赋值
{
 　　for (j = 0; j < array[0].size();j++) 
    { 　　
        array[i][j] = (i+1)*(j+1); 
    } 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

定义特殊存储类型的vector

#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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

相关函数：

vec.push_back(a);//尾部插入数字
vec.pop_back(); //尾部删除数字
cout<<vec[0]<<endl;//使用下标访问
vec.size();//获得向量当前元素个数
vec.max_size();//获得向量最大容纳量
vec.clear();//清空向量
vec.empty();//判断向量是否为空（如果为空，返回1；否则返回0）
//使用迭代器访问元素
//begin(),end(),指向头元素、尾元素的指针
vector<int>::iterator it;//定义迭代器
for(it=vec.begin();it!=vec.end();it++)
    cout<<*it<<endl;
vec.insert(vec.begin()+i,a);//在第i+1个元素前面插入a;
vec.erase(vec.begin()+2);//删除第3个元素
//获取二维数组的长度
int size_row = vec.size(); //获取行数
int size_col = vec[0].size(); //获取列数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

相关算法：

#include<algorithm>//算法头文件
reverse(vec.begin(),vec.end());//逆序翻转元素
sort(vec.begin(),vec.end());//默认是按升序排列,即从小到大
//自定义排序比较函数：按照降序比较
bool Comp(const int &a,const int &b)
{
    return a>b;
}
sort(vec.begin(),vec.end(),Comp);//实现降序排序
1
2
3
4
5
6
7
8
9