求C++双索引有序唯一关系的std风格双向映射容器实现方案

Hey there! Let's tackle this problem step by step. You're asking for a bidirectional container that combines ordered collection behavior, hash-map-level lookup speed, and standard library-style conventions (like iterators). Here's a practical, efficient solution tailored to your needs:

Core Design Breakdown #

First, let's align on your requirements to make sure we cover every base:

• Bidirectional mapping between unique, hashable types T and U
• Ordered sequence of (T, U) pairs (with reproducible iteration order)
• O(1) lookup performance (matching std::unordered_map) for both T → U and U → T
• Std-compliant interface with iterators and familiar methods

Solution Implementation #

The core idea is to combine three internal components: two hash maps for fast bidirectional lookups, and an ordered container to preserve pair order. We'll wrap these in a class that feels just like a standard library container.

Full Code Example #

#include <unordered_map>
#include <vector>
#include <stdexcept>
#include <utility>
#include <algorithm>

template <typename T, typename U>
class bidirectional_map {
public:
    // Standard library-style iterator types
    using iterator = typename std::vector<std::pair<T, U>>::iterator;
    using const_iterator = typename std::vector<std::pair<T, U>>::const_iterator;
    using value_type = std::pair<T, U>;

    // Insert a new (T, U) pair (throws if either value already exists)
    void insert(const value_type& pair) {
        if (forward_map.contains(pair.first) || reverse_map.contains(pair.second)) {
            throw std::invalid_argument("Duplicate key or value detected");
        }
        forward_map[pair.first] = pair.second;
        reverse_map[pair.second] = pair.first;
        ordered_pairs.push_back(pair);
    }

    // Insert via move semantics for better efficiency
    void insert(value_type&& pair) {
        if (forward_map.contains(pair.first) || reverse_map.contains(pair.second)) {
            throw std::invalid_argument("Duplicate key or value detected");
        }
        auto moved_u = std::move(pair.second);
        auto moved_t = std::move(pair.first);
        forward_map[moved_t] = moved_u;
        reverse_map[moved_u] = moved_t;
        ordered_pairs.emplace_back(std::move(moved_t), std::move(moved_u));
    }

    // O(1) lookup: T → U (throws if T doesn't exist)
    U& operator[](const T& t) {
        auto it = forward_map.find(t);
        if (it == forward_map.end()) {
            throw std::out_of_range("Key not found in forward map");
        }
        return it->second;
    }

    // O(1) lookup: U → T (throws if U doesn't exist)
    T& operator[](const U& u) {
        auto it = reverse_map.find(u);
        if (it == reverse_map.end()) {
            throw std::out_of_range("Value not found in reverse map");
        }
        return it->second;
    }

    // Const versions of lookup methods
    const U& operator[](const T& t) const {
        auto it = forward_map.find(t);
        if (it == forward_map.end()) {
            throw std::out_of_range("Key not found in forward map");
        }
        return it->second;
    }

    const T& operator[](const U& u) const {
        auto it = reverse_map.find(u);
        if (it == reverse_map.end()) {
            throw std::out_of_range("Value not found in reverse map");
        }
        return it->second;
    }

    // Check if a T exists in the map
    bool contains(const T& t) const {
        return forward_map.contains(t);
    }

    // Check if a U exists in the map
    bool contains(const U& u) const {
        return reverse_map.contains(u);
    }

    // Standard iterators for ordered traversal
    iterator begin() noexcept { return ordered_pairs.begin(); }
    const_iterator begin() const noexcept { return ordered_pairs.begin(); }
    const_iterator cbegin() const noexcept { return ordered_pairs.cbegin(); }

    iterator end() noexcept { return ordered_pairs.end(); }
    const_iterator end() const noexcept { return ordered_pairs.end(); }
    const_iterator cend() const noexcept { return ordered_pairs.cend(); }

