一篇文章徹底搞懂C++常見容器

2023-02-14 06:00:13

1.概述

C++容器屬於STL（標準模板庫）中的一部分（六大元件之一），從字面意思理解，生活中的容器用來存放（容納）水或者食物，東西，而C++中的容器用來存放各種各樣的資料，不同的容器具有不同的特性，下圖（思維導圖）中列舉除了常見的幾種C++容器，而這部分C++的容器與python中的序列有很多相似之處，也許這也很好地印證了江湖上“C生萬物”的說法。因本人是學完python後才學C++的，突然有種：“山重水複疑無路，柳暗花明又一村”的感覺。因為python是偏向於頂層的語言，那時候什麼迭代器，生成器之類的東西都不是非常清楚，然後在C++中又遇到了類似內容，便有了更好的理解，也許這就是很多人不建議初學者學習python的原因吧。

2.容器詳解

2.1vector（向量）

從這個命名就可以很好地理解，線上性代數中，向量是一維的結構，而在容器中，向量也是看似一維的儲存形式。可以理解為長度可變的陣列。只不過在尾部增刪資料的時候效率最高，其他位置增刪資料則效率較低。舉個例子（開胃菜）：

#include <iostream> 
#include <vector> 
using namespace std;
// 程式的主函數
int main()
{
	vector<int> V;
	V.push_back(1);
	V.push_back(2);
	V.push_back(1);
	V.push_back(2);
	cout << V[0] << endl;
	system("pause");
	return 0;
}

列印輸出：1。

從上面的例子可以看出，向量和陣列的用法極其類似。當然，容器還有一個極其好用的功能，就是容器的巢狀使用。

#include <iostream> 
#include <vector> 
using namespace std;
// 程式的主函數
int main()
{
	vector<vector<int>> V;
	vector<int> sub_V;
	sub_V.push_back(1);
	sub_V.push_back(2);
	sub_V.push_back(1);
	V.push_back(sub_V);
	cout << V[0][1] << endl;
	system("pause");
	return 0;
}

列印輸出2這個時候的向量可以看作是一個二維陣列，當然比二維陣列更加靈活、強大。

當然向量容器還有其他更加豐富的操作。比如：

    int size = vec1.size();         //元素個數
    bool isEmpty = vec1.empty();    //判斷是否為空
    vec1.insert(vec1.end(),5,3);    //從vec1.back位置插入5個值為3的元素
    vec1.pop_back();              //刪除末尾元素
    vec1.erase(vec1.begin(),vec1.end());//刪除之間的元素，其他元素前移
    cout<<(vec1==vec2)?true:false;  //判斷是否相等==、！=、>=、<=...
    vector<int>::iterator iter = vec1.begin();    //獲取迭代器首地址
    vector<int>::const_iterator c_iter = vec1.begin();   //獲取const型別迭代器
    vec1.clear();                 //清空元素

舉個最常見的例子：

#include <iostream> 
#include <vector> 
using namespace std;
// 程式的主函數
int main()
{
	vector<int> V;
	V.push_back(1);
	V.push_back(2);
	V.push_back(3);
	for (vector<int>::iterator it = V.begin(); it != V.end(); it++)
		cout << *it << " ";
	cout << endl;
	cout << "==========================" << endl;
	V.insert(V.begin() + 2,10);
	for (vector<int>::iterator it = V.begin(); it != V.end(); it++)
		cout << *it << " ";
	system("pause");
	return 0;
}

注意如果不是在其尾部插入資料，要傳入插入位置的迭代器。

列印輸出：

2.2deque（雙端佇列）

deque，顧名思義，從前後兩端都可以進行資料的插入和刪除操作，同時支援資料的快速隨機存取。舉個例子：

