C++ std::map, как получить доступ к ключам по местоположению индекса

Question

Я хотел бы использовать C++ std::map чтобы получить доступ к значению, связанному с данным ключом в log (n) времени. Так как ключи std::map отсортированы, технически я могу получить доступ к ключам по расположению в отсортированном порядке. Я знаю, что std::map не имеет итератора произвольного доступа. Существует ли какая-либо "подобная карте" структура данных, обеспечивающая как доступ через ключи (с помощью оператора []), так и обеспечивающая произвольный доступ (только для чтения) через местоположение ключа в отсортированном порядке. Вот основной пример:

my_fancy_map['a'] = 'value_for_a'
my_fancy_map['b'] = 'value_for_b'

assert my_fancy_map.get_key_at_location(0) == 'a'
assert my_fancy_map.get_key_at_location(1) == 'b'
assert my_fancy_map.get_value_at_location(1) == 'value_for_b'
assert my_fancy_map['a'] == 'value_for_a'

Answer 1

Вы можете использовать ранжированные индексы Boost.MultiIndex:

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

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ranked_index.hpp>
#include <boost/multi_index/member.hpp>

using namespace boost::multi_index;

template<typename K,typename T>
using ranked_map=multi_index_container<
  std::pair<K,T>,
  indexed_by<
    ranked_unique<member<std::pair<K,T>,K,&std::pair<K,T>::first>>
  >
>;

#include <cassert>
#include <string>

int main()
{
  ranked_map<std::string,std::string> m;

  m.emplace("a","value for a");
  m.emplace("b","value for b");

  assert(m.nth(0)->first=="a");
  assert(m.nth(1)->first=="b");
  assert(m.nth(1)->second=="value for b");
  assert(m.find("a")->second=="value for a");
}

Обратите внимание, однако, что nth не O(1), а логарифмический, поэтому ранжированные индексы не являются произвольным доступом.

Постскриптум: Другая альтернатива с истинным произвольным доступом - плоские ассоциативные контейнеры Boost.Container:

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

#include <boost/container/flat_map.hpp>
#include <cassert>
#include <string>

int main()
{
  boost::container::flat_map<std::string,std::string> m;

  m["a"]="value for a";
  m["b"]="value for b";

  assert(m.nth(0)->first=="a");
  assert(m.nth(1)->first=="b");
  assert(m.nth(1)->second=="value for b");
  assert(m["a"]=="value for a");
}

Недостатком является то, что вставка занимает линейное, а не логарифмическое время.

Answer 2

Вы можете просто просмотреть их:

my_fancy_map['a'] = 'value_for_a'
my_fancy_map['b'] = 'value_for_b'

auto location = std::begin(my_fancy_map);
assert location.first == 'a'
++location;
assert location.first == 'b'
assert location.second == 'value_for_b'
assert my_fancy_map['a'] == 'value_for_a'