    // Erase a pair by T (O(n) for ordered container removal; swap to list for O(1) erases)
    void erase(const T& t) {
        auto forward_it = forward_map.find(t);
        if (forward_it == forward_map.end()) return;

        U u = forward_it->second;
        forward_map.erase(forward_it);
        reverse_map.erase(u);

        // Remove from ordered pairs
        auto pair_it = std::find_if(ordered_pairs.begin(), ordered_pairs.end(),
            [&t](const auto& p) { return p.first == t; });
        if (pair_it != ordered_pairs.end()) {
            ordered_pairs.erase(pair_it);
        }
    }

    // Erase a pair by U
    void erase(const U& u) {
        auto reverse_it = reverse_map.find(u);
        if (reverse_it == reverse_map.end()) return;

        T t = reverse_it->second;
        reverse_map.erase(reverse_it);
        forward_map.erase(t);

        // Remove from ordered pairs
        auto pair_it = std::find_if(ordered_pairs.begin(), ordered_pairs.end(),
            [&u](const auto& p) { return p.second == u; });
        if (pair_it != ordered_pairs.end()) {
            ordered_pairs.erase(pair_it);
        }
    }

    // Clear all elements
    void clear() noexcept {
        forward_map.clear();
        reverse_map.clear();
        ordered_pairs.clear();
    }

    // Get the number of elements
    size_t size() const noexcept {
        return ordered_pairs.size();
    }

    // Check if container is empty
    bool empty() const noexcept {
        return ordered_pairs.empty();
    }

    // Custom sort method to reorder pairs (preserves lookup speed)
    template <typename Compare>
    void sort(Compare comp) {
        std::sort(ordered_pairs.begin(), ordered_pairs.end(), comp);
    }

private:
    std::unordered_map<T, U> forward_map;   // T → U lookups
    std::unordered_map<U, T> reverse_map;   // U → T lookups
    std::vector<std::pair<T, U>> ordered_pairs; // Preserves insertion order (or custom sorted order)
};

Key Features Explained #

• O(1) Lookups: The two std::unordered_map instances ensure both directions of lookup are constant time, matching std::unordered_map performance as requested.
• Ordered Iteration: The std::vector stores pairs in insertion order by default, so iterating from begin() to end() will always reproduce the same sequence. Use the sort() method if you need a custom order (like sorted by T or U).
• Strict Uniqueness: The insert() method checks for existing T or U values before adding a new pair, enforcing your requirement that all values of T and U are unique.
• Std-Style Interface: We've included standard iterators, size(), empty(), clear(), and contains() methods to match the feel of standard library containers.

Customization Tips #

• Faster Erases: If you need O(1) erase operations instead of O(n), replace the std::vector with a std::list for ordered_pairs. Adjust the erase logic to use list iterators, and lookups will still stay O(1).
• Default Insertion: If you want to support operator[] for inserting new pairs (like std::unordered_map), you'll need to handle uniqueness carefully—creating a default U for a new T could conflict with existing U values. The example uses a strict insert() method to avoid accidental duplicates, but you could add a safe version if needed.

Usage Example #

#include <iostream>

int main() {
    bidirectional_map<int, std::string> bmap;
    bmap.insert({1, "one"});
    bmap.insert({2, "two"});
    bmap.insert({3, "three"});

    // O(1) lookups
    std::cout << bmap[1] << std::endl; // Outputs "one"
    std::cout << bmap["two"] << std::endl; // Outputs 2

    // Ordered iteration
    for (const auto& pair : bmap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    // Outputs in insertion order: 1: one, 2: two, 3: three

    // Sort by string value
    bmap.sort([](const auto& a, const auto& b) {
        return a.second < b.second;
    });

    for (const auto& pair : bmap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }
    // Outputs sorted: 1: one, 3: three, 2: two

    bmap.erase(2);
    std::cout << bmap.size() << std::endl; // Outputs 2

    return 0;
}

内容的提问来源于stack exchange，提问作者Glen Fletcher