MK
摩柯社区 - 一个极简的技术知识社区
AI 面试

C++关联容器与数据检索策略

2022-07-117.1k 阅读

C++关联容器概述

在C++编程中，关联容器是一种特殊类型的容器，它提供了高效的数据检索功能。与序列容器（如vector和list）不同，关联容器存储的元素是按照特定的键（key）来组织的，而不是按照元素的插入顺序。这种组织方式使得在关联容器中查找元素变得非常高效，时间复杂度通常为对数级，相比于序列容器的线性查找时间复杂度，这是一个巨大的性能提升。

C++标准库提供了两种主要的关联容器类型：map和set，以及它们对应的无序版本unordered_map和unordered_set。

map容器

map是一种键值对（key - value）的集合，其中每个键都是唯一的。map中的元素是按照键的顺序存储的，默认情况下是按照升序排列。这意味着在map中查找元素时，可以利用其有序性进行二分查找，从而实现高效的检索。

下面是一个简单的map使用示例：

#include <iostream>
#include <map>

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

    // 插入元素
    myMap.insert({1, "one"});
    myMap.insert({2, "two"});
    myMap.insert({3, "three"});

    // 通过键访问值
    std::cout << "Value for key 2: " << myMap[2] << std::endl;

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

    return 0;
}

在上述代码中，我们首先创建了一个map对象myMap，它的键是int类型，值是std::string类型。然后通过insert方法插入了几个键值对。可以通过键直接访问对应的值，如myMap[2]。最后，通过范围for循环遍历map，输出所有的键值对。

set容器

set容器与map类似，但它只存储键，不存储对应的值（实际上可以看作值与键相同）。set中的元素也是唯一的，并且按照升序排列。set适用于需要快速判断某个元素是否存在的场景。

以下是set的使用示例：

#include <iostream>
#include <set>

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

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

    // 检查元素是否存在
    if (mySet.find(2) != mySet.end()) {
        std::cout << "Element 2 exists in the set." << std::endl;
    }

    // 遍历set
    for (const auto& element : mySet) {
        std::cout << element << std::endl;
    }

    return 0;
}

在这个示例中，我们创建了一个set对象mySet，插入了几个整数。通过find方法可以检查某个元素是否存在于set中。最后通过范围for循环遍历set，输出所有元素。

无序关联容器

除了有序的map和set，C++还提供了无序版本的关联容器unordered_map和unordered_set。它们的主要区别在于元素的存储顺序是无序的，这是通过哈希表（hash table）来实现的。无序关联容器在大多数情况下提供了更快的查找、插入和删除操作，平均时间复杂度为常数级O(1)，但在最坏情况下可能退化为线性时间复杂度O(n)。

unordered_map示例

#include <iostream>
#include <unordered_map>

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

    // 插入元素
    myUnorderedMap.insert({1, "one"});
    myUnorderedMap.insert({2, "two"});
    myUnorderedMap.insert({3, "three"});

    // 通过键访问值
    std::cout << "Value for key 2: " << myUnorderedMap[2] << std::endl;

    // 遍历unordered_map
    for (const auto& pair : myUnorderedMap) {
        std::cout << pair.first << " : " << pair.second << std::endl;
    }

    return 0;
}

unordered_set示例

#include <iostream>
#include <unordered_set>

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

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

    // 检查元素是否存在
    if (myUnorderedSet.find(2) != myUnorderedSet.end()) {
        std::cout << "Element 2 exists in the unordered set." << std::endl;
    }

    // 遍历unordered_set
    for (const auto& element : myUnorderedSet) {
        std::cout << element << std::endl;
    }

    return 0;
}

在这两个示例中，unordered_map和unordered_set的使用方式与对应的有序版本类似，但由于其无序性，遍历时元素的顺序可能与插入顺序不同。

关联容器的数据检索策略

基于键的查找

关联容器最核心的功能就是基于键进行高效的查找。在有序关联容器map和set中，查找操作利用了元素的有序性，通常采用二分查找算法。二分查找的时间复杂度为O(log n)，其中n是容器中元素的数量。这使得在大规模数据集中查找元素时，有序关联容器能够快速定位到目标元素。

例如，在map中查找一个键值对：

#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> myMap = {{1, "one"}, {2, "two"}, {3, "three"}};

    auto it = myMap.find(2);
    if (it != myMap.end()) {
        std::cout << "Found: " << it->second << std::endl;
    } else {
        std::cout << "Not found." << std::endl;
    }

    return 0;
}

