Эффективный связанный список в С++?

Ответ 1

Требование о недействительности итераторов, исключающее исключение из удаляемого node, запрещается для каждого контейнера, который не выделяет отдельные узлы, и сильно отличается от, например, list или map.
Тем не менее, я обнаружил, что почти в каждом случае, когда я думал, что это было необходимо, оказалось, что с небольшой дисциплиной я мог бы обойтись без этого. Возможно, вы захотите проверить, можете ли вы это сделать, вы бы очень выиграли.

Хотя std::list действительно является "правильной" вещью, если вам нужно что-то вроде списка (в основном для класса CS), утверждение, что это почти всегда неправильный выбор, несчастливо, совершенно правильно. Хотя требование O (1) полностью верно, оно тем не менее ужасно по отношению к тому, как работает компьютерное оборудование, что придает ему огромный постоянный фактор. Обратите внимание, что не только объекты, которые вы произвольно размещаете, но и узлы, которые вы поддерживаете, тоже (да, вы можете как-то обойти это с помощью распределителя, но это не так). В среднем у вас есть два одного гарантированного промаха в кэше для всего, что вы делаете, плюс до двух одно динамическое распределение для операций с мутированием (одно для объекта, а другое для node).

Изменить: Как указано в @ratchetfreak ниже, реализации std::list обычно сворачивают объект и node выделение в один блок памяти в качестве оптимизации (аналогично тому, что, например, make_shared делает), что делает средний случай несколько менее катастрофическим (одно выделение на мутацию и один гарантированный промах кеша вместо двух).
В этом случае новое, другое соображение может состоять в том, что выполнение этого может быть не совсем безотказным. Постановка объекта двумя указателями означает изменение направления, в то время как разыменование, которое может помешать автоматической предварительной выборке.
С другой стороны, префикс объекта указателями означает, что вы возвращаете объект обратно с помощью двух указателей, что будет означать до 16 байт в 64-битной системе (это может привести к разделению объекта среднего размера по линии кэша границы каждый раз). Кроме того, следует учитывать, что std::list не может позволить себе разорвать, например. SSE-код исключительно потому, что он добавляет скрытое смещение как особый сюрприз (так, например, xor-трюк, вероятно, не применим для уменьшения следа с двумя указателями). Вероятно, должно быть некоторое количество "безопасных" дополнений, чтобы убедиться, что объекты, добавленные в список, все еще работают так, как им нужно.
Я не могу сказать, являются ли это реальными проблемами с производительностью или просто недоверие и страх с моей стороны, но я считаю справедливым сказать, что в траве может быть больше змей, чем можно ожидать.

Это не без причины, что высококлассные эксперты С++ (особенно Stroustrup) рекомендуют использовать std::vector, если у вас нет по-настоящему уважительной причины.

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

Если требование не отменять итераторы действительно является абсолютной необходимостью, вы можете, например, пару a std::vector объектов с динамическим битрейтом или, из-за отсутствия чего-то лучшего, std::vector<bool>. Затем используйте reserve() соответственно, чтобы перераспределения не выполнялись. При удалении элемента не удаляйте его, а только помечайте его как удаленное в растровом изображении (вызовите деструктор вручную). В подходящее время, когда вы знаете, что это нормально, чтобы аннулировать итераторы, вызовите функцию "пылесос", которая уплотняет как бит-вектор, так и вектор объекта. Там исчезли все непредвиденные итерационные аннулирования.

Да, это требует, чтобы один дополнительный бит "элемент был удален", что раздражает. Но a std::list должен поддерживать два указателя, в дополнение к фактическому объекту, и он должен делать распределения. С вектором (или двумя векторами) доступ по-прежнему очень эффективен, как это происходит в кэше. Итерация, даже при проверке удаленных узлов, по-прежнему означает, что вы перемещаетесь линейно или почти линейно по памяти.

Ответ 2

Ваши требования в точности соответствуют требованиям std::list, за исключением того, что вы решили, что вам не нравятся накладные расходы на распределение node.

Здравый подход состоит в том, чтобы начать сверху и делать столько, сколько вам нужно:

• Просто используйте std::list.

  Бенчмарк: распределитель по умолчанию слишком медленный для ваших целей?

  • Нет: все готово.

  • Да: goto 2

• Используйте std::list с существующим настраиваемым распределителем, таким как распределитель пула Boost

  Оцените это: распределяющий пул Boost слишком медленный для ваших целей?

  • Нет: все готово.

  • Да: goto 3

