我想使用 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'
您可以使用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");
}
这里的缺点是插入需要线性时间而不是对数时间。
你可以遍历它们:
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'