Удалить элементы из списка во время итерации С++

Возврат массива из функции C++ Программирование и разработка

Удаление элементов — необходимая задача для любого контейнера. Удаление элементов из списка — простая задача, так как у нас есть предопределенные функции 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

Читайте также:  Аутентификация с помощью ключа API в Java
Оцените статью
bestprogrammer.ru
Добавить комментарий