• Используйте std::list с помощью ручного настраиваемого распределителя, точно настроенного на ваши уникальные потребности, на основе всего профилирования, которое вы сделали в шагах 1 и 2

  Тест, как раньше и т.д. и т.д.

• Подумайте о том, чтобы сделать что-то более экзотическое в крайнем случае.

  Если вы дойдете до этого этапа, у вас должен быть очень хорошо заданный вопрос SO, с большим количеством подробностей о том, что вам нужно (например, "Мне нужно сжать n узлов в келин", а не "этот документ" эта вещь медленная, и это звучит плохо ").

PS. Вышеизложенное делает два предположения, но оба заслуживают внимания:

• как указывает Baum mit Augen, недостаточно сделать простой сквозной выбор времени, потому что вам нужно быть уверенным, где ваше время идет. Это может быть сам распределитель, или промахи кэша из-за макета памяти или что-то еще. Если что-то медленно, вы все равно должны быть уверены, почему, прежде чем вы знаете, что должно измениться.

• ваши требования принимаются как заданные, но поиск способов ослабления требований часто является самым простым способом сделать что-то быстрее.

  • Вам действительно нужна постоянная вставка и удаление во всюду или только спереди или сзади, или обе, но не посередине?
  • Вам действительно нужны те ограничения аннулирования итератора, или они могут быть смягчены?
  • Есть ли шаблоны доступа, которые вы можете использовать? Если вы часто удаляете элемент с фронта, а затем заменяете его новым, можете ли вы просто обновить его на месте?

Ответ 3

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

Неиспользуемые элементы массива помещаются в связанный список, используя одну из ссылок. Когда элемент удаляется, он возвращается в свободный список. Когда свободный список исчерпан, увеличьте массив и используйте следующий элемент.

Для новых свободных элементов у вас есть два варианта:

• добавьте их в бесплатный список сразу,
• добавить их по запросу, исходя из количества элементов в свободном списке и размера массива.

Ответ 4

std::list является двусвязным списком, поэтому, несмотря на его неэффективность в построении элементов, он поддерживает вставку/удаление в O (1) временную сложность, но эта функция полностью игнорируется в этом цитируемом параграфе.

Он игнорировал , потому что это ложь.

Проблема алгоритмической сложности состоит в том, что она вообще измеряет одно. Например, когда мы говорим, что вставка в std::map равна O (log N), мы имеем в виду, что она выполняет сравнения O (log N). Затраты на итерацию, выборку строк кэша из памяти и т.д. Не учитываются.

Это значительно упрощает анализ, конечно, но, к сожалению, не обязательно однозначно отображает сложности реализации в реальном мире. В частности, одно вопиющее предположение заключается в том, что распределение памяти является постоянным временем. И это - смелая ложь.

Распределители памяти общего назначения (malloc и co) не имеют гарантии на наихудшую сложность распределения памяти. В худшем случае, как правило, зависит от ОС, а в случае с Linux он может включать убийцу OOM (просеивать текущие процессы и убивать одного, чтобы восстановить его память).

Специальные распределители памяти потенциально могут быть сделаны постоянным временем... в определенном диапазоне количества распределений (или максимального размера выделения). Поскольку обозначение Big-O имеет предел на бесконечности, его нельзя назвать O (1).

И, таким образом, когда резинка встречает дорогу, реализация std::list НЕ содержит в целом функцию O (1) вставки/удаления, потому что реализация зависит от реального распределителя памяти, а не от идеального.

Это довольно удручающее, но вам не нужно терять надежды.

В первую очередь, если вы можете определить верхнюю границу числа элементов и можете выделить столько памяти вверх, тогда вы можете создать распределитель памяти, который будет выполнять распределение памяти по постоянному времени, что даст вам иллюзию O (1).

Ответ 5

Используйте два std::list s: один "свободный список", который был предварительно распределен с большим количеством узлов при запуске, а другой "активный" список, в который вы splice узлы из свободного списка. Это постоянное время и не требует выделения node.

Ответ 6

Новое предложение slot_map требует O (1) для вставки и удаления.

Существует также ссылка на видео с предлагаемой реализацией и некоторыми предыдущими работами.

Если бы мы знали больше о фактической структуре элементов, могут быть некоторые специализированные ассоциативные контейнеры, которые намного лучше.

Ответ 7

Я бы предложил сделать то, что говорит @Yves Daoust, за исключением использования связанного списка для бесплатного списка, используйте вектор. Нажмите и нажмите свободные индексы на обратной стороне вектора. Это амортизируется O (1), вставляет, ищет и удаляет, и не предполагает какого-либо преследования курсора. Это также не требует никакого раздражающего бизнеса распределителя.

Ответ 8

I второй ответ @Useless, особенно пункт PS 2 о пересмотре требований. Если вы ослабляете ограничение аннулирования итератора, то использование std::vector<> стандартное предложение Stroustrup для контейнера с небольшим количеством предметов (по причинам уже упоминалось в комментариях). Связанный с нами questions на SO.

Начиная с С++ 11 существует также std::forward_list.

Кроме того, если стандартное распределение кучи для элементов, добавленных в контейнер, недостаточно хорош, я бы сказал, что вам нужно очень внимательно смотреть на ваши точные требования и тонкую настройку для них.

Ответ 9

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

Но в любом случае я отвлекаюсь на две отличные советы, которые я хотел раскрыть. С векторными вставками может быть дорого, так что аккуратный трюк, не вставляйте, если вы можете уйти, не делая этого. сделайте обычный push_back (положите в конец), затем поменяйте элемент тем, который вы хотите.

То же самое с удалением. Они дорогие. Поэтому замените его последним элементом, удалите его.

Ответ 10

Спасибо за все ответы. Это простой, хотя и не строгий тест.

// list.cc
#include <list>
using namespace std;

int main() {
    for (size_t k = 0; k < 1e5; k++) {
        list<size_t> ln;
        for (size_t i = 0; i < 200; i++) {
            ln.insert(ln.begin(), i);
            if (i != 0 && i % 20 == 0) {
                ln.erase(++++++++++ln.begin());
            }
        }
    }
}

и

// vector.cc
#include <vector>
using namespace std;

int main() {
    for (size_t k = 0; k < 1e5; k++) {
        vector<size_t> vn;
        for (size_t i = 0; i < 200; i++) {
            vn.insert(vn.begin(), i);
            if (i != 0 && i % 20 == 0) {
                vn.erase(++++++++++vn.begin());
            }
        }
    }
}

Этот тест предназначен для проверки того, что std::list претендует на то, чтобы преуспеть при - O (1) вставке и стирании. И из-за позиций, которые я прошу вставить/удалить, эта гонка сильно искажена против std::vector, потому что она должна сдвигать все следующие элементы (следовательно, O (n)), а std::list не нужно делать что.

Теперь я их компилирую.

clang++ list.cc -o list
clang++ vector.cc -o vector

И проверьте время выполнения. Результат:

  time ./list
  ./list  4.01s user 0.05s system 91% cpu 4.455 total
  time ./vector
  ./vector  1.93s user 0.04s system 78% cpu 2.506 total

std::vector выиграл.

Скомпилирован с оптимизацией O3, std::vector по-прежнему побеждает.

  time ./list
  ./list  2.36s user 0.01s system 91% cpu 2.598 total
  time ./vector
  ./vector  0.58s user 0.00s system 50% cpu 1.168 total

std::list должен вызывать распределение кучи для каждого элемента, тогда как std::vector может выделять кучную память в пакетном режиме (хотя он может быть зависим от реализации), поэтому std::list insert/delete имеет более высокий постоянный множитель, хотя это O (1).

Неудивительно, что этот документ говорит

std::vector хорошо любим и уважаем.

EDIT: std::deque в некоторых случаях даже лучше, по крайней мере для этой задачи.

// deque.cc
#include <deque>
using namespace std;

int main() {
    for (size_t k = 0; k < 1e5; k++) {
        deque<size_t> dn;
        for (size_t i = 0; i < 200; i++) {
            dn.insert(dn.begin(), i);
            if (i != 0 && i % 20 == 0) {
                dn.erase(++++++++++dn.begin());
            }
        }
    }
}

Без оптимизации:

./deque  2.13s user 0.01s system 86% cpu 2.470 total

Оптимизировано с помощью O3:

./deque  0.27s user 0.00s system 50% cpu 0.551 total

Ответ 11

Самый простой способ, который я вижу для выполнения всех ваших требований:

• Вставка/удаление с постоянной задержкой (надежное амортизированное постоянное время подходит для вставки).
• Отсутствие выделения/освобождения кучи на элемент.
• Недействительность iterator при удалении.

... будет что-то вроде этого, просто используя std::vector:

template <class T>
struct Node
{
    // Stores the memory for an instance of 'T'.
    // Use placement new to construct the object and
    // manually invoke its dtor as necessary.
    typename std::aligned_storage<sizeof(T), alignof(T)>::type element;

    // Points to the next element or the next free
    // element if this node has been removed.
    int next;

    // Points to the previous element.
    int prev;
};

template <class T>
class NodeIterator
{
public:
    ...
private:
    std::vector<Node<T>>* nodes;
    int index;
};

template <class T>
class Nodes
{
public:
    ...
private:
    // Stores all the nodes.
    std::vector<Node> nodes;

    // Points to the first free node or -1 if the free list
    // is empty. Initially this starts out as -1.
    int free_head;
};

... и, надеюсь, с лучшим именем, чем Nodes (я слегка подвыпивший и не очень хорошо придумываю имена на данный момент). Я оставлю реализацию до вас, но это общая идея. Когда вы удаляете элемент, просто удалите двусвязный список с помощью индексов и нажмите его на свободную головку. Итератор не делает недействительным, так как он хранит индекс для вектора. Когда вы вставляете, проверьте, свободна ли голова -1. Если нет, перепишите node в эту позицию и нажмите. В противном случае push_back к вектору.

Иллюстрация

Диаграмма (узлы хранятся смежно внутри std::vector, мы просто используем индексные ссылки, чтобы пропускать элементы без ветвления вместе с удалением и вставками с постоянным временем в любом месте):

Скажем, мы хотим удалить node. Это стандартное удаление ссылок с двойным связыванием, за исключением того, что мы используем индексы вместо указателей, а также вытесняем node в свободный список (который включает в себя только манипулирование целыми числами):

Устранение настроек ссылок:

Удаленное удаление node в список:

Теперь скажем, что вы вставляете этот список. В этом случае вы удаляете свободную головку и перезаписываете node в этой позиции.

После вставки:

Вставка в середину в постоянное время также должна быть легко понята. В основном вы просто вставляете в свободную головку или push_back в вектор, если свободный стек пуст. Затем вы выполняете стандартную двойную привязку списка. Логика для бесплатного списка (хотя я сделал эту диаграмму для кого-то еще, и она включает SLL, но вы должны получить идею):

Удостоверьтесь, что вы правильно создаете и уничтожаете элементы, используя размещение новых и ручных вызовов на dtor при вставке/удалении. Если вы действительно хотите обобщить его, вам также нужно подумать об исключении-безопасности, и нам также нужен константный итератор, доступный только для чтения.

Плюсы и минусы

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

Для достаточно больших списков (скажем, больше, чем весь ваш кеш L3 в случае, когда вам обязательно нужно ожидать огромного края), это должно значительно превзойти std::vector для удаления и вставки в/из середины и спереди. Удаление элементов из вектора может быть довольно быстрым для небольших, но попробуйте удалить миллион элементов из вектора, начиная с фронта и работая в направлении назад. Там начнутся ползания, пока этот кончится в мгновение ока. std::vector - это когда-либо слишком мало, чем когда-либо, IMO, когда люди начинают использовать свой метод erase для удаления элементов из середины вектора, охватывающего 10k элементов или более, хотя я полагаю, что это все же предпочтительнее людей, наивно используя связанные списки во всем мире способ, при котором каждый node индивидуально распределяется против универсального распределителя, в то время как кеширует недостатки в изобилии.

Недостатком является то, что он поддерживает только последовательный доступ, требует накладных расходов на два целых числа на элемент, и, как вы можете видеть на приведенной выше диаграмме, его пространственная локальность ухудшается, если вы постоянно удаляете вещи спорадически.

Деградация пространственной локализации

Потеря пространственной локации при запуске удаления и вставке большого количества из/в середину приведет к созданию шаблонов доступа к zig-zagging памяти, потенциально вытесняющим данные из строки кэша только для возврата и перезагрузки в течение одного последовательного петля. Это, как правило, неизбежно в любой структуре данных, которая позволяет абстрагироваться из середины в постоянное время, а также позволяет освободить это пространство, сохраняя при этом порядок вставки. Однако вы можете восстановить пространственную локальность, предложив какой-либо метод, или вы можете скопировать/заменить список. Конструктор копий может скопировать список таким образом, который выполняет итерацию через исходный список и вставляет все элементы, которые возвращают совершенно смежный, кэш-вектор, без отверстий (хотя это приведет к недействительности итераторов).

Альтернатива: Free List Allocator

Альтернативой, которая соответствует вашим требованиям, является реализация бесплатного списка, соответствующего std::allocator, и используйте его с std::list. Мне никогда не нравилось обходить структуры данных и беспорядочно взаимодействовать с пользовательскими распределителями, и это позволило бы удвоить использование ссылок на 64-битной памяти с помощью указателей вместо 32-разрядных индексов, поэтому я предпочел бы, чтобы вышеупомянутое решение лично использовало std::vector как в основном ваш аналоговый распределитель памяти и индексы вместо указателей (которые уменьшают размер и становятся требованием, если мы используем std::vector, поскольку указатели будут недействительными, когда вектор резервирует новую емкость).

Индексированные связанные списки

Я называю этот тип "индексированным связанным списком", поскольку связанный список на самом деле не является контейнером, а также способ связывания вещей, которые уже хранятся в массиве. И я нахожу эти индексированные связанные списки экспоненциально более полезными, так как вам не нужно получать колено в пулах памяти, чтобы избежать распределения/освобождения кучи на node и все равно поддерживать разумную локальность ссылок (большой LOR, если вы можете позволить себе пост-процесс вещей здесь и там, чтобы восстановить пространственную локальность).

Вы также можете сделать это односвязным, если вы добавите еще одно целое к итератору node для хранения предыдущего индекса node (поставляется бесплатно с зарядом памяти на 64-битной основе, предполагая 32-разрядные требования к выравниванию для int и 64-бит для указателей). Однако вы теряете возможность добавить обратный итератор и сделать все итераторы двунаправленными.

Benchmark

Я взломал быструю версию выше, так как вы, похоже, заинтересованы в em: release, MSVC 2012, не проверенные итераторы или что-то в этом роде:

--------------------------------------------
- test_vector_linked
--------------------------------------------
Inserting 200000 elements...
time passed for 'inserting': {0.000015 secs}

Erasing half the list...
time passed for 'erasing': {0.000021 secs}
time passed for 'iterating': {0.000002 secs}
time passed for 'copying': {0.000003 secs}

Results (up to 10 elements displayed):
[ 11 13 15 17 19 21 23 25 27 29 ]

finished test_vector_linked: {0.062000 secs}
--------------------------------------------
- test_vector
--------------------------------------------
Inserting 200000 elements...
time passed for 'inserting': {0.000012 secs}

Erasing half the vector...
time passed for 'erasing': {5.320000 secs}
time passed for 'iterating': {0.000000 secs}   
time passed for 'copying': {0.000000 secs}

Results (up to 10 elements displayed):
[ 11 13 15 17 19 21 23 25 27 29 ]

finished test_vector: {5.320000 secs}

Было слишком лениво использовать высокоточный таймер, но, надеюсь, это дает представление о том, почему нельзя использовать метод vector's linear-time erase в критических путях для нетривиальных размеров ввода с vector выше там, где ~ 86 раз больше (и экспоненциально хуже, чем размер ввода - я попытался с 2 миллионами элементов изначально, но сдался после ожидания почти 10 минут), и почему я думаю, что vector когда-либо слишком слегка завышен для этого вид использования. Тем не менее, мы можем превратить удаление из середины в очень быструю операцию с постоянным временем, не перетасовывая порядок элементов, не отменяя индексы и итераторы, сохраняя их, и все еще используя vector... Все, что нам нужно сделать, это просто заставьте его сохранить связанный node с prev/next индексы, чтобы разрешить пропуски удаленных элементов.

Для удаления я использовал случайный перетасованный вектор источника индексов с четными номерами, чтобы определить, какие элементы удалить и в каком порядке. Это несколько напоминает реальный случай использования в мире, когда вы удаляете середину этих контейнеров с помощью индексов/итераторов, которые вы ранее получали, например, удаление элементов, ранее выбранных пользователем с помощью инструмента выделения после его кнопки удаления (и, опять же, вы на самом деле не следует использовать скаляр vector::erase для этого с нетривиальными размерами, было бы даже лучше создать набор индексов для удаления и использования remove_if - еще лучше, чем vector::erase, для одного итератора время).

Обратите внимание, что итерация становится немного медленнее с связанными узлами, и это не связано с логикой итерации, так как тот факт, что каждая запись в векторе больше с добавленными ссылками (больше памяти для последовательного процесса equate к большему количеству промахов и ошибок страницы). Тем не менее, если вы делаете такие вещи, как удаление элементов из очень больших входов, перекос производительности настолько эпический для больших контейнеров между линейным и постоянным удалением, что обычно имеет смысл обмена.