Удаление элементов — необходимая задача для любого контейнера. Удаление элементов из списка — простая задача, так как у нас есть предопределенные функции pop_back и pop_front, но поскольку список представляет собой контейнер, соответствующий свойствам двусвязного списка, должен быть метод для удаления элементов во время итерации.
Вы не можете напрямую удалить элемент из списка во время итерации, потому что вы получаете ошибку времени выполнения, потому что итератор теперь указывает на NULL, и адрес следующего элемента списка теряется, и вы больше не можете получить доступ к списку.
Удаление элемента с помощью одного итератора
Итераторы — это компоненты STL, используемые для итерации по контейнеру. Таким образом, мы можем использовать итератор для перебора списка, и во время обхода мы можем удалить элементы, которые хотим удалить. С помощью этого метода можно удалить элементы по значению или индексу.
Синтаксис:
iterator = list_name.erase(iterator);
Это обновит итератор, чтобы он указывал на местоположение после итератора, который вы удалили из списка.
Не забудьте не делать это++ в цикле, потому что вы уже увеличиваете итератор на 1 после каждой итерации. Если вы это сделаете, то вы должны это сделать — в каждой итерации цикла для поддержания непрерывности.
- Временная сложность : O(N)
- Вспомогательное пространство : O(1)
Ниже приведена реализация описанного выше подхода.
С++
// C++ Program to implement Removing
// element from the list while iteration
#include <iostream>
#include <list>
using
namespace
std;
// Function to print elements From
// the list While iterating
void
print(list<
int
>& li)
{
auto
it = li.begin();
if
(it == li.end()) {
cout <<
"List is Empty"
<< endl;
}
for
(it; it != li.end(); it++) {
cout << *it <<
" "
;
}
cout << endl;
}
// Function to delete elements From
// the list While iterating
void
solve(list<
int
>& li)
{
list<
int
>::iterator it = li.begin();
// Before Deletion
cout <<
"Before Deletion: "
<< endl;
cout <<
"Size of List: "
<< li.size() << endl;
print(li);
// Deleting element from list while iterating
while
(it != li.end()) {
if
(*it % 3 == 0) {
it = li.erase(it);
continue
;
}
it++;
}
// After Deletion
cout <<
"\nAfter Deletion: "
<< endl;
cout <<
"Size of List: "
<< li.size() << endl;
print(li);
}
// Driver Code
int
main()
{
list<
int
> li = { 1, 2, 3, 5, 4, 6 };
solve(li);
return
0;
}
Вывод
Before Deletion: Size of List: 6 1 2 3 5 4 6 After Deletion: Size of List: 4 1 2 5 4
Итерация в цикле for
В циклах while и for такого изменения нет, меняется только способ увеличения, что может сбивать с толку.
Ниже приведена реализация темы выше
С++
// C++ Program for removing elements
// in a list using single iterator
// in for loop
#include <iostream>
#include <list>
using
namespace
std;
// Function to print elements From
// the list While iterating
void
print(list<
int
>& li)
{
auto
it = li.begin();
if
(it == li.end()) {
cout <<
"List is Empty"
<< endl;
}
for
(it; it != li.end(); it++) {
cout << *it <<
" "
;
}
cout << endl;
}
// Function to delete elements From
// the list While iterating
void
solve(list<
int
>& li)
{
list<
int
>::iterator it;
// Before Deletion
cout <<
"Before Deletion: "
<< endl;
cout <<
"Size of List: "
<< li.size() << endl;
print(li);
// Deleting element from list while iterating
// through it--
for
(
auto
it = li.begin(); it != li.end(); it++) {
if
(*it % 3 == 0) {
it = li.erase(it);
it--;
}
}
// After Deletion
cout <<
"\nAfter Deletion: "
<< endl;
cout <<
"Size of List: "
<< li.size() << endl;
print(li);
}
// Driver Code
int
main()
{
list<
int
> li = { 1, 2, 3, 5, 4, 6 };
solve(li);
return
0;
}
Вывод
Before Deletion: Size of List: 6 1 2 3 5 4 6 After Deletion: Size of List: 4 1 2 5 4
Удаление элемента с помощью двух итераторов
Использование 2 итераторов точно такое же, просто вместо того, чтобы работать с итератором, мы работаем с фиктивным итератором, так что при увеличении итератора он приходит в правильное положение.
Пример:
С++
// C++ Program to implement Removing of
// element while iterating using
// 2 iterators
#include <iostream>
#include <list>
using
namespace
std;
// Function to print elements From
// the list While iterating
void
print(list<
int
>& li)
{
auto
it = li.begin();
if
(it == li.end()) {
cout <<
"List is Empty"
<< endl;
}
for
(it; it != li.end(); it++) {
cout << *it <<
" "
;
}
cout << endl;
}
// Function to delete elements From
// the list While iterating
void
solve(list<
int
>& li)
{
list<
int
>::iterator it = li.begin();
// Before Deletion
cout <<
"Before Deletion: "
<< endl;
cout <<
"Size of List: "
<< li.size() << endl;
print(li);
// Deleting element from list while iterating
// through iterator
while
(it != li.end()) {
list<
int
>::iterator temp = it++;
if
(*temp % 3 == 0) {
temp = li.erase(temp);
}
}
// After Deletion
cout <<
"\nAfter Deletion: "
<< endl;
cout <<
"Size of List: "
<< li.size() << endl;
print(li);
}
// Driver Code
int
main()
{
list<
int
> li = { 1, 2, 3, 5, 4, 6 };
solve(li);
return
0;
}
Вывод
Before Deletion: Size of List: 6 1 2 3 5 4 6 After Deletion: Size of List: 4 1 2 5 4