Мысли о том, как реализовать?

Question

Я портирую очень старый c-код на c ++ и наткнулся на связанный список, реализованный в массиве Элемент имеет простую структуру:

struct element
{
    void *m_ptrData;
    short m_nextEntry;
    short m_prevEntry;
};

В виде массива имеется быстрый доступ к данным, если вы знаете индекс. Аспект связанного списка позволяет перемещать элементы и «удалять» из списка. Элементы могут быть перемещены в списке в зависимости от частоты использования (вверх для MRU и вниз для LRU).

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

У кого-нибудь есть мысли?

Answer 1

Поскольку это связанный список, вам, вероятно, следует использовать std :: list ...

Практическое правило заключается в том, что вы хотите использовать связанный список, когда вам нужновставьте элементы в случайные позиции в списке или удалите случайные элементы из списка.Если вам в основном нужно добавлять / удалять элементы в конец списка, используйте std::vector.Если вам нужно добавить / удалить элементы в начале или в конце списка, тогда вы должны использовать std::deque.

Имейте в виду, мы говорим о вероятностях здесь.Если вам нужно вставить элемент в середину std::vector один раз в синей луне, это, вероятно, будет в порядке.Но если вам нужно делать это все время, это окажет серьезное влияние на производительность, поскольку вектор должен будет постоянно перемещать свои элементы и, вероятно, перераспределять свою память.

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

Answer 2

Поскольку данные в этом списке являются указателями, зачем вообще связываться со связанным списком? Для небольших POD std::vector обычно является наилучшей первой ставкой, и из-за лучшей локализации своих данных, хорошо играющих с кэшем процессора, он часто превосходит связанный список, даже если теоретически связанный список должен быть лучше. Я бы выбрал std::vector, пока какое-нибудь профилирование не покажет, что есть проблема с производительностью, а std::list работает лучше.

Answer 3

Смотрите здесь:

http://linuxsoftware.co.nz/cppcontainers.html

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