c++关联容器详细介绍-阿里云开发者社区

关联容器的简介

关联容器是C++标准库的一部分，用于存储和管理具有键值对的数据元素。与顺序容器（如vector和list）不同，关联容器的主要特点是它们能够快速查找特定键的值。这是因为关联容器内部使用了高效的数据结构（如二叉树或哈希表）来组织数据。

关联容器的主要类型包括：

std::set：一个集合，包含唯一元素，按特定顺序排序。

std::map：一个映射，包含键值对，其中键是唯一的。

std::multiset和std::multimap：类似于set和map，但允许键的重复。

std::unordered_set和std::unordered_map：使用哈希表实现，不保证元素的顺序。代码示例：使用std::map

下面是一个使用std::map的示例，展示了如何创建映射、添加元素、查找元素以及遍历映射。

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

int main() {
    // 创建一个std::map，键是std::string类型，值是int类型
    std::map<std::string, int> ageMap;

    // 向map中添加键值对
    ageMap["Alice"] = 30;
    ageMap["Bob"] = 25;
    ageMap.insert(std::make_pair("Charlie", 35));

    // 查找元素
    auto search = ageMap.find("Alice");
    if (search != ageMap.end()) {
        std::cout << "Found Alice, age: " << search->second << '\n';
    } else {
        std::cout << "Alice not found" << '\n';
    }

    // 遍历map中的所有元素
    std::cout << "All elements in the map:\n";
    for (const auto& pair : ageMap) {
        std::cout << pair.first << " is " << pair.second << " years old.\n";
    }

    return 0;
}

代码解释

创建了一个std::map，其键是字符串类型（std::string），值是整数类型（int）。

使用operator[]和insert方法向映射中添加元素。

使用find方法查找键为"Alice"的元素。如果找到，打印出相应的值；如果未找到，打印一条消息。

使用范围for循环遍历映射中的所有键值对，并打印它们。

各类关联容器的特性和用法

由于关联容器的每个类型都包含许多细节和特性，下面将分别详细介绍每种类型的关联容器，并为每种类型提供一个代码示例、注释、运行结果以及相应解释。

1. std::set

用途: std::set是一个存储唯一元素的集合，按照特定顺序自动排序。

代码示例:

#include <iostream>
#include <set>

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

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

    // 尝试插入重复元素（不会成功）
    auto result = mySet.insert(3);
    if (result.second == false) {
        std::cout << "Element '3' already exists in set." << '\n';
    }

    // 遍历并打印集合
    std::cout << "Elements in set: ";
    for (int elem : mySet) {
        std::cout << elem << " ";
    }
    std::cout << '\n';

    return 0;
}

运行结果:

Element '3' already exists in set.
Elements in set: 1 3 4

解释:

创建了一个std::set，用于存储整数。
向集合中插入了三个元素（3, 1, 4）。由于set自动排序，所以元素将按照升序排列。
尝试再次插入元素3，但因为set中已存在，插入操作失败。
遍历并打印出集合中的元素。

2. std::multiset

用途: std::multiset类似于std::set，但它允许存储重复元素。

代码示例:

#include <iostream>
#include <set>

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

    // 插入元素（包括重复的元素）
    myMultiset.insert(3);
    myMultiset.insert(1);
    myMultiset.insert(3);
    myMultiset.insert(2);

    // 遍历并打印集合
    std::cout << "Elements in multiset: ";
    for (int elem : myMultiset) {
        std::cout << elem << " ";
    }
    std::cout << '\n';

    return 0;
}

运行结果:

Elements in multiset: 1 2 3 3

解释:

创建了一个std::multiset。
向集合中插入了四个元素，包括重复的元素3。
multiset同样按照特定顺序（默认升序）排序，但不同于set的是，它允许相同值的元素存在。
打印出集合中的元素，可以看到元素3出现了两次。

3. std::map

用途: std::map存储键值对，其中每个键都是唯一的，自动根据键排序。

代码示例:
#include <iostream>
#include <map>
#include <string>

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

    // 向map中添加键值对
    ageMap["Alice"] = 30;
    ageMap["Bob"] = 25;
    ageMap["Charlie"] = 35;

    // 使用迭代器遍历map
    for (const auto& pair : ageMap) {
        std::cout << pair.first << " is " << pair.second << " years old.\n";
    }

    return 0;
}

运行结果:

Alice is 30 years old.
Bob is 25 years old.
Charlie is 35 years old.

解释:

创建了一个std::map<std::string, int>，键是字符串类型，值是整型。
向映射中添加了三个键值对。
使用范围for循环遍历映射并打印每个键值对。pair.first是键，pair.second是对应的值。

