C++中map和set如何使用

发布时间：2023-02-22 11:13:33 作者：iii
来源：亿速云阅读：137

C++中map和set如何使用

1. 引言

在C++编程中，map和set是两种非常常用的关联容器。它们基于红黑树（一种自平衡二叉查找树）实现，提供了高效的查找、插入和删除操作。map和set的主要区别在于它们存储的元素类型：map存储键值对（key-value pairs），而set只存储键（key）。本文将详细介绍map和set的使用方法，并通过示例代码帮助读者更好地理解它们的应用场景。

2. `map`的使用

2.1 `map`的基本概念

map是C++标准模板库（STL）中的一种关联容器，它存储的元素是键值对（key-value pairs）。map中的键是唯一的，每个键对应一个值。map内部通过红黑树实现，因此它的查找、插入和删除操作的时间复杂度都是O(log n)。

2.2 `map`的声明和初始化

在使用map之前，需要包含头文件<map>。map的声明格式如下：

#include <map>

std::map<KeyType, ValueType> myMap;

其中，KeyType是键的类型，ValueType是值的类型。例如，声明一个键为int、值为std::string的map：

std::map<int, std::string> myMap;

map可以通过以下几种方式进行初始化：

默认初始化：创建一个空的map。
列表初始化：使用花括号{}初始化map。
拷贝初始化：通过另一个map进行初始化。

示例代码：

#include <iostream>
#include <map>

int main() {
    // 默认初始化
    std::map<int, std::string> map1;

    // 列表初始化
    std::map<int, std::string> map2 = {
        {1, "apple"},
        {2, "banana"},
        {3, "cherry"}
    };

    // 拷贝初始化
    std::map<int, std::string> map3(map2);

    // 输出map2的内容
    for (const auto& pair : map2) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

2.3 `map`的常用操作

2.3.1 插入元素

map提供了多种插入元素的方法，常用的有insert和emplace。

insert：插入一个键值对，如果键已经存在，则插入失败。
emplace：直接构造并插入一个键值对，避免了不必要的拷贝或移动操作。

示例代码：

#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> myMap;

    // 使用insert插入元素
    myMap.insert(std::make_pair(1, "apple"));
    myMap.insert(std::make_pair(2, "banana"));

    // 使用emplace插入元素
    myMap.emplace(3, "cherry");

    // 输出map的内容
    for (const auto& pair : myMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

2.3.2 访问元素

map提供了多种访问元素的方法，常用的有operator[]和at。

operator[]：通过键访问值，如果键不存在，则会插入一个默认值。
at：通过键访问值，如果键不存在，则会抛出std::out_of_range异常。

示例代码：

#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> myMap = {
        {1, "apple"},
        {2, "banana"},
        {3, "cherry"}
    };

    // 使用operator[]访问元素
    std::cout << "map[1] = " << myMap[1] << std::endl;

    // 使用at访问元素
    std::cout << "map.at(2) = " << myMap.at(2) << std::endl;

    // 访问不存在的键
    // std::cout << "map.at(4) = " << myMap.at(4) << std::endl; // 抛出异常

    return 0;
}

2.3.3 删除元素

map提供了erase方法来删除元素。erase可以接受一个键、一个迭代器或一个迭代器范围作为参数。

示例代码：

#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> myMap = {
        {1, "apple"},
        {2, "banana"},
        {3, "cherry"}
    };

    // 删除键为2的元素
    myMap.erase(2);

    // 删除第一个元素
    myMap.erase(myMap.begin());

    // 输出map的内容
    for (const auto& pair : myMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

2.3.4 查找元素

map提供了find方法来查找元素。find方法返回一个迭代器，指向找到的元素；如果未找到，则返回end()。

示例代码：

#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> myMap = {
        {1, "apple"},
        {2, "banana"},
        {3, "cherry"}
    };

    // 查找键为2的元素
    auto it = myMap.find(2);
    if (it != myMap.end()) {
        std::cout << "Found: " << it->first << ": " << it->second << std::endl;
    } else {
        std::cout << "Not found" << std::endl;
    }

    // 查找键为4的元素
    it = myMap.find(4);
    if (it != myMap.end()) {
        std::cout << "Found: " << it->first << ": " << it->second << std::endl;
    } else {
        std::cout << "Not found" << std::endl;
    }

    return 0;
}

2.3.5 遍历`map`

map可以通过迭代器进行遍历。map的迭代器指向的元素是一个std::pair，其中first是键，second是值。

示例代码：