#include <iostream> 
#include <deque> 
using namespace std;
// 程式的主函數
int main()
{
	deque<int> D;
	D.push_back(1);
	D.push_back(2);
	D.push_back(3);
	for (deque<int>::iterator it = D.begin(); it != D.end(); it++)
		cout << *it << " ";
	cout << endl;
	cout << "============在其索引2的位置插入10：" << endl;
	D.insert(D.begin() + 2,10);
	for (deque<int>::iterator it = D.begin(); it != D.end(); it++)
		cout << *it << " ";
	cout << endl;
	cout << "============在其頭部插入0：" << endl;
	D.push_front(0);
	for (deque<int>::iterator it = D.begin(); it != D.end(); it++)
		cout << *it << " ";
	cout << endl;
	cout << "============在其頭部彈出0：" << endl;
	D.pop_front();
	for (deque<int>::iterator it = D.begin(); it != D.end(); it++)
		cout << *it << " ";
	system("pause");
	return 0;
}

列印輸出：

2.3list（列表）

列表是用雙向連結串列實現的，所謂的雙向連結串列，指的是既可以從連結串列的頭部開始搜尋找到連結串列的尾部，也可以進行反向搜尋，從尾部到頭部。這使得list在任何位置插入和刪除元素都變得非常高效，但是隨機存取速度變得非常慢，因為儲存的地址是不連續的，所以list沒有過載[]運運算元，也就是說，存取list元素的時候，再也不像向量和雙端佇列那麼方便，不可以像我們以前在C語言的時候，存取陣列那樣對其元素進行存取。
一起來看個例子：

#include <iostream> 
#include <list> 
using namespace std;
// 程式的主函數
int main()
{
	//list的建立和初始化
	list<int> lst1;          //建立空list

	list<int> lst2(3);       //建立含有三個元素的list

	list<int> lst3(3, 2); //建立含有三個元素的值為2的list

	list<int> lst4(lst3);    //使用lst3初始化lst4

	list<int> lst5(lst3.begin(), lst3.end());  //同lst4
	cout << "lst4中的元素有：" << endl;
	for (list<int>::iterator it = lst4.begin(); it != lst4.end(); it++)
		cout << *it << " ";
	cout << endl;
	cout << "lst5中的元素有：" << endl;
	for (list<int>::iterator it = lst5.begin(); it != lst5.end(); it++)
		cout << *it << " ";
	cout << endl;
	system("pause");
	return 0;
}

執行，列印輸出：

然後再來看一個元素的新增，排序的例子。

#include <iostream> 
#include <list> 
#include <vector> 
using namespace std;
// 程式的主函數
int main()
{
	//list的建立和初始化
	list<int> lst1;          //建立空list

	for(int i = 0; i < 10; i++)
		lst1.push_back(9-i);                    //新增值
	cout << "lst1中的元素有：" << endl;
	for (list<int>::iterator it = lst1.begin(); it != lst1.end(); it++)
		cout << *it << " ";
	cout << endl;
	cout << "對lst1中的元素進行排序：" << endl;
	lst1.sort();
	for (list<int>::iterator it = lst1.begin(); it != lst1.end(); it++)
		cout << *it << " ";
	cout << endl;
	cout << "在索引為5的地方插入999：" << endl;
	list<int>::iterator insert_it = lst1.begin();
	for (int i = 0; i < 5; i++)
		insert_it++;
	lst1.insert(insert_it, 3, 999);
	for (list<int>::iterator it = lst1.begin(); it != lst1.end(); it++)
		cout << *it << " ";
	cout << endl;
	cout << "刪除相鄰重複元素後：" << endl;
	lst1.unique();                         //刪除相鄰重複元素
	for (list<int>::iterator it = lst1.begin(); it != lst1.end(); it++)
		cout << *it << " ";
	cout << endl;
	system("pause");
	return 0;
}

執行後，列印輸出：

特別注意，由於list的底層是雙向連結串列，因此insert操作無法直接像向量和雙端佇列一樣直接插入資料，只能通過迭代器的自加移動到相應位置，再插入資料。

2.4 array（陣列）

array和C語言中的陣列沒有太大的區別，建立後只能儲存一種型別的資料，且不能改變大小。比較簡單，舉個例子：

