Почему там нет boost :: intrusive :: map?
Буст документация (http://www.boost.org/doc/libs/1_55_0/doc/html/intrusive.html) утверждает, что навязчивые контейнеры реализованы для list (оба одинарные / двойные связи), set а также multiset,
Я не мог найти реализацию для карты. Есть ли какая-то более глубокая причина для этого, или это просто ожидание реализации?
Решение
Это потому что map<Key, Value> на самом деле set<std::pair<Key const, Value>> и наборы Boost.Intrusive и Boost.MultiIndex позволяют использовать один из членов-значений в качестве ключа. Другими словами, нет необходимости map если find может принять сопоставимый ключ, а не все значение для поиска которая была давней нерешенной проблемой с std::map а также std::set:
Функции поиска ассоциативных контейнеров (find, lower_bound, upper_bound,
equal_range) принимает только аргумент key_type, требующий от пользователей создания
(явно или неявно) объект типа key_type для поиска.
Это может быть дорого, например построение большого объекта для поиска в наборе
когда функция компаратора смотрит только на одно поле объекта. Там
среди пользователей существует сильное желание иметь возможность поиска с использованием других типов, которые
сопоставимы с key_type.
Другие решения
поскольку версия 1.59 Boost.Intrusive поддерживает картоподобные ассоциативные контейнеры. Он значительно более гибкий, чем стандартные контейнероподобные контейнеры, так как программист не обязан определять какие-либо std::pair как структура, чтобы определить key_type а также mapped_type, Новая опция key_of_value добавляется к навязчивым наборам интерфейсов, определяющим, какая часть значения должна рассматриваться как key_type и как его получить. Это было сделано для упрощения использования карты при использовании Boost.Intrusive. Пример кода взят из документации Boost:
#include <boost/static_assert.hpp>
#include <boost/type_traits/is_same.hpp>
#include <boost/intrusive/set.hpp>
#include <boost/intrusive/unordered_set.hpp>
#include <vector>
#include <cassert>
using namespace boost::intrusive;
class MyClass : public set_base_hook<>
, public unordered_set_base_hook<>
{
public:
int first;
explicit MyClass(int i) : first(i){}
};
//key_of_value function object, must:
//- be default constructible (and lightweight)
//- define the key type using "type"//- define an operator() taking "const value_type&" and
// returning "const type &"struct first_int_is_key
{
typedef int type;
const type & operator()(const MyClass& v) const
{ return v.first; }
};
//Define omap like ordered and unordered classes
typedef set< MyClass, key_of_value<first_int_is_key> > OrderedMap;
typedef unordered_set< MyClass, key_of_value<first_int_is_key> > UnorderedMap;
int main()
{
BOOST_STATIC_ASSERT((boost::is_same< OrderedMap::key_type, int>::value));
BOOST_STATIC_ASSERT((boost::is_same<UnorderedMap::key_type, int>::value));
//Create several MyClass objects, each one with a different value
//and insert them into the omap
std::vector<MyClass> values;
for(int i = 0; i < 100; ++i) values.push_back(MyClass(i));
//Create ordered/unordered maps and insert values
OrderedMap omap(values.begin(), values.end());
UnorderedMap::bucket_type buckets[100];
UnorderedMap umap(values.begin(), values.end(), UnorderedMap::bucket_traits(buckets, 100));
//Test each element using the key_type (int)
for(int i = 0; i != 100; ++i){
assert(omap.find(i) != omap.end());
assert(umap.find(i) != umap.end());
assert(omap.lower_bound(i) != omap.end());
assert(++omap.lower_bound(i) == omap.upper_bound(i));
assert(omap.equal_range(i).first != omap.equal_range(i).second);
assert(umap.equal_range(i).first != umap.equal_range(i).second);
}
//Count and erase by key
for(int i = 0; i != 100; ++i){
assert(1 == omap.count(i));
assert(1 == umap.count(i));
assert(1 == omap.erase(i));
assert(1 == umap.erase(i));
}
assert(omap.empty());
assert(umap.empty());
return 0;
}