4. std::multimap

用途: std::multimap与std::map相似，但它允许一个键对应多个值。

代码示例:

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

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

    // 向multimap中添加键值对
    ageMultimap.insert(std::make_pair("Alice", 30));
    ageMultimap.insert(std::make_pair("Bob", 25));
    ageMultimap.insert(std::make_pair("Alice", 32));  // 允许重复键

    // 使用迭代器遍历multimap
    for (const auto& pair : ageMultimap) {
        std::cout << pair.first << " is " << pair.second << " years old.\n";
    }

    return 0;
}

运行结果:

Alice is 30 years old.
Alice is 32 years old.
Bob is 25 years old.

解释:

创建了一个std::multimap<std::string, int>。
向多映射中添加了三个键值对，其中"Alice"作为键出现了两次，展示了多映射可以有重复键的特性。
遍历并打印出多映射中的元素。

5. std::unordered_set 和 std::unordered_map

这两种类型的容器使用哈希表实现，不保证元素的顺序，但通常提供更快的查找性能。

std::unordered_set

用途: 用于存储唯一元素，不保证任何顺序。

代码示例:

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> myUnorderedSet;

    // 插入元素
    myUnorderedSet.insert(3);
    myUnorderedSet.insert(1);
    myUnorderedSet.insert(4);

    // 遍历并打印集合
    std::cout << "Elements in unordered set: ";
    for (int elem : myUnorderedSet) {
        std::cout << elem << " ";
    }
    std::cout << '\n';

    return 0;
}

运行结果:

Elements in unordered set: 4 3 1

解释:

创建了一个std::unordered_set。

向无序集合中插入了三个元素。

由于是无序集合，打印的元素顺序可能与插入顺序不同。

std::unordered_map

用途: 存储键值对，不保证顺序。代码示例:

#include <iostream>
#include <unordered_map>
#include <string>

int main() {
    std::unordered_map<std::string, int> ageUnorderedMap;

    // 向unordered_map中添加键值对
    ageUnorderedMap["Alice"] = 30;
    ageUnorderedMap["Bob"] = 25;
    ageUnorderedMap["Charlie"] = 35;

    // 使用迭代器遍历unordered_map
    for (const auto& pair : ageUnorderedMap) {
        std::cout << pair.first << " is " << pair.second << " years old.\n";
    }

    return 0;
}

运行结果:

Charlie is 35 years old.
Alice is 30 years old.
Bob is 25 years old.

解释:

创建了一个std::unordered_map<std::string, int>。
向无序映射中添加了三个键值对。
遍历并打印出无序映射中的元素。元素的顺序是不确定的，因为unordered_map不保证元素的顺序。

关联容器的迭代器

1. 迭代器基础

迭代器是一种访问容器中元素的对象，类似于指针。在 C++ 中，迭代器是一种重要的抽象，使得算法能够独立于它们操作的数据结构。

a. 迭代器类型

输入迭代器：只能向前移动（单次遍历），只读访问。
输出迭代器：只能向前移动（单次遍历），只写访问。
前向迭代器：可以多次遍历，读写访问。
双向迭代器：类似于前向迭代器，但可以向前和向后移动。
随机访问迭代器：提供与指针类似的功能，可以进行随机访问。

b. 获取迭代器

使用容器的.begin()和.end()成员函数来获取指向容器第一个元素和末尾的迭代器。

2. 使用迭代器遍历关联容器

以std::map为例，我们可以使用迭代器来遍历容器。

代码示例

#include <iostream>
#include <map>

int main() {
    std::map<std::string, int> ageMap = {{"Alice", 30}, {"Bob", 25}};

    for (auto it = ageMap.begin(); it != ageMap.end(); ++it) {
        std::cout << it->first << " is " << it->second << " years old." << std::endl;
    }
}

3. 结合使用标准算法库

C++标准库提供了一系列通用算法，例如std::find, std::copy, std::sort等，这些算法可以和容器一起使用。

代码示例

使用std::find_if结合lambda表达式在std::map中查找满足特定条件的元素。

#include <iostream>
#include <map>
#include <algorithm>

int main() {
    std::map<std::string, int> ageMap = {{"Alice", 30}, {"Bob", 25}, {"Charlie", 35}};

    auto it = std::find_if(ageMap.begin(), ageMap.end(), [](const auto& pair) {
        return pair.second > 30;
    });

    if (it != ageMap.end()) {
        std::cout << it->first << " is older than 30." << std::endl;
    }
}

在这个例子中，使用了std::find_if来查找第一个年龄大于30的人。

关联容器高级特性

1. 自定义比较函数

