указатели — C ++: Какой тип данных в STXXL подходит для создания дерева бинарного поиска внешней памяти?
Я хочу создать структуру данных дерева двоичного поиска внешней памяти, данные которой находятся во внешней памяти с помощью stxxl как библиотека.
Для этого какой тип данных в STXXL подходит для использования в качестве узлов в дереве. Если мы используем stxxl: Vector в качестве Узлов дерева, как мы будем держать указатели на них.
Я прочитал в STXXL: векторную документацию, что явно невозможно использовать указатели, что очень логично для понимания.
Предупреждение:
Не храните ссылки на элементы внешнего вектора. Такие ссылки могут быть признаны недействительными во время любого следующего доступа к
элементы вектора.
Тогда возникает вопрос: что является альтернативой для хранения структуры данных бинарного дерева поиска с использованием типов данных ‘stxxl’?
Решение
Храните итераторы, указывающие на элементы вместо указателей / ссылок на элементы. Указатели / ссылки будут признаны недействительными из-за подкачки на / с диска, но итераторы не будут признаны недействительными.
Пример:
// Safe to store this, not safe to store &nodes[node_index].
stxxl::vector<Node>::iterator node_it = nodes.begin() + node_index;
… а также const_iterator только для чтения.
node_it не будет признан недействительным, если элемент не будет удален. В отличие от STL, он даже не становится недействительным, если вы делаете такие вещи, как push_back, Разыменование будет записывать / читать страницы на / с диска (только чтение для const_iterator), и поэтому вы можете рассматривать его как указатель, который не становится недействительным.
Другие решения
Вы можете сохранить непосредственно stxxl :: vector в структуре узла. Однако при использовании и обходе узлов вам нужно возвращать ссылку на вектор, а не на сам вектор. Если вы вернете вектор напрямую, вы его глубоко скопируете, что невозможно. Возврат ссылок из существующего узла — это безопасный способ использования:
const stxxl::vector<int> &Node::getVectorFromNode() const
{
return _VectorNodeMember;
}