Если вам нужны стабильные индексы или указатели, то ваши требования к структуре данных начинают напоминать требования к распределителю памяти. Распределители памяти также являются особым типом структуры данных, но сталкиваются с требованием, что они не могут перетасовывать или перераспределять память, поскольку это сделало бы недействительными указатели, сохраненные клиентом. Так что я рекомендую посмотреть на реализации распределителя памяти, начиная с классического свободного списка.
Бесплатный список
Вот простая реализация C, которую я написал, чтобы проиллюстрировать идею коллегам (не беспокоится о синхронизации потоков):
typedef struct FreeList FreeList;
struct FreeList
{
/// Stores a pointer to the first block in the free list.
struct FlBlock* first_block;
/// Stores a pointer to the first free chunk.
struct FlNode* first_node;
/// Stores the size of a chunk.
int type_size;
/// Stores the number of elements in a block.
int block_num;
};
/// @return A free list allocator using the specified type and block size,
/// both specified in bytes.
FreeList fl_create(int type_size, int block_size);
/// Destroys the free list allocator.
void fl_destroy(FreeList* fl);
/// @return A pointer to a newly allocated chunk.
void* fl_malloc(FreeList* fl);
/// Frees the specified chunk.
void fl_free(FreeList* fl, void* mem);
// Implementation:
typedef struct FlNode FlNode;
typedef struct FlBlock FlBlock;
typedef long long FlAlignType;
struct FlNode
{
// Stores a pointer to the next free chunk.
FlNode* next;
};
struct FlBlock
{
// Stores a pointer to the next block in the list.
FlBlock* next;
// Stores the memory for each chunk (variable-length struct).
FlAlignType mem[1];
};
static void* mem_offset(void* ptr, int n)
{
// Returns the memory address of the pointer offset by 'n' bytes.
char* mem = ptr;
return mem + n;
}
FreeList fl_create(int type_size, int block_size)
{
// Initialize the free list.
FreeList fl;
fl.type_size = type_size >= sizeof(FlNode) ? type_size: sizeof(FlNode);
fl.block_num = block_size / type_size;
fl.first_node = 0;
fl.first_block = 0;
if (fl.block_num == 0)
fl.block_num = 1;
return fl;
}
void fl_destroy(FreeList* fl)
{
// Free each block in the list, popping a block until the stack is empty.
while (fl->first_block)
{
FlBlock* block = fl->first_block;
fl->first_block = block->next;
free(block);
}
fl->first_node = 0;
}
void* fl_malloc(FreeList* fl)
{
// Common case: just pop free element and return.
FlNode* node = fl->first_node;
if (node)
{
void* mem = node;
fl->first_node = node->next;
return mem;
}
else
{
// Rare case when we're out of free elements.
// Try to allocate a new block.
const int block_header_size = sizeof(FlBlock) - sizeof(FlAlignType);
const int block_size = block_header_size + fl->type_size*fl->block_num;
FlBlock* new_block = malloc(block_size);
if (new_block)
{
// If the allocation succeeded, initialize the block.
int j = 0;
new_block->next = fl->first_block;
fl->first_block = new_block;
// Push all but the first chunk in the block to the free list.
for (j=1; j < fl->block_num; ++j)
{
FlNode* node = mem_offset(new_block->mem, j * fl->type_size);
node->next = fl->first_node;
fl->first_node = node;
}
// Return a pointer to the first chunk in the block.
return new_block->mem;
}
// If we failed to allocate the new block, return null to indicate failure.
return 0;
}
}
void fl_free(FreeList* fl, void* mem)
{
// Just push a free element to the stack.
FlNode* node = mem;
node->next = fl->first_node;
fl->first_node = node;
}
Последовательность с произвольным доступом, вложенные списки свободных мест
Когда идея бесплатного списка понята, одним из возможных решений является следующее:
Этот тип структуры данных даст вам стабильные указатели, которые не делают недействительными, а не только индексы. Однако это увеличивает стоимость произвольного доступа, а также последовательного доступа, если вы хотите использовать для него итератор. Он может выполнять последовательный доступ наравне с vector, используя что-то вроде метода for_each.
Идея состоит в том, чтобы использовать концепцию свободного списка выше, за исключением того, что каждый блок хранит собственный свободный список, а внешняя структура данных, объединяющая блоки, хранит свободный список блоков. Блок извлекается из свободного стека только тогда, когда он становится полностью заполненным.
Биты параллельной занятости
Другой способ — использовать параллельный массив битов, чтобы указать, какие части массива заняты/свободны. Преимущество здесь в том, что вы можете во время последовательной итерации проверить, занято ли сразу много индексов (64 бита одновременно, и в этот момент вы можете получить доступ ко всем 64 непрерывным элементам в цикле без индивидуальной проверки, чтобы увидеть, заняты ли они). заняты). Если не все 64 индекса заняты, вы можете использовать инструкции FFS, чтобы быстро определить, какие биты установлены. .
Вы можете комбинировать это со свободным списком, чтобы затем использовать биты для быстрого определения того, какие индексы заняты во время итерации, при быстрой вставке и удалении с постоянным временем.
На самом деле вы можете получить более быстрый последовательный доступ, чем std::vector, со списком индексов/указателей на стороне, поскольку, опять же, мы можем делать такие вещи, как проверка 64-бит сразу, чтобы увидеть, какие элементы нужно пройти внутри структуры данных, и потому что шаблон доступа всегда будет последовательным (аналогично использованию отсортированного списка индексов в массиве).
Все эти концепции вращаются вокруг того, чтобы оставить пустые места в массиве для восстановления при последующих вставках, что становится практическим требованием, если вы не хотите, чтобы индексы или указатели были признаны недействительными для элементов, которые не были удалены из контейнера.
Список односвязных индексов
Другим решением является использование односвязного списка, о котором большинство людей может подумать, что он включает в себя отдельное выделение кучи для каждого узла и множество промахов кеша при обходе, но это не обязательно так. Мы можем просто хранить узлы последовательно в массиве и связывать их вместе. На самом деле открывается мир возможностей для оптимизации, если вы думаете о связанном списке не столько как о контейнере, сколько о способе просто связать вместе существующие элементы, хранящиеся в другом контейнере, например массиве, чтобы обеспечить различные шаблоны обхода и поиска. Пример со всем, что только что сохранено в непрерывном массиве с индексами, чтобы связать их вместе:
С данными, хранящимися следующим образом:
struct Bucket
{
struct Node
{
// Stores the element data.
T some_data;
// Points to either the next node in the bucket
// or the next free node available if this node
// has been removed.
int next;
};
vector<Node> data;
// Points to first node in the bucket.
int head;
// Points to first free node in the bucket.
int free_head;
};
Это не допускает произвольного доступа, и его пространственная локализация ухудшается, если вы часто удаляете из середины и вставляете. Но его достаточно легко восстановить с помощью копии с постобработкой. Это может подойти, если вам нужен только последовательный доступ и вы хотите удалить и вставить постоянное время. Если вам нужны стабильные указатели, а не только индексы, вы можете использовать приведенную выше структуру с вложенным свободным списком.
Индексированный SLL, как правило, хорошо работает, когда у вас есть много небольших списков, которые очень динамичны (постоянные удаления и вставки). Другой пример с частицами, хранящимися смежно, но 32-битные индексные ссылки используются только для разделения их на сетку для быстрого обнаружения столкновений, позволяя частицам перемещаться в каждом отдельном кадре, и требуется изменить только пару целых чисел, чтобы перенести частицу из одного ячейку сетки в другую:
В этом случае вы можете хранить сетку 1000x1000 менее чем в 4 мегабайтах — это определенно лучше, чем хранить миллион экземпляров std::list или std::vector и постоянно удалять и вставлять из/в них по мере движения частиц.
Индексы занятости
Другое простое решение, если вам нужны только стабильные индексы, — это просто использовать, скажем, std::vector с std::stack<int> свободными индексами для восстановления/перезаписи при вставках. Это соответствует принципу свободного списка удаления за постоянное время, но немного менее эффективно, поскольку требует памяти для хранения стека свободных индексов. Бесплатный список делает стек бесплатным.
Однако, если вы не перевернете его вручную и не будете использовать только std::vector<T>, вы не сможете очень эффективно заставить его запускать деструктор типа элемента, который вы сохраняете при удалении (я не следил за C++, больше C программист в наши дни, но может быть способ сделать это красиво, который по-прежнему уважает ваши деструкторы элементов, не создавая вручную свой собственный эквивалент std::vector - возможно, эксперт по C++ мог бы вмешаться). Это может быть хорошо, если ваши типы являются тривиальными типами POD.
template <class T>
class ArrayWithHoles
{
private:
std::vector<T> elements;
std::stack<size_t> free_stack;
public:
...
size_t insert(const T& element)
{
if (free_stack.empty())
{
elements.push_back(element);
return elements.size() - 1;
}
else
{
const size_t index = free_stack.top();
free_stack.pop();
elements[index] = element;
return index;
}
}
void erase(size_t n)
{
free_stack.push(n);
}
};
Что-то в этом роде. Это оставляет нас перед дилеммой, поскольку мы не можем сказать, какие элементы были удалены из контейнера, чтобы пропустить их во время итерации. Здесь вы снова можете использовать параллельные битовые массивы или просто хранить список допустимых индексов сбоку.
Если вы сделаете это, список допустимых индексов может ухудшиться с точки зрения шаблонов доступа к памяти в массив, поскольку они со временем становятся несортированными. Быстрый способ исправить это — периодически сортировать индексы по основанию, после чего вы восстановите шаблон последовательного доступа.
person
Community
schedule
21.12.2017
id, (x, y, ptr, id) избавляет большинство запросов от необходимости дерефированияptrдля его получения, но может привести к увеличению количества страниц. ошибки повторяют очень большой индекс. - person kfsone schedule 21.10.2013