在上述代码中，通过find方法查找键为2的元素。如果找到，find方法返回一个指向该元素的迭代器；如果未找到，则返回end()迭代器。

在无序关联容器unordered_map和unordered_set中，查找操作基于哈希表。哈希表通过将键映射到一个哈希值，然后根据哈希值快速定位到存储该键值对（或键）的位置。理想情况下，哈希表的查找操作平均时间复杂度为O(1)，这使得无序关联容器在查找频繁的场景下表现非常出色。

例如，在unordered_set中查找一个元素：

#include <iostream>
#include <unordered_set>

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

    auto it = myUnorderedSet.find(2);
    if (it != myUnorderedSet.end()) {
        std::cout << "Found." << std::endl;
    } else {
        std::cout << "Not found." << std::endl;
    }

    return 0;
}

同样，通过find方法进行查找，根据返回的迭代器判断元素是否存在。

范围查找

有序关联容器map和set还支持范围查找。由于元素是有序存储的，可以利用这一特性查找满足一定条件的元素范围。例如，查找所有键大于某个值且小于另一个值的元素。

下面是一个在map中进行范围查找的示例：

#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> myMap = {{1, "one"}, {2, "two"}, {3, "three"}, {4, "four"}, {5, "five"}};

    auto lowerIt = myMap.lower_bound(2);
    auto upperIt = myMap.upper_bound(4);

    for (auto it = lowerIt; it != upperIt; ++it) {
        std::cout << it->first << " : " << it->second << std::endl;
    }

    return 0;
}

在上述代码中，lower_bound方法返回一个迭代器，指向键大于或等于指定值的第一个元素；upper_bound方法返回一个迭代器，指向键大于指定值的第一个元素。通过这两个方法，我们可以获取到键在[2, 4)范围内的所有元素。

自定义比较函数

在默认情况下，有序关联容器map和set使用<运算符对元素进行比较。但在某些情况下，我们可能需要自定义比较逻辑。例如，当键是自定义类型时，或者需要按照不同于默认的顺序进行排序。

对于map和set，可以通过在构造函数中传递一个比较函数对象来实现自定义比较。下面是一个自定义比较函数的示例，用于按照降序排列set中的整数：

#include <iostream>
#include <set>

struct CompareDescending {
    bool operator()(int a, int b) const {
        return a > b;
    }
};

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

    mySet.insert(1);
    mySet.insert(2);
    mySet.insert(3);

    for (const auto& element : mySet) {
        std::cout << element << std::endl;
    }

    return 0;
}

在上述代码中，我们定义了一个CompareDescending结构体，它重载了()运算符，实现了降序比较逻辑。然后在创建set对象时，将这个结构体作为模板参数传递，使得set中的元素按照降序排列。

哈希函数定制

对于无序关联容器unordered_map和unordered_set，哈希函数的选择至关重要。默认情况下，C++标准库为基本数据类型提供了合理的哈希函数。但当键是自定义类型时，我们需要自定义哈希函数。

下面是一个自定义哈希函数的示例，用于unordered_set存储自定义结构体：

#include <iostream>
#include <unordered_set>
#include <string>

struct Point {
    int x;
    int y;
};

namespace std {
    template<>
    struct hash<Point> {
        std::size_t operator()(const Point& p) const {
            return std::hash<int>()(p.x) ^ std::hash<int>()(p.y);
        }
    };
}

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

    Point p1 = {1, 2};
    Point p2 = {3, 4};

    myUnorderedSet.insert(p1);
    myUnorderedSet.insert(p2);

    for (const auto& point : myUnorderedSet) {
        std::cout << "(" << point.x << ", " << point.y << ")" << std::endl;
    }

    return 0;
}

在上述代码中，我们定义了一个Point结构体。为了能在unordered_set中存储Point类型的对象，我们在std命名空间中特化了hash模板，为Point类型定义了一个哈希函数。这个哈希函数通过异或x和y的哈希值来生成唯一的哈希值。

关联容器的性能分析

插入操作性能

在有序关联容器map和set中，插入操作的时间复杂度为O(log n)。这是因为插入元素时需要找到合适的位置以保持容器的有序性，这个查找位置的过程类似于二分查找。例如，在map中插入一个新的键值对：