自定义比较函数可以控制容器中元素的排序顺序。我们将以std::set为例，演示如何使用自定义比较函数。

代码示例

#include <iostream>
#include <set>
#include <string>

// 自定义比较函数
struct CompareLength {
    bool operator()(const std::string& a, const std::string& b) const {
        return a.length() < b.length();
    }
};

int main() {
    // 使用自定义比较函数初始化std::set
    std::set<std::string, CompareLength> words{"apple", "banana", "cherry"};

    // 遍历并打印元素
    for (const auto& word : words) {
        std::cout << word << " ";
    }
    std::cout << std::endl;

    return 0;
}

运行结果:

apple cherry banana

解释:

定义了一个自定义比较结构CompareLength，它比较两个字符串的长度。
使用CompareLength作为std::set的比较函数来初始化集合。这就让set可以根据字符串长度进行排序而不是使用字典顺序进行排序。
遍历并打印set，可以看到元素按照长度排序。

2. 容器的内存管理

关联容器的内存管理涉及元素的添加和删除，以及如何影响容器的内存使用。下面通过一个例子来展示std::map的内存管理。

代码示例

由于内存使用和管理在正常运行的程序中不容易直接观察，这里仅展示如何添加和删除元素。

#include <iostream>
#include <map>

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

    // 添加元素
    numbers[1] = "one";
    numbers[2] = "two";
    numbers[3] = "three";

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

    // 遍历并打印
    for (const auto& pair : numbers) {
        std::cout << pair.first << " => " << pair.second << std::endl;
    }

    return 0;
}

运行结果:

1 => one
3 => three

解释:

创建了一个std::map<int, std::string>。
向map中添加了三个键值对。
使用erase方法删除了键为2的元素。
遍历并打印剩余元素，可以看到键为2的元素已被删除。

3. 性能分析和优化

性能分析和优化通常涉及选择合适的容器类型、合理使用迭代器以及避免不必要的复制。针对性能优化的代码示例通常较为复杂，且需要特定的性能分析工具来观察效果。下面是一些通用的优化建议：

选择合适的容器：根据数据的使用模式选择最合适的容器。例如，频繁查找操作可能更适合使用std::unordered_map而不是std::map。

避免不必要的复制：使用引用或指针来访问容器中的元素，而不是创建它们的副本。

预分配内存：对于预知大小的数据集，预先分配足够的内存可以减少动态内存分配的开销。

使用有效的迭代器操作：尽量使用范围for循环或迭代器而不是通过键直接访问元素，尤其是在std::map和std::set中。关联容器应用案例

关联容器可以用于解决各种实际问题，从简单的数据存储到复杂的数据结构建构。这里我将提供一些具体的实际应用案例。

应用案例0：使用std::map进行词频统计

在这个例子中，使用std::map来统计一段文本中每个单词出现的频率。

代码示例

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

