Главная » C++ » c ++ 11 - реализация bimap в современном C ++ без Boost

c ++ 11 — реализация bimap в современном C ++ без Boost

Этот вопрос был задан ранее Вот Я признаю, но это сейчас 4 года назад, поэтому я смею просить обновления:

Мне нужен способ добавить кортеж / пару в контейнер и эффективно искать как левый, так и правый элемент.

Boost имеет bimap а также multi_index которые делают именно то, что я хочу, но мне интересно, какова рекомендуемая альтернатива в простом современном C ++ — 11/14, если вы не хотите вводить зависимость для повышения (по каким-либо причинам).

Один ответ в связанном предполагает, что нет необходимости в s.th. как бимап больше из-за прозрачные компараторы. Принятый ответ предлагает реализацию, сочетающую std::mapс обоими key1 -> key2 а также key2 -> key1,

Я действительно не знаю, как прозрачные компараторы помогают мне здесь, и мне просто интересно, есть ли некоторые вот как ты должен это делать и почему — решение. Можете ли вы предоставить некоторые советы / ссылки?

5

Решение

Я думаю, что это просто много утомительной работы.

Ради интереса я намеревался реализовать отправную точку здесь.

Жить на Колиру

Заметки:

  • «Основная» поддержка является std::list<tuple<K,V>>, Это гарантирует, что семантика аннулирования итератора / ссылки настолько близка к std::map насколько возможно
  • Основная подложка дублируется как «левый» вид (который доступен только для чтения только для внешнего использования)
  • «Правильный» вид очень похож, но использует std::reference_wrapper<value_type const> поэтому мы индексируем только первый контейнер, на самом деле

Я реализовал только простые запросы (lower_bound, upper_bound, equal_range а также find). Конечно, есть итераторы и дальнобойщики.

У вас останется кое-что сделать (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;
5

Другие решения

Других решений пока нет …

Источник
По вопросам рекламы ammmcru@yandex.ru
Web-Answers © 2024 Наверх
Adblock
detector