list

列表（list）是C++ STL中的一種容器類型，它是一個(gè)雙向鏈表，可以在任意位置高效地添加、刪除、移動(dòng)元素。

以下是一些常用的列表操作：

1. 創(chuàng)建列表

#include <list>
std::list<int> myList;

2. 添加元素

myList.push_back(1); // 在列表尾部添加元素
myList.push_front(2); // 在列表頭部添加元素
myList.insert(myList.begin(), 3); // 在指定位置插入元素

3. 刪除元素

myList.pop_back(); // 刪除尾部元素
myList.pop_front(); // 刪除頭部元素
myList.erase(myList.begin()); // 刪除指定位置的元素

4. 遍歷列表

std::list<int>::iterator it;
for(it=myList.begin(); it!=myList.end(); ++it) {std::cout << *it << ' ';
}

5. 獲取列表大小

std::cout << myList.size() << std::endl;

6. 判斷列表是否為空

if(myList.empty()) {std::cout << "List is empty" << std::endl;
}

7. 清空列表

myList.clear();

8. 列表排序

myList.sort(); // 默認(rèn)從小到大排序
myList.sort(std::greater<int>()); // 從大到小排序

9. 反轉(zhuǎn)列表

myList.reverse();

以上是一些常用的列表操作，更多操作可以參考C++ STL中l(wèi)ist的文檔。

vector

C++中的vector是STL（標(biāo)準(zhǔn)模板庫）中的容器之一，用于存儲(chǔ)動(dòng)態(tài)大小的元素序列。

以下是vector的常見操作：

1. 創(chuàng)建一個(gè)空的vector：

   vector<int> vec; // 創(chuàng)建一個(gè)空的vector<int>vector<string> strVec; // 創(chuàng)建一個(gè)空的vector<string>

2. 在vector末尾添加元素：

   vec.push_back(1); // 在vector末尾添加一個(gè)int類型元素1strVec.push_back("hello"); // 在vector末尾添加一個(gè)string類型元素"hello"

3. 訪問vector中的元素：

   int firstElem = vec[0]; // 訪問第一個(gè)元素string lastElem = strVec.back(); // 訪問最后一個(gè)元素

4. 獲取vector的大小：

   int size = vec.size(); // 獲取vector中元素的個(gè)數(shù)bool isEmpty = strVec.empty(); // 判斷vector是否為空

5. 刪除vector中的元素：

   vec.pop_back(); // 刪除vector末尾的一個(gè)元素strVec.erase(strVec.begin() + 2); // 刪除vector中索引為2的元素

6. 清空vector中所有元素：

   vec.clear(); // 清空vector中所有元素strVec.resize(0); // 將vector的大小設(shè)置為0

7. 遍歷vector中的所有元素：

   for (int i = 0; i < vec.size(); i++) {cout << vec[i] << " ";}for (auto s : strVec) {cout << s << " ";}

第二種方法可以使用C++11中的range-based for循環(huán)。

map

C++中的map是STL（標(biāo)準(zhǔn)模板庫）中的關(guān)聯(lián)容器之一，用于存儲(chǔ)鍵值對(duì)。

以下是map的常見操作：

1. 創(chuàng)建一個(gè)空的map：

   map<string, int> myMap; // 創(chuàng)建一個(gè)空的map，鍵為string類型，值為int類型

2. 在map中插入鍵值對(duì)：

   myMap.insert(make_pair("apple", 10)); // 在map中插入鍵為"apple"，值為10的鍵值對(duì)myMap["banana"] = 20; // 在map中插入鍵為"banana"，值為20的鍵值對(duì)

3. 訪問map中的元素或查找鍵：

   int value = myMap["apple"]; // 訪問鍵為"apple"的值auto it = myMap.find("banana"); // 查找鍵為"banana"的迭代器if (it != myMap.end()) {int value = it->second; // 獲取迭代器指向的值}

4. 獲取map的大小：

   int size = myMap.size(); // 獲取map中鍵值對(duì)的個(gè)數(shù)bool isEmpty = myMap.empty(); // 判斷map是否為空

5. 刪除map中的鍵值對(duì)：

   myMap.erase("apple"); // 刪除鍵為"apple"的鍵值對(duì)auto it = myMap.find("banana");if (it != myMap.end()) {myMap.erase(it); // 刪除迭代器指向的鍵值對(duì)}

