C++11無序關聯容器有哪幾種

C++11無序關聯容器有哪幾種

C++11標準引入了無序關聯容器（Unordered Associative Containers），這些容器基于哈希表實現，提供了平均常數時間復雜度的插入、刪除和查找操作。與有序關聯容器（如std::map和std::set）不同，無序關聯容器不維護元素的順序，而是通過哈希函數將元素映射到桶中。C++11標準中定義了四種無序關聯容器，分別是std::unordered_set、std::unordered_multiset、std::unordered_map和std::unordered_multimap。

1. std::unordered_set

std::unordered_set是一個無序集合，它存儲唯一的元素。與std::set不同，std::unordered_set不保證元素的順序，而是通過哈希函數將元素映射到桶中。std::unordered_set的主要特點包括：

• 唯一性：std::unordered_set中的元素是唯一的，不允許重復。
• 哈希函數：元素通過哈希函數映射到桶中，哈希函數可以通過模板參數自定義。
• 平均常數時間復雜度：插入、刪除和查找操作的平均時間復雜度為O(1)。

示例代碼

#include <unordered_set>
#include <iostream>

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

    uset.insert(6);
    uset.erase(3);

    for (const auto& elem : uset) {
        std::cout << elem << " ";
    }
    return 0;
}

2. std::unordered_multiset

std::unordered_multiset是一個無序多重集合，它允許存儲重復的元素。與std::unordered_set類似，std::unordered_multiset也不保證元素的順序，而是通過哈希函數將元素映射到桶中。std::unordered_multiset的主要特點包括：

• 允許重復：std::unordered_multiset中的元素可以重復。
• 哈希函數：元素通過哈希函數映射到桶中，哈希函數可以通過模板參數自定義。
• 平均常數時間復雜度：插入、刪除和查找操作的平均時間復雜度為O(1)。

示例代碼

#include <unordered_set>
#include <iostream>

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

    umset.insert(6);
    umset.erase(2);

    for (const auto& elem : umset) {
        std::cout << elem << " ";
    }
    return 0;
}

3. std::unordered_map

std::unordered_map是一個無序映射容器，它存儲鍵值對。與std::map不同，std::unordered_map不保證鍵值對的順序，而是通過哈希函數將鍵映射到桶中。std::unordered_map的主要特點包括：

• 鍵值對：std::unordered_map存儲鍵值對，鍵是唯一的。
• 哈希函數：鍵通過哈希函數映射到桶中，哈希函數可以通過模板參數自定義。
• 平均常數時間復雜度：插入、刪除和查找操作的平均時間復雜度為O(1)。

示例代碼

#include <unordered_map>
#include <iostream>

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

    umap.insert({"date", 4});
    umap.erase("banana");

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

4. std::unordered_multimap

std::unordered_multimap是一個無序多重映射容器，它允許存儲多個具有相同鍵的鍵值對。與std::unordered_map類似，std::unordered_multimap也不保證鍵值對的順序，而是通過哈希函數將鍵映射到桶中。std::unordered_multimap的主要特點包括：

• 允許重復鍵：std::unordered_multimap中的鍵可以重復，允許多個鍵值對具有相同的鍵。
• 哈希函數：鍵通過哈希函數映射到桶中，哈希函數可以通過模板參數自定義。
• 平均常數時間復雜度：插入、刪除和查找操作的平均時間復雜度為O(1)。

示例代碼

#include <unordered_map>
#include <iostream>

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

    ummap.insert({"banana", 4});
    ummap.erase("apple");

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

總結

C++11標準引入了四種無序關聯容器：std::unordered_set、std::unordered_multiset、std::unordered_map和std::unordered_multimap。這些容器基于哈希表實現，提供了平均常數時間復雜度的插入、刪除和查找操作。與有序關聯容器不同，無序關聯容器不維護元素的順序，而是通過哈希函數將元素映射到桶中。根據具體需求，可以選擇合適的無序關聯容器來存儲和操作數據。