BidirectionalMap.h

Go to the documentation of this file.

#pragma once
#include <unordered_map>
#include <stdexcept>
#include <utility>
 
template <typename T, typename U>
class BidirectionalMap
{
public:
    // The Side class is a nested template, providing a read-only view.
    // It does NOT have an 'other' pointer, as bidirectional logic is handled by the parent.
    template <typename SideKey, typename SideValue>
    class Side
    {
        // Grant BidirectionalMap full access to Side's private members (specifically 'map')
        // This is crucial for BidirectionalMap to manage consistency across both directions.
        friend class BidirectionalMap<T, U>;
 
    public:
        Side() = default;
 
        const SideValue& at(const SideKey& key) const {
            auto it = map.find(key);
            if (it == map.end()) {
                throw std::out_of_range("Key not found in BidirectionalMap::Side::at");
            }
            return it->second;
        }
 
        bool contains(const SideKey& key) const {
            return map.count(key) > 0;
        }
 
        size_t size() const {
            return map.size();
        }
 
        bool empty() const {
            return map.empty();
        }
 
        typename std::unordered_map<SideKey, SideValue>::const_iterator begin() const { return map.begin(); }
        typename std::unordered_map<SideKey, SideValue>::const_iterator end() const { return map.end(); }
 
    private:
        std::unordered_map<SideKey, SideValue> map;
 
        void clear_map_only() {
            map.clear();
        }
    };
 
    using LeftSideType = Side<T, U>;  // Maps T -> U
    using RightSideType = Side<U, T>; // Maps U -> T
 
    BidirectionalMap() = default;
 
    LeftSideType& get_left() { return left; }
    const LeftSideType& get_left() const { return left; }
 
    RightSideType& get_right() { return right; }
    const RightSideType& get_right() const { return right; }
 
    void insert(const T& key, const U& value) {
        auto it_left_key = left.map.find(key);
        if (it_left_key != left.map.end()) {
            U old_value = std::move(it_left_key->second);
            left.map.erase(it_left_key);
            right.map.erase(old_value);
        }
 
        auto it_right_value = right.map.find(value);
        if (it_right_value != right.map.end()) {
            T old_key = std::move(it_right_value->second);
            right.map.erase(it_right_value);
            left.map.erase(old_key);
        }
 
        left.map.insert_or_assign( key, value );
        right.map.insert_or_assign( value, key );
    }
 
    template <typename KT, typename KU>
    void emplace(KT&& key, KU&& value) {
        auto it_left_key = left.map.find(key);
        if (it_left_key != left.map.end()) {
            right.map.erase(it_left_key->second);
            left.map.erase(it_left_key);
        }
 
        auto it_right_value = right.map.find(value);
        if (it_right_value != right.map.end()) {
            left.map.erase(it_right_value->second);
            right.map.erase(it_right_value);
        }
 
        left.map.emplace(key, value);
        right.map.emplace(std::forward<KU>(value), std::forward<KT>(key));
    }
 
    void remove_left(const T& key) {
        auto it_left = left.map.find(key);
        if (it_left != left.map.end()) {
            U value = it_left->second; // Get the associated value before erasing from left.map
            left.map.erase(it_left);   // Remove T -> U mapping
            right.map.erase(value);    // Remove corresponding U -> T mapping
        }
    }
 
    void remove_right(const U& key) {
        auto it_right = right.map.find(key);
        if (it_right != right.map.end()) {
            T value = it_right->second; // Get the associated value (which is T) before erasing from right.map
            right.map.erase(it_right);  // Remove U -> T mapping
            left.map.erase(value);      // Remove corresponding T -> U mapping
        }
    }
 
    void clear() {
        left.clear_map_only();
        right.clear_map_only();
    }
 
    void reserve(size_t n) {
        left.map.reserve(n);
        right.map.reserve(n);
    }
 
private:
    LeftSideType left{};
    RightSideType right{};
};