C ++: смесь между вектором и списком: что-то вроде std :: веревка?

Question

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

std::vector плохо, потому что:

• Он должен перераспределить, если он больше не подходит.
• Он не работает на огромных объемах данных (потому что вы не всегда можете получить очень большие куски непрерывного свободногопамять).

std::list плохо, потому что:

• Распределение выполняется для каждого отдельного push_back.Это медленно и приводит к большой фрагментации памяти.

Итак, я хочу что-то среднее между ними.

По сути, я хочу что-то вроде std::list< boost::array<T, 100> > или около того.Или, может быть, вместо 100, пусть будет 4096/sizeof(T).Может быть, также std::list< std::vector<T> >, и первые векторы могут быть маленькими, а затем могут расти другие.На самом деле я хочу, чтобы это было скрыто от использования, поэтому я могу просто сделать mycontainer.push_back(x).

std::rope немного похоже на это, но не доступно в стандарте.

Есть ли что-то подобное в Boost или около того?

Answer 1

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

Answer 2

Да, это называется std :: vector.Это O (1) время push_back, которое почти всегда быстрее, чем std :: list.(Да, и это также эффективно использует память)

Самая важная особенность std :: list - постоянное удаление / вставка из середины.Если вам это не нужно, выберите std :: vector.