bimap implementation in modern C++ without Boost

Question

This question has been asked before here I admit, but it's now 4 years ago so I dare to ask for an update:

I need a way to add a tuple/pair to a container and search for both - the left and the right element efficiently.

Boost has bimap and multi_index which do exactly what I want but I wonder what's the recommended alternative in plain modern C++-11/14 in case you don't want to introduce a dependency to boost (for whatever reasons).

One answer in the linked suggests that there's no need for s.th. like a bimap any more due to transparent comparators. The accepted answer suggests an implementation combining std::maps to both key1 -> key2 and key2 -> key1.

I don't really know how the transparent comparators help me here and I'm just curious whether there is some this is how you should do it and why - solution. Can you provide some hints/links?

Kaffir

Possible duplicate of Is there a more efficient implementation for a bidirectional map? – Quirinus

Answer 1

I think it's just a lot of tedious work.

For fun, I set out to implement a starting point here.

Live On Coliru

Notes:

• The 'main' backing is a std::list<tuple<K,V>>. This makes sure that the iterator/reference invalidation semantics are as close to std::map as possible
• The main backing doubles as the "left" view (which is only available read-only for external use)
• The "right" view is very similar but uses a std::reference_wrapper<value_type const> so we only index the first container, really

I've only implemented the simple queries (lower_bound, upper_bound, equal_range and find). Of course iterators and ranged-for are there.

You'll have some bits left to do (erase, emplace, range-insertion, initializer_list construction; stateful allocator/comparator support is sketchy (no constructors take the relevant arguments) but scoped allocators have been taken into account.)

Without further ado:

#include <algorithm>
#include <tuple>
#include <list>
#include <functional> // for std::reference_wrapper
#include <cassert>

namespace bimap {
    namespace detail {
        template <typename Cmp, typename V, size_t I> struct CompareByElement : private Cmp {
            bool operator()(V const& a, V const& b) const {
                using std::get;
                return Cmp::operator()(get<I>(a), get<I>(b));
            }
            bool operator()(V const& a, V const& b) {
                using std::get;
                return Cmp::operator()(get<I>(a), get<I>(b));
            }
        };

        namespace tags {
            struct left_view;
            struct right_view;
        }

        template <typename ViewTag, typename Left, typename Right, typename LeftCmp, typename RightCmp, typename RawAlloc>
        struct view_traits;

        template <typename Left, typename Right, typename LeftCmp, typename RightCmp, typename RawAlloc>
        struct view_traits<tags::left_view, Left, Right, LeftCmp, RightCmp, RawAlloc> {
            using value_type     = std::tuple<Left, Right>;
            using allocator_type = typename RawAlloc::template rebind<value_type>::other;
            using base_type      = std::list<value_type, allocator_type>;
            using comparator     = CompareByElement<LeftCmp, value_type, 0>;
        };

        template <typename Left, typename Right, typename LeftCmp, typename RightCmp, typename RawAlloc>
        struct view_traits<tags::right_view, Left, Right, LeftCmp, RightCmp, RawAlloc> {
            using value_type     = std::tuple<Left, Right>;
            using allocator_type = typename RawAlloc::template rebind<std::reference_wrapper<value_type const>>::other;
            using base_type      = std::list<std::reference_wrapper<value_type const>, allocator_type>;
            using comparator     = CompareByElement<RightCmp, value_type, 1>;
        };

        template <typename Left, typename Right, typename LeftCmp, typename RightCmp, typename RawAlloc>
        struct bimap_traits {
            using left_traits = view_traits<tags::left_view,  Left, Right, LeftCmp, RightCmp, RawAlloc>;
            using right_traits = view_traits<tags::right_view, Left, Right, LeftCmp, RightCmp, RawAlloc>;
        };

        template <typename Traits> struct map_adaptor : 
            private Traits::base_type,
            private Traits::comparator // empty base class optimization
        {
            using value_type     = typename Traits::value_type;
            using allocator_type = typename Traits::allocator_type;
            using base_type      = typename Traits::base_type;
            using comparator     = typename Traits::comparator;

            using iterator       = typename base_type::iterator;
            using const_iterator = typename base_type::const_iterator;

            using base_type::cbegin;
            using base_type::cend;
            using base_type::begin;
            using base_type::end;
            using base_type::insert;
            using base_type::size;

            auto lower_bound(value_type const& v)       { return std::lower_bound(base_type::begin(), base_type::end(), v, get_comp()); }
            auto upper_bound(value_type const& v)       { return std::upper_bound(base_type::begin(), base_type::end(), v, get_comp()); }
            auto equal_range(value_type const& v)       { return std::equal_range(base_type::begin(), base_type::end(), v, get_comp()); }
            auto lower_bound(value_type const& v) const { return std::lower_bound(base_type::begin(), base_type::end(), v, get_comp()); }
            auto upper_bound(value_type const& v) const { return std::upper_bound(base_type::begin(), base_type::end(), v, get_comp()); }
            auto equal_range(value_type const& v) const { return std::equal_range(base_type::begin(), base_type::end(), v, get_comp()); }

            auto find(value_type const& v) { 
                auto er = equal_range(v);
                return er.first == er.second? end() : er.first;
            }

            auto find(value_type const& v) const { 
                auto er = equal_range(v);
                return er.first == er.second? end() : er.first;
            }

            base_type& base()                  { return *static_cast<base_type*>(this);       } 
            base_type const & base() const     { return *static_cast<base_type const*>(this); } 
          private:
            comparator& get_comp()             { return *this;                                } 
            comparator const& get_comp() const { return *this;                                } 
        };
    }

