Самая быстрая динамическая структура данных в С++

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

отредактирован: Мне очень жаль, что я не включил в свой вопрос все важные моменты; ниже я бы попытался добавить дополнительную информацию:

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

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

4 ответа

Хорошее короткое сравнение контейнеров STL:

http://john-ahlgren.blogspot.com/2013/10/stl-container-performance.html

Если вам удастся использовать ассоциативный массив, карты, по крайней мере, гарантируют время вставки/поиска O (log n), которое является хорошим бит быстрее для больших объемов данных/множеств вставок и удалений, чем векторная гарантия O (n) для обратных вставок.

Не уверен, что они будут работать здесь или нет, эта ссылка также показывает некоторые графики тестов, используя случайные вставки/удаления/поиска/заливки/сортировки и т.д. В нескольких разных контейнерах:

http://www.baptiste-wicht.com/2012/12/cpp-benchmark-vector-list-deque/

Наконец, блок-схема из SO, которая может помочь вам принять решение о контейнере:

В каком сценарии я использую конкретный контейнер STL?

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


Будет ли связанный список реализован с использованием массива в соответствии с вашими потребностями?

class AList
{ public: AList() { for (int = 0; i != 256; ++i ) { nodes[i].prev = (i-1+256)%256; nodes[i].next = (i+1)%256; } } int const& operator[](int index) { // Deal with the case where nodes[index].isSet == false return nodes[index].data; } // Not sure what the requirements are for adding // and removing items from the list. // // add(); // remove(); private: struct Node { Node() : data(0), prev(0), next(0), isSet(false) {} int data; unsigned char prev; unsigned char next; bool isSet; }; Node nodes[256];
};


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

licensed under cc by-sa 3.0 with attribution.