一、序列式容器和关联式容器我们所知道的vector、list、deque、string等其逻辑结构为线性各个位置存储的值没有固定的顺序要求这类容器称为序列式容器。而关联式容器的逻辑结构通常是非线性的各个位置的元素顺序不能随意更改否则会破坏其底层存储结构。典型的关联式容器有map/set系列、unordered_map和unordered_set系列。二、set系列的使用一set的声明set的模板声明如下template class T, class Compare lessT, class Alloc allocatorT class set;1. 第一个模板参数T底层关键字的类型即set中存储的数据类型。2. 第二个模板参数Compare仿函数默认实现为小于比较lessT可根据需求传入自定义仿函数实现自定义排序规则。3. 第三个模板参数Alloc空间配置器set底层存储数据的内存由该配置器分配通常使用默认配置器即可若需高性能场景如频繁增删、大量数据存储可自行实现内存池传入该参数。补充set的底层由红黑树平衡二叉搜索树实现因此其增、删、查操作的时间复杂度均为O(logN)迭代器遍历遵循红黑树的中序遍历规则因此遍历结果是有序的。二set的构造和迭代器1. 构造函数// empty (1) 无参默认构造 explicit set (const key_compare comp key_compare(), const allocator_type alloc allocator_type()); // range (2) 迭代器区间构造将[first, last)区间内的数据构造为set template class InputIterator set (InputIterator first, InputIterator last, const key_compare comp key_compare(), const allocator_type allocator_type()); // copy (3) 拷贝构造用已有set对象x构造新的set set (const set x); // initializer list (5) 初始化列表构造用初始化列表il中的数据构造set set (initializer_listvalue_type il, const key_compare comp key_compare(), const allocator_type alloc allocator_type());2. 迭代器set的迭代器为双向迭代器不支持随机访问即不能使用、-等随机访问操作其类型为指向const value_type的迭代器set中的元素不可修改避免破坏红黑树结构。// 正向迭代器从首元素开始到尾后位置结束 iterator begin(); // 返回指向首元素的迭代器 iterator end(); // 返回指向尾后位置不存储数据的迭代器 // 反向迭代器从尾元素开始到首元素前位置结束 reverse_iterator rbegin(); // 返回指向尾元素的反向迭代器 reverse_iterator rend(); // 返回指向首元素前位置的反向迭代器三set的增删查操作1. 插入操作// 单个数据插入插入val若val已存在则插入失败返回pairiterator,bool// 其中iterator指向val所在位置插入成功则指向新元素失败则指向已存在的元素bool表示插入是否成功pairiterator,bool insert(const value_type val);// 列表插入插入初始化列表il中的所有元素已存在的元素不会重复插入void insert(initializer_listvalue_type il);// 迭代器区间插入插入[first, last)区间内的所有元素已存在的元素不会重复插入template class InputIteratorvoid insert (InputIterator first, InputIterator last);2. 查找操作// 查找val返回val所在的迭代器若未找到则返回end()iterator find (const value_type val);// 统计val个数返回val在set中的个数set中元素唯一因此返回值只能是0或1size_type count (const value_type val) const;思考当需求只是判断某个元素是否存在时用count比find更简洁只需判断count返回值是否为1但如果需要获取该元素的具体位置那就只能用find了。3. 删除操作// 按迭代器删除删除迭代器position指向的元素返回删除后下一个元素的迭代器iterator erase (const_iterator position);// 按值删除删除val若val不存在返回0存在则返回1删除成功的个数size_type erase (const value_type val);// 按区间删除删除[first, last)区间内的所有元素返回删除后下一个元素的迭代器iterator erase (const_iterator first, const_iterator last);4. 边界查找操作// lower_bound返回第一个大于等于val的元素的迭代器iterator lower_bound (const value_type val) const;// upper_bound返回第一个大于val的元素的迭代器iterator upper_bound (const value_type val) const;二者搭配使用可组合出一个左闭右开区间[lower_bound(val), upper_bound(val))该区间恰好包含所有等于val的元素set中最多一个可作为其他接口如erase的参数。四multiset和set的差异multiset与set的底层实现一致均为红黑树核心差异在于multiset支持关键字冗余即允许存储多个相同的元素基于这一差异二者的接口使用存在以下不同结合代码示例理解更清晰#includeiostream #includeset using namespace std; int main() { // 差异1multiset排序但不 deduplicate插入重复元素会全部保留 multisetint s { 4,2,7,2,4,8,4,5,4,9 }; auto it s.begin(); while (it ! s.end()) { cout *it ; it; } cout endl; // 输出结果2 2 4 4 4 4 5 7 8 9有序 // 差异2find查找时若存在多个相同元素返回中序遍历的第一个元素 int x; cin x; auto pos s.find(x); while (pos ! s.end() *pos x) { cout *pos ; pos; } cout endl; // 例如输入4会输出所有4 // 差异3count返回元素的实际个数而非0或1 cout s.count(x) endl; // 例如输入4返回4 // 差异4按值erase时会删除所有等于x的元素而非仅删除一个 s.erase(x); for (auto e : s) { cout e ; } cout endl; // 例如输入4会删除所有4输出剩余元素 return 0; }三、map系列的使用一map类的介绍map是键值对key-value容器底层同样由红黑树实现其模板声明如下template class Key, class T, class Compare lessKey, class Alloc allocatorpairconst Key,T class map;1. Keymap底层关键字的类型即键的类型用于唯一标识每个键值对。2. Tmap底层value的类型即值的类型是关键字对应的关联数据。3. Compare仿函数默认实现为小于比较lessKey用于对关键字进行排序若Key不支持默认比较或需要自定义排序规则可自行实现仿函数传入。4. Alloc空间配置器用于分配map底层存储键值对的内存默认使用标准配置器即可。补充map的底层红黑树节点中存储的是键值对数据而非单个元素因此需要使用pair类型封装键和值。二pair类型介绍pair本质是一个模板结构体用于封装两个不同类型的数据此处用于封装map的key和valuemap中键值对的类型定义为typedef pairconst Key, T value_type; pair的具体定义如下 template class T1, class T2 struct pair { typedef T1 first_type; // 第一个成员的类型对应map的key typedef T2 second_type; // 第二个成员的类型对应map的value T1 first; // 第一个成员map的key不可修改 T2 second; // 第二个成员map的value可修改 // 无参构造将两个成员初始化为对应类型的默认值 pair(): first(T1()), second(T2()) {} // 带参构造用a和b初始化first和second pair(const T1 a, const T2 b): first(a), second(b) {} // 拷贝构造用另一个pair对象pr初始化当前pair templateclass U, class V pair (const pairU,V pr): first(pr.first), second(pr.second) {} };make_pair函数为了简化pair对象的创建C提供了make_pair模板函数可自动推导两个成员的类型无需手动指定模板参数template class T1,class T2inline pairT1,T2 make_pair (T1 x, T2 y){return ( pairT1,T2(x,y) );}make_pair的作用对比使用场景// 没有make_pair时每次创建pair都要写完整的模板类型繁琐且易出错 std::pairint, std::string p1(42, hello); std::pairint, std::string p2(100, world); std::pairint, std::string p3(1, one); // 插入map时同样需要写完整类型代码冗余 std::mapint, std::string m; m.insert(std::pairint, std::string(1, one)); m.insert(std::pairint, std::string(2, two)); // 有了make_pair编译器会自动推导模板类型简洁高效 auto p std::make_pair(42, hello); // 自动推断为pairint, string m.insert(std::make_pair(3, three)); // 插入map时无需手动指定类型三map的构造和迭代器1. 构造函数// empty (1) 无参默认构造创建一个空的map explicit map (const key_compare comp key_compare(), const allocator_type alloc allocator_type()); // range (2) 迭代器区间构造将[first, last)区间内的键值对构造为map template class InputIterator map (InputIterator first, InputIterator last, const key_compare comp key_compare(), const allocator_type allocator_type()); // copy (3) 拷贝构造用已有map对象x构造新的map map (const map x); // initializer list (5) 初始化列表构造用初始化列表il中的键值对构造map map (initializer_listvalue_type il, const key_compare comp key_compare(), const allocator_type alloc allocator_type());2. 迭代器map的迭代器为双向迭代器不支持随机访问其指向的是pairconst Key, T类型key不可修改value可修改。// 正向迭代器iterator begin(); // 返回指向首元素键值对的迭代器iterator end(); // 返回指向尾后位置的迭代器// 反向迭代器reverse_iterator rbegin(); // 返回指向尾元素的反向迭代器reverse_iterator rend(); // 返回指向首元素前位置的反向迭代器四map的增删查操作map的增删查操作核心关注关键字key插入操作需传入键值对查找和删除操作仅需传入key与set的接口逻辑类似但需注意键值对的特殊性。1. 插入操作// 单个键值对插入插入valpair类型若key已存在则插入失败即使value不同也失败// 返回pairiterator,booliterator指向key所在的键值对bool表示插入是否成功pairiterator,bool insert (const value_type val);// 列表插入插入初始化列表il中的所有键值对已存在的key不会重复插入void insert (initializer_listvalue_type il);// 迭代器区间插入插入[first, last)区间内的所有键值对已存在的key不会重复插入template class InputIteratorvoid insert (InputIterator first, InputIterator last);2. 查找操作// 按key查找返回key所在键值对的迭代器未找到则返回end()// 找到后可通过迭代器访问keyit-first和valueit-second且可修改valueiterator find (const key_type k);// 按key统计个数返回key在map中的个数map中key唯一因此返回0或1size_type count (const key_type k) const;3. 删除操作// 按迭代器删除删除迭代器position指向的键值对返回删除后下一个元素的迭代器iterator erase (const_iterator position);// 按key删除删除key对应的键值对key不存在返回0存在返回1size_type erase (const key_type k);// 按区间删除删除[first, last)区间内的所有键值对返回删除后下一个元素的迭代器iterator erase (const_iterator first, const_iterator last);4. 边界查找操作// lower_bound返回第一个key大于等于k的键值对的迭代器iterator lower_bound (const key_type k);// lower_boundconst版本返回第一个key大于等于k的键值对的const迭代器不可修改valueconst_iterator lower_bound (const key_type k) const;// upper_bound返回第一个key大于k的键值对的迭代器补充原文档遗漏接口iterator upper_bound (const key_type k);const_iterator upper_bound (const key_type k) const;五map的数据修改重要规则map支持修改valuemapped_type但不支持修改key。因为key是红黑树排序的依据修改key会破坏底层搜索树的结构导致容器混乱。补充说明从map的类型定义来看传统意义上的“value”即与key关联的数据被typedef为mapped_type而value_type是红黑树节点中存储的pairconst Key, T键值对。日常使用中我们仍习惯将T类型的关联数据称为value。1. 通过迭代器修改value通过find返回的迭代器或遍历得到的迭代器可直接修改其指向的键值对的second成员即value// 查找key为k的键值对返回其迭代器未找到返回end()iterator find (const key_type k);// 示例修改key为1对应的valuemapint, string m; m.insert(make_pair(1, one));auto it m.find(1);if (it ! m.end()) { it-second first; } // 合法修改value// it-first 2; // 非法修改key会报错2. 通过operator[]修改/插入/查找operator[]是map的多功能复合接口同时支持插入、查找和修改操作其内部实现依赖insert接口具体逻辑如下mapped_type operator[] (const key_type k){// 1. 尝试插入键值对{k, mapped_type()}mapped_type()为value的默认值如int默认0string默认空串pairiterator, bool ret insert({ k, mapped_type() });// 2. ret.first指向key为k的键值对无论插入成功与否iterator it ret.first;// 3. 返回value的引用可通过引用修改valuereturn it-second;}深入理解insert与operator[]的关联insert插入pairkey, T对象时有两种情况1. 若key已在map中插入失败返回的pairiterator,bool中first指向该key所在的键值对second为false。2. 若key不在map中插入成功返回的pairiterator,bool中first指向新插入的键值对second为true。核心结论无论插入成功与否insert返回的pair对象的first始终指向key所在的迭代器——这一特性使得insert可以实现operator[]的多功能逻辑- 当key不存在时insert插入默认value的键值对operator[]返回该value的引用可修改插入修改- 当key存在时insert插入失败但first仍指向该key的键值对operator[]返回value的引用可修改查找修改。与vector[]的对比六multimap和map的差异multimap与map的使用基本一致核心差异在于multimap支持key冗余允许多个相同的key基于这一差异二者的接口使用存在以下不同与set和multiset的差异逻辑完全一致1. insert插入键值对时允许插入相同key的不同value不会判断key是否已存在。2. find查找key时若存在多个相同key返回中序遍历的第一个键值对的迭代器。3. count返回key对应的键值对的实际个数而非0或1。4. erase按key删除时会删除所有key等于该值的键值对按迭代器删除时仅删除该迭代器指向的单个键值对。5. 不支持operator[]因为key可冗余operator[]无法确定返回哪个key对应的value因此仅支持插入无法实现修改和精准查找故不提供该接口。