首页 文章

C std :: map如何通过索引位置访问键

提问于
浏览 次
0

我想在log（n）时间内使用C std::map 来访问与给定键相关联的值 . 由于 std::map 的键是排序的，从技术上讲，我可以按排序顺序中的位置访问键 . 我知道std :: map没有随机访问迭代器 . 是否有任何"map like"数据结构提供通过密钥的访问（通过使用[]运算符），并通过排序顺序中的密钥位置提供（只读）随机访问 . 这是一个基本的例子：

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'
c++ dictionary stl

2 回答

  • 0

    你可以使用Boost.MultiIndex的ranked indices：

    Live On Coliru

    #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）而是对数，因此排名索引不是完全随机访问 .

    Postscript: 具有真正随机访问的另一种选择是Boost.Container的flat associative containers：

    Live On Coliru

    #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");
}

    这里的缺点是插入需要线性而不是对数时间 .

    回复于
  • 1

    你可以迭代它们：

    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'
    回复于

相关问题