Шаблон проектирования для структуры данных - PullRequest
Новая
       15

Шаблон проектирования для структуры данных

3 голосов
/ 12 июля 2011

На этот вопрос дан ответ, поэтому ниже следует объяснение того, чего я хотел достичь.

Я хотел создать табличную структуру данных, предназначенную для эффективного доступа к любой записи строки через первичный столбец, который может быть хеширован. Я подумал, что лучший способ сделать это - сохранить вектор двусвязных списков, каждый из которых будет представлять один столбец, и карту, которая будет содержать сопоставления хэшей записей первичного столбца с узлами. Теперь первая ошибка, которую я сделал, заключалась в том, что мне нужно было бы создать собственную реализацию двусвязного списка, чтобы иметь возможность хранить указатели на узлы, хотя фактически стандарт утверждает, что итераторы для std :: list делают не становится недействительным в результате вставки или сплайсинга (см. ответ Ларсмана). Вот некоторый псевдокод, чтобы проиллюстрировать то, что я хотел сделать ранее. Предположим, что существует типовое имя T, представляющее тип записи, и существование dlist и класса узла, как описано ранее. 

typedef dlist<T> column_type;
typedef vector<T> row_type;
typedef ptr_unordered_map<int32_t, row_type> hash_type;

shared_ptr<ptr_vector<column_type> > columns;
shared_ptr<hash_type> hashes;

Теперь, прочитав ответ Ларсмана, я узнал, что мне это не понадобится, так как Boost.MultiIndex полностью удовлетворяет все мои потребности. Даже если бы я это сделал, Boost.Intrusive предлагает более эффективные структуры данных для выполнения того, что я описываю.

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

1 Ответ

3 голосов
/ 12 июля 2011

front() должен возвращать ссылку на узел, содержащий value_type

Похоже, вы думаете о begin вместо front, в терминах STL / Boost,за исключением того, что методы begin обычно возвращают итераторы вместо ссылок.

Как бы я мог использовать карту ключевых хешей для типов std::list::iterator и разрешить добавление строк без записи вкарта устарела

Просто сделай;«list обладают важным свойством, что вставка и объединение не делают недействительными итераторы для перечисления элементов, и что даже удаление делает недействительными только итераторы, которые указывают на удаляемые элементы» ( STL docs ).

Если вы хотите, вы можете сохранить один std::list для всей таблицы и vector итераторов в ней для представления начальных точек строк.

Кроме того, вы смотрели на Boost.Intrusive и Boost.MultiIndex ? А знаете ли вы, что std::map (красно-черное дерево) хэшей - это очень неоптимальный способ представления хеш-таблицы?

...