bimap Umsetzung in modernem C++ ohne Boost-

Question

Diese Frage gestellt wurde, bevor here Ich gebe zu, aber jetzt ist es vor 4 Jahren, damit ich für ein Update zu fragen wagen:

Ich brauche einen Weg, um ein Tupel/pair hinzufügen ein Container und suchen Sie nach beiden - das linke und das rechte Element effizient.

Boost hat bimap und multi_index die genau das tun, was ich will, aber ich frage mich, was ist die empfohlene Alternative in schlichtem modernem C++ - 11/14 für den Fall, dass Sie keine Abhängigkeit zu erhöhen (aus welchen Gründen auch immer).

Eine Antwort in der verknüpften schlägt vor, dass es keine Notwendigkeit für s.th. wie ein bimap mehr wegen transparente komparatoren. Die akzeptierte Antwort schlägt eine Implementierung vor, die std::map s mit sowohl key1 ->key2 als auch key2 ->key1 kombiniert.

Ich weiß nicht wirklich, wie die transparenten Komparatoren mir hier helfen, und ich bin nur neugierig, ob es einige ist, wie Sie es tun sollten und warum - Lösung. Kannst du ein paar Hinweise/Links geben?

Answer 1

Ich denke, es ist nur eine Menge mühsame Arbeit.

Aus Spaß habe ich hier einen Ausgangspunkt eingeführt.

Live On Coliru

Anmerkungen:

• Die 'Haupt' Unterlage ist ein std::list<tuple<K,V>>. Dies stellt sicher, dass der Iterator/Referenzungültigkeits Semantik std::map so nahe wie möglich ist
• Die Hauptunterlage als „links“ Ansicht verdoppelt (die nur verfügbar ist schreibgeschützt für die externen Gebrauch)
• Die „richtige“ Sicht sehr ähnlich ist, verwendet aber ein std::reference_wrapper<value_type const>, so dass wir nur Index der erste Behälter, wirklich

ich habe nur die einfache Abfragen implementiert (lower_bound, upper_bound, equal_range und find). Natürlich sind Iteratoren und Ranged-for da.

Sie werden einige Bits haben noch zu tun (erase, emplace, Entfernungs-Insertion, initializer_list Konstruktion; Stateful Allocator/Komparator-Unterstützung ist lückenhaft (keine Konstruktoren nehmen die entsprechenden Argumente), aber scoped Verteilern berücksichtigt wurden.)

Ohne weitere Umschweife:

#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 
} 

Drucke:

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