#include <iostream> 
#include <string>
#include <array>
using namespace std;
// 程式的主函數
int main()
{
	array<int, 4> arr = {1, 3, 2};
	cout << "arr values:" << std::endl;
	for (array<int, 4>::iterator it = arr.begin(); it != arr.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
	cout << "sizeof(arr) = " << sizeof(arr) << endl;
	cout << "size of arr = " << arr.size() << endl;
	cout << "max size arr = " << arr.max_size() << endl;
	cout << "empty = " << (arr.empty() ? "no" : "yes") << endl;
	system("pause");
	return 0;
}

當然，最常見的，array也支援巢狀，可以採用這樣的方式來構建二維（多維）陣列，由於比較簡單，就不舉例了。

2.5 string（字串）

與vector相似的容器。專門用於儲存字元。隨機存取快。尾部插入刪除快。在部分說法中，string不算是STL容器，但是為了內容的完整性，我們還是將其一併學習。

#include <iostream> 
#include <string>
using namespace std;
// 程式的主函數
int main()
{
	string s1 = "Bob:";
	string s2("hellow world!");
	for (int i = 0; i < s1.size(); i++)
	{
		cout << s1[i];
	}
	cout << endl;
	for (int i = 0; i < s2.size(); i++)
	{
		cout << s2[i];
	}
	cout << endl;

	cout << s1 + s2 << endl;
	s1.insert(s1.size(),"you say ");
	cout << s1 + s2 << endl;
	system("pause");
	return 0;
}

執行，列印輸出如下：

通過以上例子可以發現，與我們在C語言中學習的string並沒有多少區別，其實本身區別也不是很大，只是在建立了之後還可以新增元素（盲猜是新建立了一個同名的string，僅此而已），且新增元素的方式也很簡單，直接通過insert(插入位置，需要新增的字串)這樣的格式新增即可。上面一個例子是從末尾新增的，所以索引肯定是s1.size()。當然還有字串的相加，字串的比較等，都是屬於更為基礎的內容，沒有新增到例子當中去，感興趣的同學可以自己找資料去學習。

2.6 map（對映）

map容器和python中的字典非常類似，或者說一模一樣。都是通過鍵值對的方式來儲存和存取資料的，底層是通過紅黑樹來實現的。先來看個map的建立以及初始化的例子。

#include <iostream> 
#include <map> 
#include <string>
using namespace std;
// 程式的主函數
int main()
{
	//map的建立和初始化
	//第一種：用insert函數插入pair資料：
	map<int, string> my_map;
	my_map.insert(pair<int, string>(1, "first"));
	my_map.insert(pair<int, string>(2, "second"));
	//第二種：用insert函數插入value_type資料：
	my_map.insert(map<int, string>::value_type(3, "first"));
	my_map.insert(map<int, string>::value_type(4, "second"));
	//第三種：用陣列的方式直接賦值：
	my_map[5] = "first";
	my_map[6] = "second";
	map<int, string>::iterator it;           //迭代器遍歷
	for (it = my_map.begin(); it != my_map.end(); it++)
		cout << it->first << "->" <<it->second << endl;
	system("pause");
	return 0;
}

執行，列印輸出如下結果：

從以上結果可以看出，其中陣列直接賦值的方法最簡單直接，最容易理解。當然map儲存的是鍵值對，所以前面的int型別資料（key）並不代表其位置。比方說，我們將其中的int修改為float也是可以的。程式碼如下：

#include <iostream> 
#include <map> 
#include <string>
using namespace std;
// 程式的主函數
int main()
{
	//map的建立和初始化
	//第一種：用insert函數插入pair資料：
	map<float, string> my_map;
	my_map.insert(pair<float, string>(1, "first"));
	my_map.insert(pair<float, string>(2, "second"));
	//第二種：用insert函數插入value_type資料：
	my_map.insert(map<float, string>::value_type(3, "first"));
	my_map.insert(map<float, string>::value_type(4, "second"));
	//第三種：用陣列的方式直接賦值：
	my_map[5.3] = "first";
	my_map[6.6] = "second";
	map<float, string>::iterator it;           //迭代器遍歷
	for (it = my_map.begin(); it != my_map.end(); it++)
		cout << it->first << "->" <<it->second << endl;
	system("pause");
	return 0;
}

當然，同其他的容器型別一樣，map同樣支援巢狀，比如：

#include <iostream> 
#include <map> 
#include <string>
using namespace std;
// 程式的主函數
int main()
{
	//map的巢狀用法
	map<int,map<int,string>> my_map;
	my_map[1][1] = "張三";
	my_map[1][2] = "李四";
	my_map[1][3] = "王五";

	for (map<int, map<int, string>>::iterator it = my_map.begin(); it != my_map.end(); it++)
	{
		for (map<int, string>::iterator in_it = it->second.begin(); in_it != it->second.end(); in_it++)
		{
			cout << it->first << "年級" << in_it->first << "號同學：" << in_it->second << endl;
		}
	}
	cout << endl;	
	system("pause");
	return 0;
}

執行，列印輸出如下：

還有一個很重要的問題，就是map元素的刪除。map元素的刪除有好多種方法，下面僅僅列舉常見幾種。

#include <iostream>
#include <map>
#include <string>
using namespace std;

void printMap(const map<string, int>& students)
{
	for (auto ii = students.begin(); ii != students.end(); ii++)
	{
		cout << "姓名:" << ii->first
			<< " t詩作: " << ii->second << "篇"
			<< endl;
	}
	cout << endl;
}

int main(int argc, char* argv[]) {
	map<string, int> students;
	students["李白"] = 346;
	students["杜甫"] = 300;
	students["王維"] = 200;
	students["李商隱"] = 113;
	students["杜牧"] = 156;
	cout << "原map:" << endl;
	printMap(students);

	students.erase("李白");
	cout << "刪除 李白 後：" << endl;
	printMap(students);

	students.erase(std::begin(students));
	cout << "刪除第一個元素後：" << endl;
	printMap(students);

	map<string, int>::iterator iter = students.find("杜牧");
	students.erase(iter);
	cout << "刪除杜牧後：" << endl;
	printMap(students);
	system("pause");
	return 0;
}

執行後，列印輸出：

從上面的例子也可以看出，map中的鍵值對不一定是按照我們建立的順序儲存資料，map會按照key的值內部進行排序，但是保持其鍵值對的對應關係不變。

2.7 set（集合）

set也是一種關聯性容器，它同map一樣，底層使用紅黑樹實現，插入刪除操作時僅僅移動指標即可，不涉及記憶體的移動和拷貝，所以效率比較高。從中文名就可以明顯地看出，在set中不會存在重複的元素，若是儲存相同的元素，將直接視為無效，我們先來看個簡單的例子（關於set的建立和元素的新增等）：

#include <iostream> 
#include <set> 
#include <vector> 
using namespace std;
// 程式的主函數
int main()
{
	vector<int> ivec;
	for (vector<int>::size_type i = 0; i != 10; i++) {
		ivec.push_back(i);
		ivec.push_back(i);
	}
	set<int> iset(ivec.begin(), ivec.end());
	cout << "向量中的元素為：" << endl;
	for (vector<int>::iterator it = ivec.begin(); it != ivec.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
	cout << "集合中的元素為：" << endl;
	for (set<int>::iterator it = iset.begin(); it != iset.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
	cout << "向量的大小為：" << endl;
	cout << ivec.size() << endl;
	cout << "集合的大小為：" << endl;
	cout << iset.size() << endl; 

	system("pause");
	return 0;
}

列印輸出：

上面例子的方法，相當於直接將向量的值賦給了集合，從而順便建立了集合，那麼如果想通過逐一賦值的方式建立集合，又該如何編寫程式碼呢？如何清除集合中的元素呢？以及是否知道某元素在集合中呢？同樣我們通過一段程式碼來看一下。

#include <iostream> 
#include <set> 
#include <vector> 
#include <string>
using namespace std;
// 程式的主函數
int main()
{
	set<string> set1;
	set1.insert("the"); 

	//刪除集合
	while (!set1.empty())
	{
		//獲取頭部
		set<string>::iterator it = set1.begin();
		//列印頭部元素
		cout << *it << endl;

		//從頭部刪除元素
		set1.erase(set1.begin());
	}
	set<int>set2;
	for (int i = 100; i < 110; i++)
		set2.insert(i);
	cout << "set2中5出現的次數為：";
	cout << set2.count(5) << endl;
	set2.clear();
	cout << "set2清除之後的大小為：";
	cout << set2.size() << endl;
	system("pause");
	return 0;
}

執行，列印輸出：