#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> myMap = {
        {1, "apple"},
        {2, "banana"},
        {3, "cherry"}
    };

    // 使用迭代器遍历map
    for (auto it = myMap.begin(); it != myMap.end(); ++it) {
        std::cout << it->first << ": " << it->second << std::endl;
    }

    // 使用范围for循环遍历map
    for (const auto& pair : myMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

2.4 `map`的高级用法

2.4.1 自定义比较函数

map默认使用std::less作为比较函数，即按键的升序排列。如果需要自定义比较函数，可以在声明map时指定。

示例代码：

#include <iostream>
#include <map>

// 自定义比较函数
struct Compare {
    bool operator()(const int& a, const int& b) const {
        return a > b; // 按降序排列
    }
};

int main() {
    std::map<int, std::string, Compare> myMap = {
        {1, "apple"},
        {2, "banana"},
        {3, "cherry"}
    };

    // 输出map的内容
    for (const auto& pair : myMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

2.4.2 `multimap`

multimap是map的一个变种，它允许键重复。multimap的使用方法与map类似，但由于键可以重复，因此在插入和查找时需要注意。

示例代码：

#include <iostream>
#include <map>

int main() {
    std::multimap<int, std::string> myMultimap;

    // 插入元素
    myMultimap.insert(std::make_pair(1, "apple"));
    myMultimap.insert(std::make_pair(2, "banana"));
    myMultimap.insert(std::make_pair(1, "apricot"));

    // 输出multimap的内容
    for (const auto& pair : myMultimap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

3. `set`的使用

3.1 `set`的基本概念

set是C++标准模板库（STL）中的一种关联容器，它存储的元素是唯一的键（key）。set内部通过红黑树实现，因此它的查找、插入和删除操作的时间复杂度都是O(log n)。

3.2 `set`的声明和初始化

在使用set之前，需要包含头文件<set>。set的声明格式如下：

#include <set>

std::set<KeyType> mySet;

其中，KeyType是键的类型。例如，声明一个键为int的set：

std::set<int> mySet;

set可以通过以下几种方式进行初始化：

默认初始化：创建一个空的set。
列表初始化：使用花括号{}初始化set。
拷贝初始化：通过另一个set进行初始化。

示例代码：

#include <iostream>
#include <set>

int main() {
    // 默认初始化
    std::set<int> set1;

    // 列表初始化
    std::set<int> set2 = {1, 2, 3, 4, 5};

    // 拷贝初始化
    std::set<int> set3(set2);

    // 输出set2的内容
    for (const auto& elem : set2) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    return 0;
}

3.3 `set`的常用操作

3.3.1 插入元素

set提供了insert方法来插入元素。insert方法返回一个std::pair，其中first是一个迭代器，指向插入的元素；second是一个布尔值，表示插入是否成功。

示例代码：

#include <iostream>
#include <set>

int main() {
    std::set<int> mySet;

    // 插入元素
    mySet.insert(1);
    mySet.insert(2);
    mySet.insert(3);

    // 输出set的内容
    for (const auto& elem : mySet) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    return 0;
}

3.3.2 删除元素

set提供了erase方法来删除元素。erase可以接受一个键、一个迭代器或一个迭代器范围作为参数。

示例代码：

#include <iostream>
#include <set>

int main() {
    std::set<int> mySet = {1, 2, 3, 4, 5};

    // 删除键为3的元素
    mySet.erase(3);

    // 删除第一个元素
    mySet.erase(mySet.begin());

    // 输出set的内容
    for (const auto& elem : mySet) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    return 0;
}

3.3.3 查找元素

set提供了find方法来查找元素。find方法返回一个迭代器，指向找到的元素；如果未找到，则返回end()。

示例代码：

#include <iostream>
#include <set>

int main() {
    std::set<int> mySet = {1, 2, 3, 4, 5};

    // 查找键为3的元素
    auto it = mySet.find(3);
    if (it != mySet.end()) {
        std::cout << "Found: " << *it << std::endl;
    } else {
        std::cout << "Not found" << std::endl;
    }

    // 查找键为6的元素
    it = mySet.find(6);
    if (it != mySet.end()) {
        std::cout << "Found: " << *it << std::endl;
    } else {
        std::cout << "Not found" << std::endl;
    }

    return 0;
}

3.3.4 遍历`set`

set可以通过迭代器进行遍历。set的迭代器指向的元素是键本身。

示例代码：

#include <iostream>
#include <set>

int main() {
    std::set<int> mySet = {1, 2, 3, 4, 5};

    // 使用迭代器遍历set
    for (auto it = mySet.begin(); it != mySet.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    // 使用范围for循环遍历set
    for (const auto& elem : mySet) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    return 0;
}

3.4 `set`的高级用法

3.4.1 自定义比较函数

set默认使用std::less作为比较函数，即按键的升序排列。如果需要自定义比较函数，可以在声明set时指定。

示例代码：

#include <iostream>
#include <set>

// 自定义比较函数
struct Compare {
    bool operator()(const int& a, const int& b) const {
        return a > b; // 按降序排列
    }
};

int main() {
    std::set<int, Compare> mySet = {1, 2, 3, 4, 5};

    // 输出set的内容
    for (const auto& elem : mySet) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    return 0;
}

3.4.2 `multiset`

multiset是set的一个变种，它允许键重复。multiset的使用方法与set类似，但由于键可以重复，因此在插入和查找时需要注意。

示例代码：

#include <iostream>
#include <set>

int main() {
    std::multiset<int> myMultiset;

    // 插入元素
    myMultiset.insert(1);
    myMultiset.insert(2);
    myMultiset.insert(1);

    // 输出multiset的内容
    for (const auto& elem : myMultiset) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    return 0;
}

4. `map`和`set`的性能分析

map和set基于红黑树实现，因此它们的查找、插入和删除操作的时间复杂度都是O(log n)。这使得它们在处理大量数据时仍然能够保持较高的性能。然而，由于红黑树的实现较为复杂，map和set的内存开销相对较大。

4.1 查找性能

map和set的查找性能非常高效，时间复杂度为O(log n)。这使得它们非常适合用于需要频繁查找的场景。

4.2 插入和删除性能

map和set的插入和删除操作的时间复杂度也是O(log n)。由于红黑树的自平衡特性，插入和删除操作不会导致树的高度显著增加，从而保证了操作的稳定性。

4.3 内存开销

map和set的内存开销相对较大，因为它们需要存储额外的指针来维护树的结构。此外，map还需要存储键值对，而set只需要存储键。

5. `map`和`set`的应用场景

5.1 `map`的应用场景

map非常适合用于需要存储键值对并进行快速查找的场景。例如：

字典：存储单词及其释义。
缓存：存储键及其对应的缓存值。
计数器：存储元素及其出现次数。

5.2 `set`的应用场景

set非常适合用于需要存储唯一元素并进行快速查找的场景。例如：

去重：存储一组唯一的元素。
集合运算：进行交集、并集、差集等操作。
排序：存储一组有序的元素。

6. 总结

map和set是C++中非常强大的关联容器，它们基于红黑树实现，提供了高效的查找、插入和删除操作。map适用于存储键值对，而set适用于存储唯一元素。通过本文的介绍，读者应该能够掌握map和set的基本使用方法，并能够在实际编程中灵活运用它们。

在实际应用中，选择map还是set取决于具体的需求。如果需要存储键值对并进行快速查找，map是更好的选择；如果只需要存储唯一元素并进行快速查找，set则更为合适。无论选择哪种容器，理解其内部实现和性能特点都是非常重要的，这有助于编写出高效、稳定的代码。

C++中map和set如何使用

C++中map和set如何使用

1. 引言

2. map的使用

2.1 map的基本概念

2.2 map的声明和初始化

2.3 map的常用操作

2.3.1 插入元素

2.3.2 访问元素

2.3.3 删除元素

2.3.4 查找元素

2.3.5 遍历map

2.4 map的高级用法

2.4.1 自定义比较函数

2.4.2 multimap

3. set的使用

3.1 set的基本概念

3.2 set的声明和初始化

3.3 set的常用操作

3.3.1 插入元素

3.3.2 删除元素

3.3.3 查找元素

3.3.4 遍历set

3.4 set的高级用法

3.4.1 自定义比较函数

3.4.2 multiset

4. map和set的性能分析

4.1 查找性能

4.2 插入和删除性能

4.3 内存开销

5. map和set的应用场景

5.1 map的应用场景

5.2 set的应用场景

6. 总结

相关阅读

2. `map`的使用

2.1 `map`的基本概念

2.2 `map`的声明和初始化

2.3 `map`的常用操作

2.3.5 遍历`map`

2.4 `map`的高级用法

2.4.2 `multimap`

3. `set`的使用

3.1 `set`的基本概念

3.2 `set`的声明和初始化

3.3 `set`的常用操作

3.3.4 遍历`set`

3.4 `set`的高级用法

3.4.2 `multiset`

4. `map`和`set`的性能分析

5. `map`和`set`的应用场景

5.1 `map`的应用场景

5.2 `set`的应用场景