#include <iostream>
#include <map>

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

    for (int i = 0; i < 100000; ++i) {
        myMap.insert({i, "value"});
    }

    return 0;
}

在上述代码中，每次插入操作的时间复杂度为O(log n)，其中n是插入元素后map中的元素数量。随着元素数量的增加，插入操作的时间会逐渐增加，但增长速度相对较慢。

在无序关联容器unordered_map和unordered_set中，插入操作的平均时间复杂度为O(1)。这是因为哈希表可以快速定位到插入位置。然而，在最坏情况下，当哈希冲突严重时，插入操作的时间复杂度可能退化为O(n)。例如，在unordered_set中插入元素：

#include <iostream>
#include <unordered_set>

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

    for (int i = 0; i < 100000; ++i) {
        myUnorderedSet.insert(i);
    }

    return 0;
}

在一般情况下，这个插入过程非常快，但如果哈希函数设计不合理，导致大量元素哈希到同一个位置，性能就会急剧下降。

删除操作性能

有序关联容器map和set的删除操作时间复杂度也为O(log n)。删除元素时，首先需要通过二分查找找到要删除的元素，然后将其从容器中移除。例如，在set中删除一个元素：

#include <iostream>
#include <set>

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

    mySet.erase(3);

    for (const auto& element : mySet) {
        std::cout << element << std::endl;
    }

    return 0;
}

在上述代码中，erase方法首先通过二分查找找到键为3的元素，然后将其删除，整个操作的时间复杂度为O(log n)。

无序关联容器unordered_map和unordered_set的删除操作平均时间复杂度为O(1)。同样，在最坏情况下，由于哈希冲突，时间复杂度可能退化为O(n)。例如，在unordered_map中删除一个键值对：

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, std::string> myUnorderedMap = {{1, "one"}, {2, "two"}, {3, "three"}};

    myUnorderedMap.erase(2);

    for (const auto& pair : myUnorderedMap) {
        std::cout << pair.first << " : " << pair.second << std::endl;
    }

    return 0;
}

在正常情况下，删除操作可以快速定位并移除目标元素，但如果哈希冲突严重，性能会受到影响。

查找操作性能

如前面所述，有序关联容器map和set的查找操作时间复杂度为O(log n)，这是基于二分查找的特性。例如，在map中查找一个键值对：

#include <iostream>
#include <map>

int main() {
    std::map<int, std::string> myMap = {{1, "one"}, {2, "two"}, {3, "three"}};

    auto it = myMap.find(2);
    if (it != myMap.end()) {
        std::cout << "Found: " << it->second << std::endl;
    } else {
        std::cout << "Not found." << std::endl;
    }

    return 0;
}

每次查找操作的时间复杂度为O(log n)，即使在元素数量非常大的情况下，查找速度仍然相对较快。

无序关联容器unordered_map和unordered_set的查找操作平均时间复杂度为O(1)，这是哈希表的优势所在。例如，在unordered_set中查找一个元素：

#include <iostream>
#include <unordered_set>

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

    auto it = myUnorderedSet.find(2);
    if (it != myUnorderedSet.end()) {
        std::cout << "Found." << std::endl;
    } else {
        std::cout << "Not found." << std::endl;
    }

    return 0;
}

在理想情况下，查找操作可以瞬间完成，但如果哈希函数不好，导致大量冲突，查找时间复杂度会变为O(n)。

关联容器的应用场景

字典应用

map容器非常适合实现字典功能。例如，在一个程序中需要将单词映射到其定义，map就可以很好地满足这个需求。每个单词作为键，对应的定义作为值。

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

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

    dictionary["apple"] = "A round, red or green fruit.";
    dictionary["banana"] = "A long, yellow fruit.";

    std::string word = "apple";
    auto it = dictionary.find(word);
    if (it != dictionary.end()) {
        std::cout << "Definition of " << word << ": " << it->second << std::endl;
    } else {
        std::cout << "Word not found in dictionary." << std::endl;
    }

    return 0;
}

在上述代码中，我们创建了一个map来模拟字典，通过单词查找其定义。

集合运算

set容器常用于集合运算，如求交集、并集和差集。例如，假设有两个集合，需要求出它们的交集：

#include <iostream>
#include <set>

