Итерация последовательности при ее изменении. Использовать вектор или список? C ++ / STL

Question

Предположим, у меня есть длинная последовательность неупорядоченных элементов S s1, s2, s3,.... произвольного, но фиксированного типа данных, через которые я хочу выполнить итерацию и удалить определенные элементы в соответствии с некоторым логическим критерием.

Теперь, если после итерации последовательности, если я не заинтересован в окончательном упорядочении последовательности, то я могу сохранить свою последовательность двумя способами

1. Используйте обычный ol 'std::list для представления последовательности.Выполните удаление с помощью методов std :: list.
2. Используйте std::vector для представления последовательности.Если определенный элемент не соответствует критерию и должен быть удален, поменяйте его местами с последним векторным элементом и выполните pop_back.

Мои вопросы

1.Каким будет лучший / эффективный способ хранения моей последовательности по времени и / или по памяти?

2. Если бы мне пришлось рисковать, я бы сказал, список, потому что, если объем памяти типа данных si большой, подкачка будет дорогой.Будет ли это рассуждение правильным?

Answer 1

На практике std::vector имеет большое преимущество в производительности по сравнению с другими контейнерами из-за ограниченного объема памяти.Если ваши элементы, кроме того, являются подвижными (т. Е. Недорогими для обмена), то ваш второй вариант должен быть вашей первой попыткой.Реализуйте его с помощью стандартной удалить / стереть идиома:

v.erase(std::remove_if(v.begin(), v.end(), predicate), v.end());

Вы должны также установить вторую версию с std::list и сравнить производительность:

l.remove_if(predicate);

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

(Предположительно, если ваш тип элемента огромен, как sizeof(T) > 10000, список, вероятно, начнет работать быстрее, чем вектор. Протестируйте и сравните, и сделайте ваш код модульным, чтобы потом было проще его изменить.)

Answer 2

Если у вас есть компилятор C ++ 11 или, по крайней мере, ссылка на rvalue, использование swap ничего не будет стоить, если ваш тип данных не плоский (т. Е. Содержит указатели на внешние ресурсы или, другими словами, стоит дорого). копировать), так как он просто переместит ваши структуры вокруг. Поэтому, если у вас есть такой компилятор, создайте конструктор перемещения (подробнее об этом) для типа данных, и все готово. Просто используйте std::vector с этого момента.

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

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

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

Answer 3

Почти во всех практических случаях сначала используйте std::vector.Как всегда, сначала напишите свой код, а затем оптимизируйте, если и когда это необходимо.Если ваш профилировщик указывает, что причиной является неэффективность vector, попробуйте список.Я почти никогда не видел преимущества в производительности от этого.

Answer 4

Мы можем только догадываться. Я бы сказал, что если объекты легко копируются (например, базовые типы), то std::vector будет более эффективным, так как удаление элементов не будет выделять / перераспределять / освобождать любую память. Но если стоимость копирования элементов значительна, то std::list будет лучше.

Но учтите, что в C ++ 11 копия будет преобразована в перемещение, поэтому вам следует учитывать стоимость перемещения, которая, вероятно, будет значительно меньше, чем копия.