STL

STL之vector

Posted by Liao on 2020-03-05

一、vector的特性

  • vector封装了数组，拥有连续的内存空间，并且起始地址不变，能够高效地进行存取，时间复杂度为O(1)
  • 但由于其内存空间是连续的，在进行插入或删除操作时，会造成内存块拷贝，时间复杂度为O(n)；另外，在数组内存空间不够时，也会重新申请一块内存空间进行内存拷贝。

（与list数据结构相反，用于不同的场景）

二、初始化

1
2
3
4
5
vector<int>vec(int size);  //创建一个大小size,初始值为0的容器

vector<int> vec(int size, int val);  //创建一个大小为size，且值均为val的容器

vector<vector<int>> vec(int row, vector<int>(int size, int val)) //行数，一维数组的初始化
1
2
nums: [-1,-3,2,4]; 
vector<int>dp(nums); // dp[i]每一个元素和nums一样

三、vector的二维数组

二维数组可表示成vecotr<vector<int>>vec

3.1 初始化
1
memset(vec,-1,sizeof(vec));  //把二维数组初始化为-1
1
2
3
4
5
6
// 先定义 再初始化
vector<vector<bool>>visited; // 全局定义

void test() {
  visited = vector(n, vector<bool>(m));
}
3.2 行列的表示

​ 行表示：vec.size()

​ 列表示：vec[0].size()

曾做过DFS遍历二叉树的题目，有一处利用vector二维数组很巧妙

vec[level].push_back(root->val) 在第n层插入对应根的值

3.3 二维数组排序
1
2
3
4
int n = grid.size();
for(int i = 0; i < n; i++) {
   sort(grid[i].begin(), grid[i].end());
}

四、常用的操作

1
2
3
4
5
6
7
8
9
10
11
12
13
reverse(vec.begin(),vec.end())　//翻转数组

sort(vec.begin(),vec.end())　//升序排序数组

vec.insert(vec.begin(), val);  //插入到vector数组的前面

vec.push_back(11);

vec.pop_back();//删除最后一个元素

vec.front(); //取第一个元素

vec.back(); //取最后一个元素

五、常用库函数

1
2
*max_element(vec.begin(), vec.end()); // 返回vector中最大的元素
accumulate(vec.begin(), vec.end(), 0); // 统计vector元素的总和
FEATURED TAGS
STL
FRIENDS