int main() {
    std::set<int> set1 = {1, 2, 3, 4, 5};
    std::set<int> set2 = {3, 4, 5, 6, 7};

    std::set<int> intersection;
    std::set_intersection(set1.begin(), set1.end(), set2.begin(), set2.end(), std::inserter(intersection, intersection.begin()));

    for (const auto& element : intersection) {
        std::cout << element << std::endl;
    }

    return 0;
}

在上述代码中，我们使用std::set_intersection算法来计算两个set的交集，并将结果存储在一个新的set中。

统计词频

unordered_map非常适合统计词频。例如，在一段文本中统计每个单词出现的次数：

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

int main() {
    std::string text = "apple banana apple orange banana apple";
    std::unordered_map<std::string, int> wordCount;

    std::istringstream iss(text);
    std::string word;
    while (iss >> word) {
        ++wordCount[word];
    }

    for (const auto& pair : wordCount) {
        std::cout << pair.first << " : " << pair.second << " times" << std::endl;
    }

    return 0;
}

在上述代码中，我们通过unordered_map来统计每个单词在文本中出现的次数。由于unordered_map的快速查找和插入特性，这个操作可以高效完成。

缓存实现

无序关联容器unordered_map常被用于实现缓存。例如，在一个函数调用频繁且计算结果不变的场景下，可以将计算结果缓存起来，避免重复计算。

#include <iostream>
#include <unordered_map>

int expensiveCalculation(int x) {
    // 模拟一个复杂的计算
    return x * x * x;
}

std::unordered_map<int, int> cache;
int cachedCalculation(int x) {
    auto it = cache.find(x);
    if (it != cache.end()) {
        return it->second;
    } else {
        int result = expensiveCalculation(x);
        cache[x] = result;
        return result;
    }
}

int main() {
    int value = 5;
    std::cout << "Result: " << cachedCalculation(value) << std::endl;
    std::cout << "Result (from cache): " << cachedCalculation(value) << std::endl;

    return 0;
}

在上述代码中，cachedCalculation函数首先检查缓存中是否已经有计算结果，如果有则直接返回；如果没有，则调用expensiveCalculation进行计算，并将结果存入缓存。

关联容器的选择与优化

选择合适的关联容器

在选择关联容器时，需要考虑以下几个因素：

  1. 查找性能：如果需要频繁查找元素，并且对平均查找性能要求极高，无序关联容器unordered_map和unordered_set通常是更好的选择，因为它们的平均查找时间复杂度为O(1)。但如果需要支持范围查找或者元素需要有序存储，那么有序关联容器map和set更为合适，其查找时间复杂度为O(log n)。
  2. 插入和删除性能：无序关联容器在平均情况下插入和删除操作的时间复杂度为O(1)，但在最坏情况下可能退化为O(n)。有序关联容器的插入和删除时间复杂度始终为O(log n)。如果插入和删除操作频繁，并且对最坏情况性能有要求，有序关联容器可能更可靠。
  3. 元素顺序：如果需要元素按照特定顺序存储（如升序或降序），那么必须使用有序关联容器map和set。如果元素顺序无关紧要，无序关联容器可以提供更好的性能。
  4. 内存占用：一般来说，无序关联容器由于哈希表的实现，可能会占用更多的内存空间。如果内存空间有限，需要考虑这一点。

优化关联容器的使用

  1. 选择合适的哈希函数：对于无序关联容器，哈希函数的质量直接影响性能。一个好的哈希函数应该尽可能均匀地将键分布到哈希表中，减少哈希冲突。当使用自定义类型作为键时，务必精心设计哈希函数。
  2. 预分配内存：在有序关联容器中，虽然它们会根据需要自动调整大小，但如果能够提前知道大概需要存储的元素数量，可以通过reserve方法预分配内存，避免频繁的内存重新分配操作，提高性能。
  3. 避免不必要的拷贝：在插入元素到关联容器时，尽量使用emplace方法代替insert方法。emplace方法直接在容器中构造对象，避免了不必要的拷贝和移动操作，提高效率。

例如，在map中使用emplace插入元素：

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

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

    myMap.emplace(1, "one");

    return 0;
}

在上述代码中，emplace方法直接在map中构造了键值对，减少了一次拷贝操作。

通过合理选择和优化关联容器的使用，可以显著提高程序的性能和效率，使其在处理大量数据和频繁的数据检索操作时表现更加出色。无论是开发高效的算法，还是构建大型的应用程序，深入理解和熟练运用关联容器都是非常重要的。