All geek questions in one place

Bimap in modern C ++ without Boost

This question has been asked before here I admit, but 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 efficiently look for both left and right elements.

Boost has bimap and multi_index that do exactly what I want, but I'm wondering what the recommended alternative in simple modern C ++ is 11/14 if you do not want to introduce a dependency to increase (for some reason).

One answer in the link assumes there is no need for s.th. like bimap more because of transparent comparators. The accepted answer proposes an implementation combining std::map with both key1 → key2 and key2 → key1 .

I really don't know how transparent comparators help me here, and I'm just wondering if you have one, how you should do it, and why - a solution. Can you provide some hints / links?

+5
source share
1 answer

I think this is just a tedious job.

For fun, I decided to implement the starting point here.

Live on coliru

Notes:

  • The "main" support is std::list<tuple<K,V>> . This ensures that the iterator / link invalidation semantics are invalid as close as possible to std::map
  • The main support is duplicated as a "left" view (which is read-only for external use)
  • The "correct" view is very similar, but uses std::reference_wrapper<value_type const> , so we only index the first container, really

I just performed simple queries ( lower_bound , upper_bound , equal_range and find ). Of course, there are iterators and rank-and-file.

You have a few bits left ( erase , emplace , range-insertion, initializer_list construction, support for a stateful distributor / comparator is fragmentary (no constructors accept the appropriate arguments), but allocated allocators count.)

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 }

Print

 1, three; 2, aaaa; 1, three; 2, aaaa; 2, aaaa; 1, three;
+5
source

Source: https://habr.com/ru/post/1243451/

More articles:


All Articles