list

列表（list）是C++ STL中的一种容器类型，它是一个双向链表，可以在任意位置高效地添加、删除、移动元素。

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

创建列表


#include <list>

std::list<int> myList;

添加元素


myList.push_back(1); // 在列表尾部添加元素

myList.push_front(2); // 在列表头部添加元素

myList.insert(myList.begin(), 3); // 在指定位置插入元素

删除元素


myList.pop_back(); // 删除尾部元素

myList.pop_front(); // 删除头部元素

myList.erase(myList.begin()); // 删除指定位置的元素

遍历列表


std::list<int>::iterator it;

for(it=myList.begin(); it!=myList.end(); ++it) {

    std::cout << *it << ' ';

}

获取列表大小


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

判断列表是否为空


if(myList.empty()) {

    std::cout << "List is empty" << std::endl;

}

清空列表


myList.clear();

列表排序


myList.sort(); // 默认从小到大排序

myList.sort(std::greater<int>()); // 从大到小排序

反转列表


myList.reverse();

以上是一些常用的列表操作，更多操作可以参考C++ STL中list的文档。

vector

C++中的vector是STL（标准模板库）中的容器之一，用于存储动态大小的元素序列。

以下是vector的常见操作：

创建一个空的vector：


   vector<int> vec; // 创建一个空的vector<int>

   vector<string> strVec; // 创建一个空的vector<string>

在vector末尾添加元素：


   vec.push_back(1); // 在vector末尾添加一个int类型元素1

   strVec.push_back("hello"); // 在vector末尾添加一个string类型元素"hello"

访问vector中的元素：


   int firstElem = vec[0]; // 访问第一个元素

   string lastElem = strVec.back(); // 访问最后一个元素

获取vector的大小：


   int size = vec.size(); // 获取vector中元素的个数

   bool isEmpty = strVec.empty(); // 判断vector是否为空

删除vector中的元素：


   vec.pop_back(); // 删除vector末尾的一个元素

   strVec.erase(strVec.begin() + 2); // 删除vector中索引为2的元素

清空vector中所有元素：


   vec.clear(); // 清空vector中所有元素

   strVec.resize(0); // 将vector的大小设置为0

遍历vector中的所有元素：


   for (int i = 0; i < vec.size(); i++) {

       cout << vec[i] << " ";

   }

   

   for (auto s : strVec) {

       cout << s << " ";

   }

第二种方法可以使用C++11中的range-based for循环。

map

C++中的map是STL（标准模板库）中的关联容器之一，用于存储键值对。

以下是map的常见操作：

创建一个空的map：


   map<string, int> myMap; // 创建一个空的map，键为string类型，值为int类型

在map中插入键值对：


   myMap.insert(make_pair("apple", 10)); // 在map中插入键为"apple"，值为10的键值对

   myMap["banana"] = 20; // 在map中插入键为"banana"，值为20的键值对

访问map中的元素或查找键：


   int value = myMap["apple"]; // 访问键为"apple"的值

   auto it = myMap.find("banana"); // 查找键为"banana"的迭代器

   if (it != myMap.end()) {

       int value = it->second; // 获取迭代器指向的值

   }

获取map的大小：


   int size = myMap.size(); // 获取map中键值对的个数

   bool isEmpty = myMap.empty(); // 判断map是否为空

删除map中的键值对：


   myMap.erase("apple"); // 删除键为"apple"的键值对

   auto it = myMap.find("banana");

   if (it != myMap.end()) {

       myMap.erase(it); // 删除迭代器指向的键值对

   }

清空map中的所有键值对：


   myMap.clear(); // 清空map中的所有键值对

遍历map中的所有键值对：


   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循环。

set

C++中的set是STL（标准模板库）中的关联容器之一，用于存储不重复的元素，并按照一定顺序进行排序。

以下是set的常见操作：

创建一个空的set：


   set<int> mySet; // 创建一个空的set，元素为int类型

在set中插入元素：


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

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

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

访问set中的元素或查找元素：


   auto it = mySet.find(20); // 查找元素20的迭代器

   if (it != mySet.end()) {

       int value = *it; // 获取迭代器指向的值

   }

获取set的大小：


   int size = mySet.size(); // 获取set中元素的个数

   bool isEmpty = mySet.empty(); // 判断set是否为空

删除set中的元素：


   mySet.erase(20); // 删除元素20

   auto it = mySet.find(30);

   if (it != mySet.end()) {

       mySet.erase(it); // 删除迭代器指向的元素

   }

清空set中的所有元素：


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

遍历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循环。

性能比较

使用相同的算法，对vector、list和set进行插入数据和删除数据操作


//insert number to list,increasing sort

void insert_l(int arg){

    list<int>::iterator iter;

    for(iter = gl.begin();iter!=gl.end();iter++){//ergodic list

        if(arg<*iter){

            gl.insert(iter,arg);//insert number

            break;

        }

    }

    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 seed

    while(!gl.empty()){

        uniform_int_distribution<unsigned> u(0,gl.size()-1);

        list<int>::iterator iter = gl.begin();//using iterator

        for(int i=0;i<u(e1);i++){

            iter++;

        }

        gl.erase(iter);//delete number

    }

}

结果

| 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数据总共只用了2.2331秒、而vector用了106.619秒、list用了807.597秒

总结

vector的遍历性能明显比list要快。这是因为vector的元素是存储在一块连续的内存空间中，可以直接通过指针进行访问。而list的元素是通过链表相互连接起来的，无法直接访问，需要遍历整个链表才能访问某个元素，因此遍历性能相对较低。

vector和list在不同场景下有不同的优劣势，需要根据具体情况选择适合的容器。例如，需要随机访问或者高效的遍历操作时，可以选择vector；需要频繁的插入或者删除操作时，可以选择list。

set是基于红黑树实现的，红黑树是一种自平衡的二叉查找树，它具有快速的插入、删除和查找操作的时间复杂度，因此在处理大量数据时，set的性能表现会更好。

cpp模板库容器list vector map set操作和性能对比

list

vector

map

set

性能比较

总结