bimap的实现不带升压

Question

这个问题已经被问here之前，我承认，但现在4年以前它是如此我敢问的更新：

我需要一种方法来一个元组/对添加到一个容器并且有效地搜索左边和右边的元素。

升压具有bimap和multi_index里面做正是我想要的，但我不知道什么是纯现代C++推荐的替代方案 - 11/14如果你不希望引入的依赖性提高（无论何种原因）。

链接中的一个答案表明没有必要s.th.像一个bimap更多由于透明比较器。被接受的答案暗示了将std::map与key1→key2和key2→key1组合的实现。

我真的不知道透明比较器是如何帮助我的，我只是好奇是否有一些这是你应该怎么做，为什么 - 解决方案。你能提供一些提示/链接吗？

Answer 1

我认为这只是很多繁琐的工作。

为了好玩，我着手在这里实施一个起点。

Live On Coliru

注：

• '主' 背衬为std::list<tuple<K,V>>。这可以确保迭代器/参考无效语义接近std::map尽可能
• 主要背衬兼作“左”视图（其仅提供只读外用）
• “正确”的视图是非常相似，但采用的是std::reference_wrapper<value_type const>所以我们只指数第一容器，真的

我只实现了简单的查询（lower_bound，upper_bound，equal_range和find）。当然，iterators和ranged-for在那里。 （erase,emplace，范围插入，initializer_list构造;有状态分配器/比较器支持是粗略的（没有构造函数采用相关参数），但已将范围分配器考虑在内）。

事不宜迟：

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

打印：

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