关联容器

2.1 关联容器的定义和特点

关联容器是C++标准模板库(STL)中的一种容器类型，与顺序容器不同，关联容器中的元素不是按插入顺序存储的，而是按照键(key)自动排序并存储的。关联容器通过键来高效地访问元素，而不是通过位置索引。

主要特点：

自动排序：元素在插入时根据键自动排序
高效查找：基于键的查找操作非常高效(对数时间复杂度)
键值对：部分关联容器(map/multimap)存储键值对
唯一键：部分关联容器(set/map)要求键唯一
多重键：部分关联容器(multiset/multimap)允许多个元素具有相同键

关联容器与顺序容器的区别：

特性	顺序容器	关联容器
元素存储	按插入顺序	按键自动排序
访问方式	位置索引/迭代器	键值查找
查找效率	O(n)	O(log n)
主要用途	线性序列存储	键值映射/集合

2.2 关联容器的分类

2.2.1 set

存储唯一键的集合
元素本身即为键
自动排序
头文件：#include <set>

2.2.2 multiset

存储可重复键的集合
元素本身即为键
自动排序
头文件：#include <set>

2.2.3 map

存储键值对(key-value pairs)
键唯一
按键自动排序
头文件：#include <map>

2.2.4 multimap

存储键值对
允许重复键
按键自动排序
头文件：#include <map>

2.3 关联容器的共同特性

2.3.1 构造函数

cpp

set<T> s;                         // 空set
set<T> s(begin, end);             // 从迭代器范围构造
set<T> s(initializer_list);       // 初始化列表构造

map<K, V> m;                      // 空map
map<K, V> m(begin, end);          // 从迭代器范围构造
map<K, V> m(initializer_list);    // 初始化列表构造

2.3.2 容量操作

cpp

bool empty() const;               // 容器是否为空
size_t size() const;              // 元素数量
size_t max_size() const;          // 最大可能元素数量

2.3.3 修改操作

cpp

// 插入元素
pair<iterator, bool> insert(const value_type& value);  // set
iterator insert(iterator hint, const value_type& value);
void insert(InputIt first, InputIt last);

// 删除元素
void erase(iterator pos);
size_type erase(const key_type& key);
void erase(iterator first, iterator last);

// 清空容器
void clear() noexcept;

2.3.4 查找操作

cpp

// 查找键
iterator find(const key_type& key);
const_iterator find(const key_type& key) const;

// 统计键出现次数
size_type count(const key_type& key) const;

// 返回键的边界
iterator lower_bound(const key_type& key);
const_iterator lower_bound(const key_type& key) const;
iterator upper_bound(const key_type& key);
const_iterator upper_bound(const key_type& key) const;
pair<iterator, iterator> equal_range(const key_type& key);

2.3.5 迭代器

cpp

iterator begin() noexcept;
const_iterator begin() const noexcept;
iterator end() noexcept;
const_iterator end() const noexcept;
reverse_iterator rbegin() noexcept;
const_reverse_iterator rbegin() const noexcept;
reverse_iterator rend() noexcept;
const_reverse_iterator rend() const noexcept;

2.4 set和multiset详解

2.4.1 set

存储唯一键的集合
元素按升序自动排序
插入重复元素会被忽略
查找效率高(O(log n))

常用操作示例

cpp

#include <iostream>
#include <set>

