C++之vector/list/array区别(一百一十九)

一、vector、list、array容器区别

1.vector数据结构
vector用数组实现，拥有一段连续的内存空间，并且起始地址不变。
因此能高效的进行访问，时间复杂度为o(1)，因为使用下标访问;
但因为内存空间是连续的，所以在进行插入和删除操作时，会造成内存块的拷贝，时间复杂度为o(n)。
另外，当数组中内存空间不够时，会重新申请一块内存空间并进行内存拷贝。

2.list数据结构
list是由双向链表实现的，因此内存空间是不连续的。
只能通过指针访问数据，所以list的随机访问效率不高，时间复杂度为o(n);
但由于链表的特点，能高效地进行插入和删除。

3.array数据结构

元素在栈上分配内存，大小固定不变，内存连续，可随机存取。和vector相比是对静态数组的封装，使用下标访问元素数据。array不可以动态插入,因为第一次分配空间就固定了，使用时：注意数组越界操作问题.

4.使用区别：
<1>.如果你需要高效的随即存取，而不在乎插入和删除的效率，使用vector 
<2>.如果你需要大量的插入和删除，而不关心随即存取，则应使用list 
<3>.如果你需要随即存取，而且关心两端数据的插入和删除，则应使用deque

5.内部实现：
<1>.vector: 内部实现是数组，一段连续的内存。
<2>.list： 内部实现是双链表
<3>.deque：内部实现是内存块的链表。
<4>.string： 连续的内存
<5>.set，map： 红黑树(平衡二叉树的一种,有序)
<6>.unordered_map, unordered_set：用哈希表(散列表)来实现。
<7>.stack: 用vector或者是deque来实现
<8>.queue：用deque实现

一、vector、list、array用法

1.vector demo

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

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

	for(auto i:vec)
		cout << i << " ";

	cout << endl;
	
	// while(vec.empty() != true){
	// 	int i = vec.back();
	// 	cout << i << " ";
	// 	vec.pop_back();
	// }

	for(int i = 0; i < vec.size(); i++){
		cout << vec.at(i) << " ";
	}
	
  return 0;
}

2.list demo

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

int main (){
  list<int> ll;
	for(int i = 0; i < 10; i++)
		ll.push_back(i);

	for(auto i:ll)
		cout << i << " ";

	cout << endl;
	
	// while(ll.empty() != true){
	// 	int i = ll.back();
	// 	cout << i << " ";
	// 	ll.pop_back();
	// }

	for(list<int>::iterator it = ll.begin(); it != ll.end(); it++){
		cout << *it << " ";
	}
	
  return 0;
}

3.array demo

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

int main (){
  array<int,10> arr = {};
	cout << "len = " << arr.size() << endl;
	//1.push data
	for(int i = 0; i < arr.size(); i++)
		arr.at(i) = i;

	//2.
	for(auto i:arr)
		cout << i << " ";
	
	cout << endl;
	//3.
	for(auto it = arr.begin(); it != arr.end(); it++)
		cout << *it << " ";
	cout << endl;
	
	//4.	
	for(array<int,arr.size()>::iterator it = arr.begin(); it != arr.end(); it++){
		cout << *it << " ";
	}
	cout << endl;


	//5.
	array<int, 4> arr1 = { 1, 3, 2, 4 };	
	for(auto it = arr1.begin(); it != arr1.end(); it++)
		cout << *it << " ";
	cout << endl;
	
  return 0;
}