Можно ли заставить контейнер multi_index использовать непрерывную память?

Здесь у меня есть простой контейнер multi_index, и мне интересно, есть ли способ заставить multi_index размещать элементы в памяти непрерывно. Я думал, что это было бы возможно, если бы основной индекс был random_access.

Однако этот простой пример показывает, что неожиданно элементы не являются смежными в памяти. Существует ли комбинация boost::multi_index::indexed_by, которая может привести к непрерывной памяти?

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/random_access_index.hpp>

int main(){
    typedef boost::multi_index_container<
        double,  // simply store doubles
        boost::multi_index::indexed_by<
            boost::multi_index::random_access<>
        >
    > random_access_container;

    random_access_container v; // fill container
    v.reserve(10); // also tried this
    v.push_back(1.);
    v.push_back(2.);
    v.push_back(3.);

    assert( v[0] == 1. ); // ok
    assert( *(&v[0] + 1) == v[1] ); // this fails, memory is not contiguous
}

ПРИМЕЧАНИЕ 1. Я хочу это для совместимости (чтобы я мог воспользоваться контейнером multi_index --с другими параметрами доступа--), но также использовать прямой доступ к памяти (как это возможно с std::vector).

ПРИМЕЧАНИЕ 2. Я только что нашел эту цитату из документации, http://www.boost.org/doc/libs/1_61_0/libs/multi_index/doc/reference/rnd_indices.html#rnd_indices, так что это выглядит сложно.

Если не указано иное или если соответствующий интерфейс не существует, индексы произвольного доступа проверяют те же требования к контейнеру, что и std::vector, а также требования к конкретным операциям списка std::list в [list.ops]. Некоторые из наиболее важных отличий относительно std::vector:

  1. Индексы произвольного доступа не обеспечивают непрерывность памяти и, следовательно, не имеют функций-членов данных.

    ...


person alfC    schedule 02.06.2016    source источник


Ответы (1)


Нет, у вас нет смежности памяти. Структура индекса с произвольным доступом аналогична структуре boost::container::stable_vector:

схема памяти индекса с произвольным доступом

Приближение к непрерывной памяти может быть получено, если вы сохраните свои элементы (например, типа T) в std::vector<T>, а затем используете multi_index_container из std::ref<T>s. Это, конечно, усложняет управление временем жизни объекта.

Изменить: обоснование дизайна

Существует ряд причин, по которым смежность памяти сложно/трудно включить в дизайн библиотеки:

  • Стабильность итератора обеспечивают все индексы, а не только произвольные. Было бы невозможно сохранить это (с разумной производительностью), если бы элементы хранились непрерывно в куске памяти.
  • Предположим, нам каким-то образом удалось получить индекс произвольного доступа, вызывающий непрерывность памяти по отношению к хранению элементов. Что произойдет, если у нас будет два индекса произвольного доступа? Похоже, что первый индекс контейнера должен иметь особый статус с точки зрения определения расположения всего контейнера, чтобы он содержал воду.
  • Индексы неслучайного доступа по необходимости основаны на узлах. Это означает, что каждое значение хранится в более крупной структуре с местом для дополнительной информации (указатели rb-дерева и т. д.). Если бы элементы хранились непрерывно, то либо а) это были бы узлы, которые будут храниться непрерывно, а не сами значения , что кажется довольно бесполезным (подумайте, что data() вернет), или б) узлы должны быть отделены от значений, чтобы вместо встраивания значения в узел у нас были узлы с указателями на непрерывно хранящиеся значения , что является пустой тратой места и не выглядит разумным решением по умолчанию.
