Контейнер STL для региона/арене, как распределение

Question

Я пишу класс (кодировщик Хаффмана, если вам интересно), который должен содержать специализированное двоичное дерево, для которого контейнер STL не был непосредственно соответствующим. И это не проблема, чтобы определить структуру TreeNode с некоторыми указателями влево/вправо и построить вещь. Вопросы, которые я имею в виду, касаются распределения самих узлов.

Я думал, что было бы очень приятно, если бы я использовал контейнер STL в качестве своего «распределителя», а не напрямую вызывал new для каждого узла. Это было привлекательно, потому что это сделало бы разрушение тривиальным: мне не нужно было бы ходить по моему дереву в деструкторе по отдельности delete все узлы; деструктор запаса для контейнера STL, который я использовал, поскольку мой «распределитель» сделал бы это автоматически.

Мой первый выбор «распределителя» был std::vector<TreeNode>. Но это совсем не сработало, потому что, по мере того как вектор растет, он должен перераспределять себя и отменять все мои указатели. Итак, что я делаю на данный момент, цепляется за идею std::vector и отказывается от указателей; в каждом месте, где у меня был указатель, у меня есть целое число, содержащее индекс в моем векторе. То есть, в моем родительском классе у меня есть члены, такие как

std::vector<TreeNode> _heap;  // all nodes in tree 
int _root;       // index into _heap 

, а затем выделить новый узел я сделать что-то вроде этого:

TreeNode newnode(/*whatever*/); 
nodei = _heap.size(); 
_heap.push_back(newnode); 
// now do something with nodei 

И на самом деле это все работает просто отлично, за исключением : работа с индексами вместо указателей - обычная неприятность. Везде, где я обычно ссылался бы на остроконечный узел как *nodep, вместо этого я должен использовать _heap[nodei]. (Но, опять же, это работает, то это не проблема.)

Мои вопросы:

1. Есть ли STL контейнер класса, который гарантированно не иметь его элементы перемещаются позже, так что указатели на они останутся действительными для жизни контейнера?
2. Являются ли указатели на элементы внутри контейнеров STL хорошей идеей?
3. Было бы лучше использовать итераторы или ссылки вместо указателей для такого рода вещей (то есть указывать на элементы в контейнеризованной куче)?
4. Есть ли лучший способ реализовать локальный распределитель кучи, с легкой семантикой (т. Е. Неявной)?

Я открыт для других идей, хотя я должен предупредить вас, что я довольно консервативен. Я хотел бы придерживаться чего-то, что работает в «базовом» C++, т. Е. Я буду уклоняться от чего-то, что есть только в C++ 11 или что-то в этом роде. И я особенно подвержен накладным расходам и сложности пакетов, таких как sigc и boost, поэтому я вряд ли захочу использовать один из своих специальных контейнеров или распределителей.

Answer 1

Существует ли контейнерный класс STL, который не должен перемещать его элементы позже, так что указатели на них останутся действительными для срока службы контейнера?

std::deque не перемещать элементы, если бы вы только push_back/emplace_back элементов, что является достаточным для вашей задачи, и вы можете взять указатели на элементы.

Кроме того, большинство популярных реализаций std::deque выделяют память в кусках, где один кусок может хранить несколько элементов последовательно - это улучшает локальность и уменьшает количество назначений (по сравнению с std::list).

Являются ли указатели на элементы внутри контейнеров STL хорошей идеей?

Это хорошая идея, если вы знаете основную семантику и гарантии (которую вы можете прочитать в C++ ISO).

Например, если вы не изменяете емкость std::vector и не изменяете ее размер - указатели на элементы внутри вектора будут в порядке.

Было бы лучше использовать итераторы или ссылки вместо указателей для такого рода вещей (то есть указывать на элементы в контейнеризованной куче)?

Я не вижу никаких преимуществ, за исключением того, что некоторые реализации STL могут обеспечивать дополнительные защитные проверки в сборках Debug.

Есть ли лучший способ реализовать локальный распределитель кучи, с легкой (т. Е. Неявной) семантикой разрушения?

На самом деле я, как они идею использования индекса, т.е. region[node_index], как вы сделали (хотя это не всегда приемлемо в тех случаях, когда код ожидать «истинные» указатели). Я вижу несколько потенциальных преимуществ такого подхода:

• std::vector растет в геометрической прогрессии, что приводит к O(log N) распределений для N элементов. Можно получить аналогичное свойство для указателей, но оно сложнее - вы должны поддерживать список кусков разных размеров, например std::vector<std::vector<Node>>, где каждый новый блок имеет емкость total_size * k, и вы должны обязательно его не менять (потому что указателей на элементы).

• У вас есть контроль над sizeof(index) - вы можете использовать тип индекса, который просто подходит для вашей задачи, например, он может составлять 1-2 байта. Но размер указателей может быть намного больше, особенно на x64 - размером 8 байт.