int main() {
    std::string text = "hello world hello cplusplus";
    std::map<std::string, int> wordCount;

    // 使用stringstream来分割单词
    std::stringstream ss(text);
    std::string word;
    while (ss >> word) {
        ++wordCount[word];
    }

    // 打印每个单词及其出现次数
    std::cout << "Word frequency:" << std::endl;
    for (const auto& pair : wordCount) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

运行结果:

Word frequency:
cplusplus: 1
hello: 2
world: 1

解释:

我们创建了一个std::map<std::string, int>来存储单词及其出现次数。

使用std::stringstream来分割字符串text中的单词。

遍历所有单词，每遇到一个单词就在wordCount中增加其计数。

最后，我们遍历wordCount并打印出每个单词及其出现次数。

当然，让我们探索更多关联容器的实际应用案例。这里提供不同场景下的几个示例，展示关联容器在解决各种问题中的多样性和实用性。

应用案例1：分组统计

在这个例子中，使用std::map来对一组人按年龄进行分组统计。

代码示例

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

int main() {
    struct Person {
        std::string name;
        int age;
    };

    std::vector<Person> people = {
        {"Alice", 30}, {"Bob", 25}, {"Charlie", 30}, {"Dave", 25}
    };

    std::map<int, std::vector<std::string>> ageGroups;

    for (const auto& person : people) {
        ageGroups[person.age].push_back(person.name);
    }

    // 打印分组
    for (const auto& group : ageGroups) {
        std::cout << "Age " << group.first << ": ";
        for (const auto& name : group.second) {
            std::cout << name << " ";
        }
        std::cout << std::endl;
    }

    return 0;
}

运行结果:

Age 25: Bob Dave 
Age 30: Alice Charlie

解释:

创建了一个Person结构体和一个Person类型的向量people。

使用std::map<int, std::vectorstd::string>来按年龄分组存储人名。

遍历people，将每个人根据年龄分组。

打印出按年龄分组的结果。

应用案例2：商品库存管理

在这个例子中，使用std::unordered_map来管理商品的库存数量。

代码示例

#incl#include <iostream>
#include <unordered_map>
#include <string>

int main() {
    std::unordered_map<std::string, int> stock = {
        {"apple", 50}, {"banana", 30}, {"orange", 20}
    };

    // 减少库存
    stock["banana"] -= 5;

    // 增加新商品
    stock["pear"] = 10;

    // 打印库存
    for (const auto& item : stock) {
        std::cout << item.first << ": " << item.second << std::endl;
    }

    return 0;
}

运行结果:

orange: 20
banana: 25
apple: 50
pear: 10

解释:

创建了一个std::unordered_map<std::string, int>来存储商品名和对应的库存数量。
对banana的库存进行了更新。
向库存中添加了一个新商品pear。
遍历并打印了当前的库存情况。

最佳实践和注意事项

1. 最佳实践

a. 选择合适的容器

根据数据操作的性质选择适当的容器。例如，如果需要有序数据，使用std::map或std::set；如果需要快速查找且不关心顺序，使用std::unordered_map或std::unordered_set。

为了说明如何根据数据操作的性质选择适当的容器，我将提供两个代码示例。第一个示例将使用std::map来处理有序数据，而第二个示例将使用std::unordered_map来展示快速查找的情况。

示例1: 使用 std::map 处理有序数据

代码示例

#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> orderedMap;
    orderedMap[3] = "C";
    orderedMap[1] = "A";
    orderedMap[2] = "B";

    // 打印map内容，观察其排序
    for (const auto& elem : orderedMap) {
        std::cout << elem.first << ": " << elem.second << std::endl;
    }

    return 0;
}

运行结果

1: A
2: B
3: C

解释

在这个例子中，std::map保持了键值对的有序状态（按照键排序）。
即使元素是按照3, 1, 2的顺序插入的，map在内部对它们进行了排序。

示例2: 使用 std::unordered_map 进行快速查找

代码示例

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, std::string> unorderedMap;
    unorderedMap[3] = "C";
    unorderedMap[1] = "A";
    unorderedMap[2] = "B";

    // 快速查找键为2的元素
    if (unorderedMap.find(2) != unorderedMap.end()) {
        std::cout << "Found: " << unorderedMap[2] << std::endl;
    }

    return 0;
}

运行结果

Found: B

解释

std::unordered_map提供了更快的查找性能，但不保证元素的顺序。

在这个例子中，快速找到了键为2的元素，但如果打印整个unordered_map，会发现元素的顺序是不确定的。

通过比较这两个例子，可以看到std::map适用于需要维持元素顺序的场景，而std::unordered_map则适用于需要快速访问但不关心元素顺序的情况。

b. 使用合适的迭代器

根据容器类型选择合适的迭代器。例如，std::map和std::set使用双向迭代器，而std::unordered_map和std::unordered_set使用前向迭代器。

示例1: 使用 std::map 的双向迭代器代码示例

#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> orderedMap = {{1, "A"}, {2, "B"}, {3, "C"}};

    // 使用双向迭代器遍历map
    std::cout << "Forward traversal: ";
    for (auto it = orderedMap.begin(); it != orderedMap.end(); ++it) {
        std::cout << it->first << " ";
    }

    // 使用双向迭代器反向遍历map
    std::cout << "\nBackward traversal: ";
    for (auto it = orderedMap.rbegin(); it != orderedMap.rend(); ++it) {
        std::cout << it->first << " ";
    }

    return 0;
}

运行结果

Forward traversal: 1 2 3 
Backward traversal: 3 2 1

解释

std::map 提供双向迭代器，允许正向和反向遍历。
使用普通迭代器begin()和end()进行正向遍历。
使用反向迭代器rbegin()和rend()进行反向遍历。

示例2: 使用 std::unordered_set 的前向迭代器

代码示例

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> unorderedSet = {3, 1, 2};

    // 使用前向迭代器遍历unordered_set
    std::cout << "Elements in unordered_set: ";
    for (auto it = unorderedSet.begin(); it != unorderedSet.end(); ++it) {
        std::cout << *it << " ";
    }

    return 0;
}

运行结果

Elements in unordered_set: 1 2 3

解释

std::unordered_set 提供前向迭代器，只支持正向遍历。

使用begin()和end()进行遍历，但不保证元素的顺序。

通过这两个示例，我们可以看到不同类型的关联容器（有序和无序）提供了不同类型的迭代器。理解并根据容器的特性选择合适的迭代器是关键，这有助于编写高效且符合容器设计的代码。

