Boost.Container flat_map и std :: string_view

Question

В течение некоторого времени я использовал Boost's flat_map как свою ассоциативную коллекцию переходов по причинам, объясненным в приведенной в их документации документации, и (первоначально) благодаря тому, что она давала новые функции до реализации std компилятора, и было одинаковым на разных платформах.

Теперь я хотел бы начать использовать string_view для предотвращения копирования строк, когда они взяты из подстрок большего ввода. string_view указывает на диапазон символов в большей строке без необходимости копировать их в новый экземпляр std::string.

Достигнув использования карты, я вспомнил, что еще одной прогрессивной особенностью Boost.Container, которой я пользовался в прошлом, является конформные ключи , где вы можете использовать все, что правильно сравнивается с сохраненным ключ, а не преобразование в фактический тип ключа.

Но сейчас я не могу найти упоминаний об этом в документации. Я знаю, что std::map может сделать это сейчас (начиная с C ++ 14), но я бы предпочел использовать flat_map для крошечных коллекций.

Что я мог видеть, что давало такую ​​гибкость много лет назад, если это не проявляется в boost::flat_map::insert и т. Д.? Какие хорошие коллекции квартир можно использовать сейчас с современными компиляторами?

Answer 1

Возможно, это не то, на что вы ссылаетесь, но если вы используете std::string_view в качестве типа ключа, все операции уже работают через неявное преобразование в std::string_view:

Live On Coliru

#include <boost/container/flat_map.hpp>
#include <string_view>

int main() {
    boost::container::flat_map<std::string_view, int> m {
        { "one", 1 },
        { "two", 2 },
        { "three", 3 },
        { "four", 4 },
    };

    std::string key = "one";
    auto one = m.at(key);
    auto range = m.equal_range(key);
    auto it = m.find(key);

    m[key] = 1;
}

Обратное

Здесь вам действительно нужно использовать контейнер, который действительно поддерживает поиск совместимых ключей. Это не должно быть слишком сложно, чтобы бросить один:

Вот один из них:

Live On Coliru

#include <initializer_list>
#include <algorithm>
#include <utility>
#include <stdexcept>

#include <boost/container/small_vector.hpp>

template <typename K, typename V, typename Cmp = std::less<K>, typename Storage = boost::container::small_vector<std::pair<K, V>, 10> >
struct flat_map {
    using key_type       = K;
    using mapped_type    = V;
    using key_compare    = Cmp;

    using storage        = Storage;
    using value_type     = typename storage::value_type;
    using iterator       = typename Storage::iterator;
    using const_iterator = typename Storage::const_iterator;

    struct value_compare {
        key_compare _cmp;
        template <typename A, typename B>
        bool operator()(A const& a, B const& b) const { return _cmp(access(a), access(b)); }

      private:
        static auto& access(value_type const& v) { return v.first; }
        template <typename Other>
        static auto& access(Other const& v)      { return v; }
    } _cmp;

    storage _data;

    flat_map(std::initializer_list<value_type> i) : _data(i) {}

    iterator begin()             { return _data.begin(); }
    iterator end()               { return _data.end();   }
    const_iterator begin() const { return _data.begin(); }
    const_iterator end()   const { return _data.end();   }

    template <typename Key>
    mapped_type& operator[](Key&& key) { return find(std::forward<Key>(key))->second; }
    template <typename Key>
    mapped_type const& operator[](Key&& key) const { return find(std::forward<Key>(key))->second; }

    template <typename Key>
    iterator find(Key&& key) {
        auto r = equal_range(std::forward<Key>(key));
        return (r.first == r.second)? end() : r.first;
    }
    template <typename Key>
    const_iterator find(Key&& key) const {
        auto r = equal_range(std::forward<Key>(key));
        return (r.first == r.second)? end() : r.first;
    }

    template <typename Key>
    mapped_type& at(Key&& key) {
        auto r = equal_range(std::forward<Key>(key));
        if (r.first == r.second) throw std::out_of_range("key");
        return r.first->second;
    }
    template <typename Key>
    mapped_type const& at(Key&& key) const {
        auto r = equal_range(std::forward<Key>(key));
        if (r.first == r.second) throw std::out_of_range("key");
        return r.first->second;
    }

    template <typename Key>
    auto equal_range(Key&& key) { return std::equal_range(begin(), end(), std::forward<Key>(key), _cmp); }
    template <typename Key>
    auto equal_range(Key&& key) const { return std::equal_range(begin(), end(), std::forward<Key>(key), _cmp); }
};

Он поддерживает точно обратное первому сценарию (с учетом компаратора std::less<>):

#include <string_view>
#include <string>

int main() {
    flat_map<std::string, int, std::less<> > m {
        { "one", 1 },
        { "two", 2 },
        { "three", 3 },
        { "four", 4 },
    };

    std::string_view key = "one";
    auto one = m.at(key);
    auto range = m.equal_range(key);
    auto it = m.find(key);

    m[key] = 1;
}

Answer 2

Поддержка функций полиморфного поиска была добавлена ​​только , недавно в Boost.Container. Если все хорошо, его следует выпустить с Boost 1.68.

Тем временем вы можете эмулировать плоские ассоциативные контейнеры с заказанными std::vector и std::lower_bound.

typedef std::pair< std::string, int > element_type;
std::vector< element_type > map;

struct element_order
{
    bool operator()(element_type const& left, element_type const& right) const
    {
        return left.first < right.first;
    }

    bool operator()(std::string_view const& left, element_type const& right) const
    {
        return left < right.first;
    }

    bool operator()(element_type const& left, std::string_view const& right) const
    {
        return left.first < right;
    }
};

auto find_element(std::string_view const& key)
{
    auto it = std::lower_bound(map.begin(), map.end(), key, element_order());
    if (it != map.end() && it->first == key)
        return it;
    return map.end();
}