Можете ли вы удалить элементы из списка std::list, просматривая его?
У меня есть код, который выглядит так:
for (std::list<item*>::iterator i=items.begin();i!=items.end();i++)
{
bool isActive = (*i)->update();
//if (!isActive)
// items.remove(*i);
//else
other_code_involving(*i);
}
items.remove_if(CheckItemNotActive);
Я хотел бы удалить неактивные элементы сразу после их обновления, чтобы избежать повторного просмотра списка. Но если я добавляю закомментированные строки, я получаю сообщение об ошибке, когда i++: "Итератор списка не может быть увеличен". Я попробовал несколько альтернатив, которые не увеличивались в выражении for, но я не мог заставить что-либо работать.
Какой лучший способ удалить элементы, когда вы ходите по стандартному списку?
15 ответов
Сначала нужно увеличить итератор (с помощью i++), а затем удалить предыдущий элемент (например, используя возвращаемое значение из i++). Вы можете изменить код на цикл while следующим образом:
std::list<item*>::iterator i = items.begin();
while (i != items.end())
{
bool isActive = (*i)->update();
if (!isActive)
{
items.erase(i++); // alternatively, i = items.erase(i);
}
else
{
other_code_involving(*i);
++i;
}
}
Ты хочешь сделать:
i= items.erase(i);
Это правильно обновит итератор, чтобы он указывал на местоположение после итератора, который вы удалили.
Вам нужно сделать комбинацию ответа Кристо и MSN:
// Note: Using the pre-increment operator is preferred for iterators because
// there can be a performance gain.
//
// Note: As long as you are iterating from beginning to end, without inserting
// along the way you can safely save end once; otherwise get it at the
// top of each loop.
std::list< item * >::iterator iter = items.begin();
std::list< item * >::iterator end = items.end();
while (iter != items.end())
{
item * pItem = *iter;
if (pItem->update() == true)
{
other_code_involving(pItem);
++iter;
}
else
{
// BTW, who is deleting pItem, a.k.a. (*iter)?
iter = items.erase(iter);
}
}
Конечно, самая эффективная и изощренная вещь SuperCool® STL будет выглядеть примерно так:
// This implementation of update executes other_code_involving(Item *) if
// this instance needs updating.
//
// This method returns true if this still needs future updates.
//
bool Item::update(void)
{
if (m_needsUpdates == true)
{
m_needsUpdates = other_code_involving(this);
}
return (m_needsUpdates);
}
// This call does everything the previous loop did!!! (Including the fact
// that it isn't deleting the items that are erased!)
items.remove_if(std::not1(std::mem_fun(&Item::update)));
У меня есть сумма, вот три метода с примером:
1. используя while петля
list<int> lst{4, 1, 2, 3, 5};
auto it = lst.begin();
while (it != lst.end()){
if((*it % 2) == 1){
it = lst.erase(it);// erase and go to next
} else{
++it; // go to next
}
}
for(auto it:lst)cout<<it<<" ";
cout<<endl; //4 2
2. используя remove_if членство в списке:
list<int> lst{4, 1, 2, 3, 5};
lst.remove_if([](int a){return a % 2 == 1;});
for(auto it:lst)cout<<it<<" ";
cout<<endl; //4 2
3. используя std::remove_if функция в сочетании с erase функция-член:
list<int> lst{4, 1, 2, 3, 5};
lst.erase(std::remove_if(lst.begin(), lst.end(), [](int a){
return a % 2 == 1;
}), lst.end());
for(auto it:lst)cout<<it<<" ";
cout<<endl; //4 2
4. используя for цикл, обратите внимание, обновить итератор:
list<int> lst{4, 1, 2, 3, 5};
for(auto it = lst.begin(); it != lst.end();++it){
if ((*it % 2) == 1){
it = lst.erase(it); erase and go to next(erase will return the next iterator)
--it; // as it will be add again in for, so we go back one step
}
}
for(auto it:lst)cout<<it<<" ";
cout<<endl; //4 2
Используйте алгоритм std::remove_if.
Изменить: Работа с коллекциями должна быть такой: 1. Подготовить коллекцию. 2. процесс сбора.
Жизнь будет проще, если вы не будете смешивать эти шаги.
- станд:: remove_if. или list::remove_if (если вы знаете, что работаете со списком, а не с TCollection)
- станд:: for_each
Вот пример использования for цикл, который выполняет итерацию списка и увеличивает или повторно проверяет итератор в случае удаления элемента во время обхода списка.
for(auto i = items.begin(); i != items.end();)
{
if(bool isActive = (*i)->update())
{
other_code_involving(*i);
++i;
}
else
{
i = items.erase(i);
}
}
items.remove_if(CheckItemNotActive);
Альтернатива петлевой версии ответу Кристо.
Вы теряете некоторую эффективность, вы возвращаетесь назад и затем снова вперед при удалении, но в обмен на дополнительное приращение итератора вы можете объявить итератор в области видимости цикла, и код выглядит немного чище. Что выбрать, зависит от приоритетов на данный момент.
Ответ был совершенно несвоевременным, я знаю...
typedef std::list<item*>::iterator item_iterator;
for(item_iterator i = items.begin(); i != items.end(); ++i)
{
bool isActive = (*i)->update();
if (!isActive)
{
items.erase(i--);
}
else
{
other_code_involving(*i);
}
}
Повторение в обратном направлении позволяет избежать эффекта стирания элемента на оставшихся элементах, которые необходимо пройти:
typedef list<item*> list_t;
for ( list_t::iterator it = items.end() ; it != items.begin() ; ) {
--it;
bool remove = <determine whether to remove>
if ( remove ) {
items.erase( it );
}
}
PS: смотрите это, например, относительно обратной итерации.
PS2: я не проверил тщательно, хорошо ли он стирает элементы на концах.
Удаление делает недействительными только итераторы, которые указывают на удаляемые элементы.
Таким образом, в этом случае после удаления * i, я становится недействительным, и вы не можете сделать приращение на нем.
Что вы можете сделать, это сначала сохранить итератор элемента, который должен быть удален, затем увеличить итератор и затем удалить сохраненный.
В C++20 вы можете использовать erease_if:
std::erease_if(items, [](auto& i){
if (!i.update()) {
return true;
}
other_code_involving(i);
return false;
};
Если вы думаете о std::list как очередь, тогда вы можете удалить из очереди и поставить в очередь все элементы, которые вы хотите сохранить, но только удалить из очереди (а не поставить в очередь) элемент, который вы хотите удалить. Вот пример, где я хочу удалить 5 из списка, содержащего числа 1-10...
std::list<int> myList;
int size = myList.size(); // The size needs to be saved to iterate through the whole thing
for (int i = 0; i < size; ++i)
{
int val = myList.back()
myList.pop_back() // dequeue
if (val != 5)
{
myList.push_front(val) // enqueue if not 5
}
}
myList теперь будут иметь только номера 1-4 и 6-10.
Ты можешь написать
std::list<item*>::iterator i = items.begin();
while (i != items.end())
{
bool isActive = (*i)->update();
if (!isActive) {
i = items.erase(i);
} else {
other_code_involving(*i);
i++;
}
}
Вы можете написать эквивалентный код с std::list::remove_if, который является менее многословным и более явным
items.remove_if([] (item*i) {
bool isActive = (*i)->update();
if (!isActive)
return true;
other_code_involving(*i);
return false;
});
std::vector::erasestd::remove_if идиома должна использоваться, когда элементы - это вектор, а не список, чтобы сохранить целостность на уровне O(n) - или в случае, если вы пишете общий код, а элементы могут быть контейнером без эффективного способа удаления отдельных элементов (например, вектора)
items.erase(std::remove_if(begin(items), end(items), [] (item*i) {
bool isActive = (*i)->update();
if (!isActive)
return true;
other_code_involving(*i);
return false;
}));
Хочу поделиться своим методом. Этот метод также позволяет вставлять элемент в конец списка во время итерации.
#include <iostream>
#include <list>
int main(int argc, char **argv) {
std::list<int> d;
for (int i = 0; i < 12; ++i) {
d.push_back(i);
}
auto it = d.begin();
int nelem = d.size(); // number of current elements
for (int ielem = 0; ielem < nelem; ++ielem) {
auto &i = *it;
if (i % 2 == 0) {
it = d.erase(it);
} else {
if (i % 3 == 0) {
d.push_back(3*i);
}
++it;
}
}
for (auto i : d) {
std::cout << i << ", ";
}
std::cout << std::endl;
// result should be: 1, 3, 5, 7, 9, 11, 9, 27,
return 0;
}
Do while, он гибкий, быстрый и простой для чтения и записи.
auto textRegion = m_pdfTextRegions.begin();
while(textRegion != m_pdfTextRegions.end())
{
if ((*textRegion)->glyphs.empty())
{
m_pdfTextRegions.erase(textRegion);
textRegion = m_pdfTextRegions.begin();
}
else
textRegion++;
}
Я думаю, что у вас есть ошибка, я кодирую таким образом:
for (std::list<CAudioChannel *>::iterator itAudioChannel = audioChannels.begin();
itAudioChannel != audioChannels.end(); )
{
CAudioChannel *audioChannel = *itAudioChannel;
std::list<CAudioChannel *>::iterator itCurrentAudioChannel = itAudioChannel;
itAudioChannel++;
if (audioChannel->destroyMe)
{
audioChannels.erase(itCurrentAudioChannel);
delete audioChannel;
continue;
}
audioChannel->Mix(outBuffer, numSamples);
}