c. 有效地使用自定义比较函数

当使用自定义比较函数时，确保它们的行为是一致且高效的。

示例：自定义比较函数对字符串进行排序

代码示例

#include <iostream>
#include <set>
#include <string>

// 自定义比较函数
struct LengthCompare {
    bool operator()(const std::string& a, const std::string& b) const {
        return a.length() < b.length();
    }
};

int main() {
    // 使用自定义比较函数的std::set
    std::set<std::string, LengthCompare> strings;

    // 添加字符串
    strings.insert("Zebra");
    strings.insert("Apple");
    strings.insert("Orange");

    // 遍历并打印set内容
    for (const auto& str : strings) {
        std::cout << str << " ";
    }

    return 0;
}

运行结果

Zebra Apple Orange

解释

定义了一个自定义比较结构LengthCompare，它按字符串的长度进行比较。

创建了一个std::set，使用LengthCompare作为其排序标准。

添加了几个字符串到集合中。尽管按照字典顺序，“Apple”应该在“Zebra”之前，但由于我们使用长度进行排序，所以“Zebra”（长度为5）排在了“Apple”（长度为5）之前。

遍历并打印出集合中的字符串，可以看到它们是按照长度而非字典顺序排序的。

d. 避免不必要的复制

在可能的情况下，使用引用或指针来避免复制大型数据结构。

示例：使用引用避免复制

假设有一个包含大型数据的std::map，最好通过引用访问和修改这些数据，而不是复制它们。

代码示例

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

class LargeData {
public:
    // 假设这是一个包含大量数据的类
    LargeData() { data = "This is some large amount of data"; }
    void updateData(const std::string& newData) { data = newData; }
    std::string getData() const { return data; }

private:
    std::string data;
};

int main() {
    std::map<int, LargeData> dataMap;

    // 向map中添加数据
    dataMap[1];
    dataMap[2];

    // 使用引用来访问和修改数据，避免复制
    LargeData& dataRef = dataMap[1];
    dataRef.updateData("Updated large data");

    // 验证数据是否更新
    std::cout << "Data in key 1: " << dataMap[1].getData() << std::endl;

    return 0;
}

运行结果

Data in key 1: Updated large data

解释

定义了一个名为LargeData的类，假设它包含大量数据。

创建了一个std::map<int, LargeData>，将整数映射到LargeData对象。

向map中添加数据时，并没有进行复制操作。

通过引用dataRef访问和修改dataMap中的LargeData对象。这样做避免了将整个LargeData对象从map中复制出来的开销。

最后打印出更新后的数据，验证我们的修改成功应用于map中的对象。

2. 常见问题及解决方法

a. 性能问题

问题：使用std::map或std::set时出现性能下降。

解决方法：考虑使用std::unordered_map或std::unordered_set，它们提供更快的查找时间，但不保证元素顺序。

b. 错误的迭代器使用

问题：在遍历容器时修改了容器，导致迭代器失效。

解决方法：避免在遍历容器时直接修改容器内容。如果需要修改，先记录需要修改的元素，遍历结束后再进行修改。

c. 自定义比较函数的不当使用

问题：自定义比较函数导致的逻辑错误或性能问题。

解决方法：确保自定义比较函数的逻辑正确且高效。比较函数需要是严格弱排序。

d. 容器中元素的拷贝

问题：在插入大型对象时造成性能问题。

解决方法：使用移动语义或存储指向对象的指针而非对象本身。

c++关联容器详细介绍

关联容器的简介

1. std::set

2. std::multiset

3. std::map

4. std::multimap

5. std::unordered_set 和 std::unordered_map

关联容器的迭代器

1. 迭代器基础

2. 使用迭代器遍历关联容器

3. 结合使用标准算法库

关联容器高级特性

1. 自定义比较函数

2. 容器的内存管理

3. 性能分析和优化

最佳实践和注意事项

1. 最佳实践

2. 常见问题及解决方法

热门文章

最新文章

相关课程

相关电子书

相关实验场景

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

c++关联容器详细介绍

关联容器的简介

1. std::set

2. std::multiset

3. std::map

4. std::multimap

5. std::unordered_set 和 std::unordered_map

关联容器的迭代器

1. 迭代器基础

2. 使用迭代器遍历关联容器

3. 结合使用标准算法库

关联容器高级特性

1. 自定义比较函数

2. 容器的内存管理

3. 性能分析和优化

最佳实践和注意事项

1. 最佳实践

2. 常见问题及解决方法

热门文章

最新文章

相关课程

相关电子书

相关实验场景