6. 清空map中的所有鍵值對(duì)：

   myMap.clear(); // 清空map中的所有鍵值對(duì)

7. 遍歷map中的所有鍵值對(duì)：

   for (auto it = myMap.begin(); it != myMap.end(); it++) {cout << it->first << ": " << it->second << endl;}for (auto elem : myMap) {cout << elem.first << ": " << elem.second << endl;}

第二種方法可以使用C++11中的range-based for循環(huán)。

set

C++中的set是STL（標(biāo)準(zhǔn)模板庫）中的關(guān)聯(lián)容器之一，用于存儲(chǔ)不重復(fù)的元素，并按照一定順序進(jìn)行排序。

以下是set的常見操作：

1. 創(chuàng)建一個(gè)空的set：

   set<int> mySet; // 創(chuàng)建一個(gè)空的set，元素為int類型

2. 在set中插入元素：

   mySet.insert(10); // 在set中插入元素10mySet.insert(20); // 在set中插入元素20mySet.insert(30); // 在set中插入元素30

3. 訪問set中的元素或查找元素：

   auto it = mySet.find(20); // 查找元素20的迭代器if (it != mySet.end()) {int value = *it; // 獲取迭代器指向的值}

4. 獲取set的大小：

   int size = mySet.size(); // 獲取set中元素的個(gè)數(shù)bool isEmpty = mySet.empty(); // 判斷set是否為空

5. 刪除set中的元素：

   mySet.erase(20); // 刪除元素20auto it = mySet.find(30);if (it != mySet.end()) {mySet.erase(it); // 刪除迭代器指向的元素}

6. 清空set中的所有元素：

   mySet.clear(); // 清空set中的所有元素

7. 遍歷set中的所有元素：

   for (auto it = mySet.begin(); it != mySet.end(); it++) {cout << *it << endl;}for (auto elem : mySet) {cout << elem << endl;}

第二種方法可以使用C++11中的range-based for循環(huán)。

性能比較

使用相同的算法，對(duì)vector、list和set進(jìn)行插入數(shù)據(jù)和刪除數(shù)據(jù)操作

//insert number to list,increasing sort
void insert_l(int arg){list<int>::iterator iter;for(iter = gl.begin();iter!=gl.end();iter++){//ergodic listif(arg<*iter){gl.insert(iter,arg);//insert numberbreak;}}if(iter == gl.end()){gl.push_back(arg);//push back number}
}
//delete number from list
void delete_l(){default_random_engine e1(seed);//new random engine with seedwhile(!gl.empty()){uniform_int_distribution<unsigned> u(0,gl.size()-1);list<int>::iterator iter = gl.begin();//using iteratorfor(int i=0;i<u(e1);i++){iter++;}gl.erase(iter);//delete number}
}

結(jié)果

Data Size	Vector Time (s)	List Time (s)
10000	0.281257	0.527096
50000	6.792	23.2029
100000	26.824	107.947
150000	60.0688	333.013
200000	106.619	807.597

使用set在插入和刪除200 000數(shù)據(jù)總共只用了2.2331秒、而vector用了106.619秒、list用了807.597秒

總結(jié)

vector的遍歷性能明顯比list要快。這是因?yàn)関ector的元素是存儲(chǔ)在一塊連續(xù)的內(nèi)存空間中，可以直接通過指針進(jìn)行訪問。而list的元素是通過鏈表相互連接起來的，無法直接訪問，需要遍歷整個(gè)鏈表才能訪問某個(gè)元素，因此遍歷性能相對(duì)較低。
vector和list在不同場景下有不同的優(yōu)劣勢，需要根據(jù)具體情況選擇適合的容器。例如，需要隨機(jī)訪問或者高效的遍歷操作時(shí)，可以選擇vector；需要頻繁的插入或者刪除操作時(shí)，可以選擇list。
set是基于紅黑樹實(shí)現(xiàn)的，紅黑樹是一種自平衡的二叉查找樹，它具有快速的插入、刪除和查找操作的時(shí)間復(fù)雜度，因此在處理大量數(shù)據(jù)時(shí)，set的性能表現(xiàn)會(huì)更好。