Есть std::list<MyClass> list
с 10000+ элементов
Есть int n = 500;
Нужно удалить первые n
элементов.
Как сделать это максимально быстро?
Stack Overflow на русском — это сайт вопросов и ответов для программистов. Присоединяйтесь! Регистрация займёт не больше минуты.
Присоединиться к сообществуЕсть std::list<MyClass> list
с 10000+ элементов
Есть int n = 500;
Нужно удалить первые n
элементов.
Как сделать это максимально быстро?
Сделал такой пример чтобы проверить возможность не удалять ненужные элементы, а создать список только с нужными элементами:
std::list<int> data;
for (int index = 0; index < 10000; index++)
data.push_back(index);
__int64 t1;
::QueryPerformanceCounter((LARGE_INTEGER*)&t1);
std::list<int>::iterator range_end = data.begin();
std::advance(range_end, 500);
std::list<int> data2;
data2.insert(data2.begin(), range_end, data.end());
__int64 t2;
::QueryPerformanceCounter((LARGE_INTEGER*)&t2);
std::cout << (t2 - t1) << std::endl;
Промерил разные скорости
Ситуация такая:
до определённого кол-ва удаляемых элементов выгоднее удалять из списка элементы, после определённого кол-ва элементов - создавать новый список, а старый список удалять потом (если такая возможность есть)
Но по большей части все может упираться в конструктор и деструктор вашего класса MyClass
, так что работа со списком уже не будет иметь никакого существенного значения
P.S.
опять же вопрос - что именно вам нужно
если вам нужно часто создавать и удалять элементы списка, причем где-то посередине списка - тогда конечно std::list
- это ваше,
если добавляются и удаляются элементы только в конце - тогда std::vector
- это более оптимальное (и быстрое и памяти меньше кушает) решение
если удаление и добавление элементов происходит гораздо реже, чем получение значений элементов, тогда опять таки зачастую std::vector
подходит гораздо лучше
P.P.S.
Но splice
гораздо выгоднее insert
, ГОРАЗДО ВЫГОДНЕЕ!!!
P.S. специально показал логарифмическую шкалу, чтобы была понятна мощь splice
:)
insert
, а splice
? он должен работать за константное время; insert
все же данные копирует.
Стандартно - использовать erase
Как вариант - перенести ненужные элементы в другой список за константное время, который потом убить.
void kill(list<int>& l, size_t count)
{
list<int> tmp;
auto it = l.begin();
advance(it,count);
tmp.splice(tmp.begin(),l,l.begin(),it);
}
Что быстрее - надо сравнивать экспериментально...
Как показал эксперимент, обычный erase
все же несколько быстрее.