STL容器

总体

按照不同的需要，容器可以分为三类： 序列式容器，关联式容器，无序容器

序列式容器

vector和deque虽然可以随机访问，但不能通过[ ]进行赋值，list无法使用[ ],只能通过front()或者迭代器访问元素。list和deque都可以双向访问，故多了push_front()

#include<vector> #include<deque> #include<array> #include<list> #include<forward_list> vector<int> m_vector; m_vector.push_back(10); //m_vector[1] = 20;//error cout << m_vector[0] << endl; deque<int> m_deque; m_deque.push_back(5); //m_deque[1] = 12;//error m_deque.push_front(10); cout << m_deque[0]<<" "<<m_deque[1] << endl; array<int, 5> m_array; m_array[0] = 1; cout << m_array[0] << endl; list<int> m_list; m_list.push_back(10); m_list.push_front(5); cout << m_list.front() << endl;

关联式容器

关联式容器由二叉树实现，左子树所有元素都比自己小，右子树所有元素都比自己大。

插入元素后，会自动进行排序

#include<set> #include<map> #include<string> map<int, string> m_map = { {1,"1"},{2,"2"} }; for (const auto& elem : m_map) cout << elem.second << " " << endl;; set<double > m_set = {1,2,3,4,5}; for (const auto& elem : m_set) cout << elem <<" "; cout << endl; m_set.insert({ 1.5,2.5,3.5,4.5,5.5 });//out: 1 1.5 2 2.5 3 3.5 4 4.5 5 5.5

set 当再次插入相同的元素，将失败

m_set.insert({ 1.5,2.5,3.5,4.5,5.5 });//out: 1 1.5 2 2.5 3 3.5 4 4.5 5 5.5 for (const auto& elem : m_set) cout << elem << " ";

multiset和multimap插入元素，后将新元素排在等效元素的后面，且调用insert，emplace或者erase等等效元素的次序也保持不变

multiset<double> multiset = { 1,2,3,4,5 };//out: 1 1.5 1.5 2 2.5 2.5 3 3.5 3.5 4 4.5 4.5 5 5.5 5.5

但当尝试修改value的值，会报错，修改value将会改变容器的有序状态，所以set在底层为const double，而map在底层为pair<const int,string>

for (auto& elem : m_set) elem = 0;//error

无序容器

无序容器由hash table实现，内部结构是一个由list组成的array，通过哈希函数的运算确定元素落在这个array的位置。 元素没有明确的次序，当安插一个元素时候，所有元素的顺序都可能改变,c++标准保证删除不会改变次序，但删除后的插入将会重新排序。

#include<unordered_set> #include<unordered_map> unordered_set<double> m_unordered_set; unordered_map<int, string> m_unordered_map; m_unordered_set.insert({ 1,2,3,4,5,6 }); for (const auto& elem : m_unordered_set) cout << elem << " ";//out:1 6 4 3 2 5 cout << endl; m_unordered_set.insert( 7 ); for (const auto& elem : m_unordered_set) cout << elem << " ";//out:1 6 4 3 2 7 5 cout << endl;