    template <typename Left, typename Right, 
            typename LeftCmp = std::less<Left>, typename RightCmp = std::less<Right>,
            typename RawAlloc = std::allocator<void>,
            typename Traits = detail::bimap_traits<Left, Right, LeftCmp, RightCmp, RawAlloc>
        >
    class bimap : private detail::map_adaptor<typename Traits::left_traits> {
    public:
        using left_type      = typename detail::map_adaptor<typename Traits::left_traits>;
        using right_type     = typename detail::map_adaptor<typename Traits::right_traits>;

        using value_type     = typename Traits::left_traits::value_type;
        using allocator_type = typename Traits::left_traits::allocator_type;
        using base_type      = left_type;

        using const_iterator = typename base_type::const_iterator;
        using iterator       = const_iterator;

        using base_type::cbegin;
        using base_type::cend;
        auto begin() const { return cbegin(); }
        auto end() const { return cend(); }
        using base_type::size;

        left_type  const& left()  const { return *this;         }
        right_type const& right() const { return inverse_index; }

        std::pair<const_iterator, bool> insert(value_type const& v) {
            auto lr = left().find(v);
            auto rr = right().find(v);

            bool hasl = lr!=left().end(),
                 hasr = rr!=right().end();

            if (!hasl && !hasr) {
                auto lins = mutable_left().insert(left().lower_bound(v), v);
                auto rins = mutable_right().insert(right().lower_bound(*lins), *lins);
                (void) rins;

                return { lins, true };
            } else {
                return { end(), false };
            }
        }

    private:
        detail::map_adaptor<typename Traits::right_traits> inverse_index;
        left_type&  mutable_left()  { return *this;         }
        right_type& mutable_right() { return inverse_index; }
    };
}

#include <iostream>

#define CHECK(cond) do {\
    if (cond) { } else { std::cout << "FAILED: " #cond "\n"; } } while(false)

int main() {
    using Map = bimap::bimap<int, std::string>;
    Map bm;
    CHECK(bm.insert(std::make_tuple(1,"three")).second);

    // now left 1 and right "three" are taken:
    CHECK(!bm.insert(std::make_tuple(1,"two")).second);
    CHECK(!bm.insert(std::make_tuple(2,"three")).second);

    // unrelated keys insert fine
    CHECK(bm.insert(std::make_tuple(2,"aaaa")).second);

    // thing contains 2 elements now:
    CHECK(bm.size() == 2);

    using std::get;

    for (Map::value_type const& p : bm)         std::cout << get<0>(p) << ", " << get<1>(p) << "; "; std::cout << "\n";
    for (Map::value_type const& p : bm.left())  std::cout << get<0>(p) << ", " << get<1>(p) << "; "; std::cout << "\n";

    // right view map orders by right index
    for (Map::value_type const& p : bm.right()) std::cout << get<0>(p) << ", " << get<1>(p) << "; "; std::cout << "\n";

    // you can do find, lower_bound, equal_range etc. on both sides
}

Prints:

1, three; 2, aaaa; 
1, three; 2, aaaa; 
2, aaaa; 1, three; 

Dragelin

But this has O(n) lookup! – Bankrupt

@JoaquínMLópezMuñoz huh. How? I thought binary search was O(log n) – Dragelin

O(log n) comparisons, but O(n) increments-decrements if iterators are not random-access. – Bankrupt

@JoaquínMLópezMuñoz Oh. Yeah. Oops. Good point. It's trivial to drop in std::deque or std::vector instead of std::list. I made it clear why I chose std::list as a default here, but you make a convincing point not to cling to the iterator invalidation semantics of a node-based container here. Perhaps boost::stable_vector would be most suitable, but... then it's boost again :) – Dragelin

If you want node-based iterator invalidation guarantees and optimum memory consumption you'll end up writing Boost.MultiIndex :-) – Bankrupt

Of course. Much appreciated. I rarely venture without it – Dragelin