int main()
{
    // 创建set
    std::set<int> mySet;
    
    // 插入元素
    mySet.insert(30);
    mySet.insert(10);
    mySet.insert(20);
    mySet.insert(10); // 重复元素，不会被插入
    
    // 遍历元素(自动排序)
    std::cout << "Set elements: ";
    for(const auto& elem : mySet) {
        std::cout << elem << " "; // 输出: 10 20 30
    }
    std::cout << std::endl;
    
    // 查找元素
    auto it = mySet.find(20);
    if(it != mySet.end()) {
        std::cout << "Found: " << *it << std::endl;
    }
    
    // 删除元素
    mySet.erase(10);
    
    // 检查元素是否存在
    if(mySet.count(10) {
        std::cout << "10 exists" << std::endl;
    } else {
        std::cout << "10 does not exist" << std::endl;
    }
    
    // 大小
    std::cout << "Set size: " << mySet.size() << std::endl;
    
    return 0;
}

2.4.2 multiset

存储可重复键的集合
元素按升序自动排序
允许插入重复元素
查找效率高(O(log n))

常用操作示例

cpp

#include <iostream>
#include <set>

int main()
{
    // 创建multiset
    std::multiset<int> myMultiSet;
    
    // 插入元素(允许重复)
    myMultiSet.insert(30);
    myMultiSet.insert(10);
    myMultiSet.insert(20);
    myMultiSet.insert(10); // 重复元素，会被插入
    
    // 遍历元素(自动排序)
    std::cout << "Multiset elements: ";
    for(const auto& elem : myMultiSet) {
        std::cout << elem << " "; // 输出: 10 10 20 30
    }
    std::cout << std::endl;
    
    // 统计元素出现次数
    std::cout << "Count of 10: " << myMultiSet.count(10) << std::endl;
    
    // 删除所有10
    myMultiSet.erase(10);
    
    // 检查元素是否存在
    std::cout << "Count of 10 after erase: " << myMultiSet.count(10) << std::endl;
    
    return 0;
}

2.5 map和multimap详解

2.5.1 map

存储键值对(key-value pairs)
键唯一
按键自动排序
通过键快速访问值
插入重复键会覆盖原有值

常用操作示例

cpp

#include <iostream>
#include <map>
#include <string>

int main()
{
    // 创建map
    std::map<std::string, int> studentScores;
    
    // 插入元素
    studentScores["Alice"] = 95;
    studentScores["Bob"] = 88;
    studentScores["Charlie"] = 92;
    studentScores["Alice"] = 97; // 更新Alice的分数
    
    // 遍历元素(按键自动排序)
    std::cout << "Student scores:" << std::endl;
    for(const auto& pair : studentScores) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    
    // 访问元素
    std::cout << "Alice's score: " << studentScores["Alice"] << std::endl;
    
    // 查找元素
    auto it = studentScores.find("Bob");
    if(it != studentScores.end()) {
        std::cout << "Found Bob: " << it->second << std::endl;
    }
    
    // 删除元素
    studentScores.erase("Charlie");
    
    // 检查键是否存在
    if(studentScores.count("Charlie")) {
        std::cout << "Charlie exists" << std::endl;
    } else {
        std::cout << "Charlie does not exist" << std::endl;
    }
    
    // 大小
    std::cout << "Number of students: " << studentScores.size() << std::endl;
    
    return 0;
}

2.5.2 multimap

存储键值对
允许重复键
按键自动排序
通过键访问值，但可能有多个值

常用操作示例

cpp

#include <iostream>
#include <map>
#include <string>

int main()
{
    // 创建multimap
    std::multimap<std::string, std::string> departmentEmployees;
    
    // 插入元素(允许重复键)
    departmentEmployees.insert({"IT", "Alice"});
    departmentEmployees.insert({"IT", "Bob"});
    departmentEmployees.insert({"HR", "Charlie"});
    departmentEmployees.insert({"IT", "David"});
    
    // 遍历元素(按键自动排序)
    std::cout << "Department employees:" << std::endl;
    for(const auto& pair : departmentEmployees) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    
    // 查找特定键的所有值
    auto range = departmentEmployees.equal_range("IT");
    std::cout << "IT department employees:" << std::endl;
    for(auto it = range.first; it != range.second; ++it) {
        std::cout << it->second << std::endl;
    }
    
    // 统计键的数量
    std::cout << "IT employees count: " << departmentEmployees.count("IT") << std::endl;
    
    // 删除特定键的所有元素
    departmentEmployees.erase("HR");
    
    // 检查键是否存在
    if(departmentEmployees.find("HR") == departmentEmployees.end()) {
        std::cout << "HR department has no employees" << std::endl;
    }
    
    return 0;
}

2.6 自定义排序规则

关联容器默认使用std::less进行排序，但我们可以自定义排序规则：

cpp

#include <iostream>
#include <set>
#include <functional>

// 自定义比较函数
struct CaseInsensitiveCompare {
    bool operator()(const std::string& a, const std::string& b) const {
        return std::lexicographical_compare(
            a.begin(), a.end(),
            b.begin(), b.end(),
            [](char c1, char c2) {
                return std::tolower(c1) < std::tolower(c2);
            }
        );
    }
};

int main()
{
    // 使用自定义比较函数的set
    std::set<std::string, CaseInsensitiveCompare> caseInsensitiveSet;
    
    // 插入元素
    caseInsensitiveSet.insert("Apple");
    caseInsensitiveSet.insert("banana");
    caseInsensitiveSet.insert("apple"); // 不会插入，因为"Apple"和"apple"被视为相同
    
    // 遍历元素
    for(const auto& elem : caseInsensitiveSet) {
        std::cout << elem << " "; // 输出: Apple banana
    }
    std::cout << std::endl;
    
    // 查找元素(不区分大小写)
    auto it = caseInsensitiveSet.find("BANANA");
    if(it != caseInsensitiveSet.end()) {
        std::cout << "Found: " << *it << std::endl;
    }
    
    return 0;
}

2.7 关联容器的性能特点

操作	set/map	multiset/multimap	时间复杂度
插入	唯一键	允许重复键	O(log n)
删除	按键删除	按键删除	O(log n)
查找	按键查找	按键查找	O(log n)
遍历	有序遍历	有序遍历	O(n)
空间	额外指针	额外指针	O(n)

2.8 关联容器的选择指南

需求	推荐容器
存储唯一键的集合	set
存储可重复键的集合	multiset
键值对映射，键唯一	map
键值对映射，键可重复	multimap
需要自定义排序规则	任何关联容器+自定义比较器
需要最高效的查找	任何关联容器(对数时间)
需要按键范围查询	map/multimap

关联容器提供了高效的键值存储和查找能力，是C++标准库中处理映射和集合问题的重要工具。

关联容器 ​

2.1 关联容器的定义和特点 ​

主要特点： ​

关联容器与顺序容器的区别： ​

2.2 关联容器的分类 ​

2.2.1 set ​

2.2.2 multiset ​

2.2.3 map ​

2.2.4 multimap ​

2.3 关联容器的共同特性 ​

2.3.1 构造函数 ​

2.3.2 容量操作 ​

2.3.3 修改操作 ​

2.3.4 查找操作 ​

2.3.5 迭代器 ​

2.4 set和multiset详解 ​

2.4.1 set ​

常用操作示例 ​

2.4.2 multiset ​

常用操作示例 ​

2.5 map和multimap详解 ​

2.5.1 map ​

常用操作示例 ​

2.5.2 multimap ​

常用操作示例 ​

2.6 自定义排序规则 ​

2.7 关联容器的性能特点 ​

2.8 关联容器的选择指南 ​

关联容器

2.1 关联容器的定义和特点

主要特点：

关联容器与顺序容器的区别：

2.2 关联容器的分类

2.2.1 set

2.2.2 multiset

2.2.3 map

2.2.4 multimap

2.3 关联容器的共同特性

2.3.1 构造函数

2.3.2 容量操作

2.3.3 修改操作

2.3.4 查找操作

2.3.5 迭代器

2.4 set和multiset详解

2.4.1 set

常用操作示例

2.4.2 multiset

常用操作示例

2.5 map和multimap详解

2.5.1 map

常用操作示例

2.5.2 multimap

常用操作示例

2.6 自定义排序规则

2.7 关联容器的性能特点

2.8 关联容器的选择指南