C++ 之 Vector 和 List

Vector

---

vector 是C++ STL中最常用的容器，支持存储多种类型的数据。

与数组相比，它的大小是可变的，因此也会被称为动态数组。

使用连续的存储空间，访问速度快，但插入删除慢。

使用它，需要包含头文件：

#include 
1

定义的结构： vector<数据类型> 变量名

#include 

vector<int> v1;
vector<double> v2;
vector<string> v3;
vector<int> v4[5];      // 相当于二维数组
vector<double> v5[5]; 
1
2
3
4
5
6
7

它的常用函数：

• begin() 返回头部迭代器
• end() 返回尾部+1迭代器
• rbegin() 返回逆头部迭代器
• rend() 返回逆尾部-1迭代器
• size() 返回容器中元素个数大小
• resize() 改变容器大小,不会改变预分配的容器大小
• capacity() 获取预分配的容量大小
• resrve 获取于分配的空间
• front() 返回第一个元素
• back() 返回最后一个元素
• push_back()/emplace_back() 在容器末尾插入一个元素
• pop_back() 删除最后一个元素
• empty() 检测容器是否为空
• insert 在指定位置插入元素
• erase 在指定位置删除元素
• clear 清空容器所有元素

注意size和capacity：

size对应的是容器的真实大小，对应的方法是

capactiy对应的是容器预分配的容量大小，对应的方法是reserve

#include 
#include 
using namespace std;

int main() {
  vector<int> vec;
  // 初始化的时候容器没有对象，也就没有预留内存空间
  // vec.size() =0 vec.capacity() =0

  // 预留了空间，但容器没有对象，所以真实空间大小为0
  vec.reserve(10);
  // vec.size() =0 vec.capacity() =10

   // 插入一个元素，真实大小改变
   vec.push_back(1);
   //vec.size() =1 vec.capacity() =10

  // 修改了容器空间的真实大小
  vec.resize(10);
  // vec.size() =10 vec.capacity() =10

  // 末尾插入数据，容器的空间进行了扩展
  vec.push_back(9);
  // vec.size() =11 vec.capacity() =20
  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

基本使用：

#include 
#include 
using namespace std;

int main() {
  // 插入数据
  vector<int> vec;
  for(int i = 0; i < 4; ++i) {
    vec.push_back(i);
  }
  cout << "迭代器遍历" << endl;
  for(vector<int>::iterator iter = vec.begin(); iter != vec.end(); iter++) {
    cout << *iter << endl;
  }
  cout << "下标遍历" << endl;
  for(int i = 0; i < vec.size(); ++i) {
    cout << vec[i] << endl;
  }
  cout << "foreach遍历，不支持逆序" << endl;
  for(int value:vec) {
    cout << value << 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

List

底层为双向链表，内容空间不连续，只能通过指针访问。插入删除数据快，但是随机访问速度慢。

多适用于对数据进行频繁插入和删除的环境中。

list的iterator是不支持+、- 、< 等操作的， 但支持使用sort对元素排序

#include 
#include 

using namespace std;

int main() {
	std::list<int> myList;
	// 插入元素
	for(int i = 0; i < 10; ++i) {
		if (i < 5) {
			// 列表末尾插入元素
			myList.push_back(i);
		} 
		else {
			// 列表前端插入元素
			myList.push_front(i);
		}
	}
	// 排序元素, 默认从小到大
	myList.sort();
	// 对元素进行反序
	myList.reverse();
	// 遍历元素
	for(list<int>::iterator iter = myList.begin(); iter != myList.end(); ++iter) {
		cout << *iter << 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

vector和list相比较：vector随机访问快，但是插入删除慢，list反之

比较

---

vector的优点：

1. 使用连续的存储空间，访问速度快
2. 支持随机访问，通过[]和at方法访问数据，推荐后者，可避免越界问题
3. 可以拓展容器大小
4. 可以快速的在尾部插入和删除，及通过push_back和pop_back方法

vector的缺点：

1. 内部插入删除操作效率低，不如列表好用
2. 针对于数据只能在尾部进行push或pop
3. 添加数据超过预先分配大小，拓展容器大小会为原来的两倍，然后再拷贝数据

关于vector、array、数组相关

1. 数组是不安全的，访问时容易越界； vector和array可以通过at避免越界的问题
2. vector属于可变容器，但array和数组属于定长容器
3. 数组获取大小需要通过sizeof()/strlen()来遍历计数获取大小，但vector和array可通过size()和Empty()来获取大小和是否为空
4. 数组交换元素只能通过遍历的方式逐个交换，但vector和array通过swap()即可
5. vector的数据存储在堆中，array的数据存储在栈中