person Joaquín M López Muñoz    schedule 02.06.2016
comment
Это потому, что стабильность (итератора) была приоритетом в дизайне? В принципе, резервная функция может достичь этого, но я думаю, что это чрезвычайно усложнило бы реализацию, не так ли? - person alfC; 02.06.2016
comment
Другими словами, почему stable_vector (или multi_index) не резервирует непрерывную память (для узлов), если количество элементов известно заранее? (Я пытаюсь увидеть, есть ли какие-либо обстоятельства, при которых память может быть обманута, чтобы быть непрерывной, я не ищу гарантии при любых условиях.) - person alfC; 03.06.2016
comment
Я добавил несколько комментариев к своему ответу, надеюсь, ответив на ваши вопросы. - person Joaquín M López Muñoz; 03.06.2016
comment
Спасибо за комментарии: 1) ... но, возможно, они могут быть непрерывными, по крайней мере, после начального reserve и до того, как контейнер вырастет позже. 2) на самом деле, я мысленно исходил из того, что первый индекс был особенным (и я сделал его случайным доступом по этой причине). Наконец, смежность памяти является более слабым условием, чем смежность индекса, если есть два случайного доступа, оба могут быть смежными (но не оба смежных индекса) после начального reserve. 3) Согласен, я все время думаю, что просто изначально память может быть непрерывной по умолчанию (или, по крайней мере, узлы могут быть смежными)... - person alfC; 03.06.2016
comment
... наконец, позвольте мне сказать, что я глубоко ценю ваши усилия и изобретательность при создании такой замечательной библиотеки (и до C++11!) - person alfC; 03.06.2016
comment
Ладно, я понимаю, к чему ты клонишь. Если вам нужна смежность node (в отличие от смежности value), вероятно, вы можете прибегнуть к некоторому распределителю пула. Обратите внимание, что reserve индекса произвольного доступа не имеет к этому никакого отношения, поскольку он просто применяется к внутреннему массиву указателей индекса (см. диаграмму). Наконец, я не понимаю, для чего полезна смежность узлов (особенно потому, что тип узла неизвестен вам как пользователю). - person Joaquín M López Muñoz; 03.06.2016
comment
Честно говоря, я не думал до того, как это хранилище было реализовано в виде узлов (я думал, что если якобы привилегированный индекс был случайным, дополнительная структура находилась где-то еще в памяти), поэтому я придумываю это, пока мы говорим! : Контейнер может предоставить доступ к размеру узла, поэтому, если узлы являются смежными, можно узнать шаг. Но теперь я вижу все трудности, которые это подразумевает. Наконец, использование равномерно непрерывной памяти с шагами заключается в том, что (в ограниченных обстоятельствах) можно передать элементы последовательности устаревшей C-функции (которая принимает указатели и шаги). - person alfC; 03.06.2016
comment
@Joaquín M López Muñoz: для нас основными вариантами использования контейнера являются итерация и поиск определенного элемента. В основном мы используем multi_index, чтобы иметь контейнер объектов, отсортированных по их идентификатору. Multi_index позволяет осуществлять гетерогенный поиск, который еще недоступен в С++ 11. Возможно, в противном случае flat_set мог бы заменить замену. - person gast128; 20.02.2017
comment
А если использовать резерв? Будет ли зарезервированный блок (имеет тенденцию) быть непрерывным? - person alfC; 22.01.2018
comment
@alfC Боюсь, что нет: reserve влияет только на массив указателей индекса (верхний вектор на диаграмме, показанной в моем ответе), фактический узел на самом деле не выделяется заранее. - person Joaquín M López Muñoz; 22.01.2018
comment
@JoaquínMLópezMuñoz Понятно. Таким образом, выигрыш от использования резерва ограничен по сравнению с vector.reserve. Мультииндексный контейнер может в принципе использовать резерв, но не делает этого. Думаю, это слишком усложнит реализацию. (?) - person alfC; 22.01.2018
comment
@alfC В конце концов, multi_index_contaner - это контейнер на основе узлов, и в этом отношении он ведет себя почти так же, как, скажем, std::set, у которого тоже нет reserve. Возможно, вы захотите использовать распределитель на основе пула, чтобы увидеть, улучшит ли это эффективность и/или локальность кэша. - person Joaquín M López Muñoz; 22.01.2018
comment
Спасибо за разъяснения. Считаете ли вы Boost.Pool хорошим вариантом, который хорошо работает с несколькими индексами? boost.org/doc/libs/1_66_0/ библиотеки/пул/doc/html/index.html - person alfC; 22.01.2018
comment
Я действительно не знаю. Boost.Pool, безусловно, хорошо взаимодействует с Boost.MultiIndex (я помню, что пытался в прошлом), но что касается результирующей производительности, вам придется запустить собственное профилирование и посмотреть. - person Joaquín M López Muñoz; 22.01.2018