Different ways to delete elements in list in C++

Harshit Raj -

Do not miss this exclusive book on Binary Tree Problems. Get it now for free.

In this article, we will explore Different ways to delete elements in list in C++ such as pop_front(), pop_back(), clear(), removeif() and much more.

List can be simply defined as a sequential container. The data elements in the list are connected into a logical linear list through the linked list pointer, that is, the list also has the main advantages of the linked list. This makes the insertion and deletion of elements at any position in the list faster.

Table of Contents:

  1. Introduction
  2. How to delete elements in a list?
  3. Using Member Functions of lists
  4. Deletion of elements By Using pop_front(), pop_back() and clear()
  5. Deletion of elements By Using erase()
  6. Deletion of elements By Using unique()
  7. Deletion of elements By Using remove()
  8. Deletion of elements By Using removeif()
  9. Remove elements from a list while iterating in C++
  10. Conclusion

Introduction

What is a List?
C++ List is a built-in sequence container of STL(Standard Template Library), which allows non-contiguous memory allocation.

A list does not provide fast random access, it only supports sequential access in both directions.

C++ lists can be shrunk or expanded from both ends at runtime. Storage requirements are done automatically by an internal allocator.

By default, lists are doubly linked. Since it's a double-linked list, insertions and deletions on the list are fast.

Note:
Lists allow constant-time insertion and deletion anywhere in a sequence.
The elements of the list can be scattered in different memory blocks. A list stores the necessary information to allow sequential access to its data.

How to delete elements in a list?

Idea :
To delete the elements stored in the list container, you need to use the member functions provided by the container template class. Fortunately, compared to other STL container template classes, the list template class provides more member functions to achieve this operation
List supports bidirectional and provides an efficient method for insertion and deletion operations.

Using Member Functions of lists

Here is a list of member functions used for the deletion of elements in the list container:-

member functionFunction
pop_front()Deletes an element at the head of the list container.
pop_back()Removes an element at the end of the list container.
remove_if()Remove elements in the container that satisfy the condition.
unique()Delete adjacent duplicate elements in the container, keeping only one copy.
remove(val)Removes all elements equal to val in the container.
clear()Delete all elements stored in the list container.
erase()This member function can delete the element at the specified position in the list container, or delete multiple elements in a certain area in the container.

Deletion of elements By Using pop_front(), pop_back() and clear()

Among them, the usage of pop_front(), pop_back() and clear() is very simple.
The following implemented code describes the use of all the above member functions:

Implementation of Code

#include <iostream>
#include <list>
using namespace std;

int main()
{
   list<int>values{ 1,2,3,4 };
  
   //Delete the first element in the current container
   values.pop_front();
   // list : {2,3,4}
  
   //Delete the last element of the current container
   values.pop_back();
   // list : {2,3}
  
   //Empty the container and delete all elements in the container
   values.clear(); 
   // list : {}
  
   for (auto begin = values.begin(); begin != values.end(); ++begin)
   {
       cout << *begin << " ";
   }
   return 0;
}

Output : Its an empty list

Time complexity : O(1)

Deletion of elements By Using erase()

The erase() member function has the following 2 syntax formats:

Syntax 1 : iterator erase (iterator position);
Syntax 2: iterator erase (iterator first, iterator last);

Idea : erase() is used to delete all the elements in the range limited by the first iterator and last iterator in the list container (including the element pointed to by first, but not including the element pointed to by last)

Implementation:

#include <iostream>
#include <list>
using namespace std;
int main()
{
    list<int>values{ 1,2,3,4,5 };
    auto first = values.begin();
    ++ first ; // point to element 2
    auto last = values.end();
    -- last ; // point to element 5
    // delete 2, 3 and 4
    values.erase(first, last);
    for (auto begin = values.begin(); begin != values.end(); ++begin)
    {
        cout << *begin << " ";
    }
    return 0;
}

Output :

1 5

Time Complexity : O(n) where (n is size of list).

Deletion of elements By Using unique()

The unique() function also has the following 2 syntax formats:

void unique()
void unique(BinaryPredicate)//pass in a binary predicate function

The above two formats can remove adjacent repeated elements in the list container, and only keep one copy. But the advantage of the second format is that we can customize the de-duplication rules.

Implementation

#include <iostream>
#include <list>
using namespace std;
// binary predicate function
bool rule(double first, double second)
{
    return (int(first) == int(second));
}
int main()
{
    list<double> mylist{ 1,1.2,1.2,3,4,4.5,4.6 };
    //Delete adjacent duplicate elements, keep only one copy
    mylist . unique (); 
    for (auto it = mylist.begin(); it != mylist.end(); ++it)
        cout << *it << ' ';
    cout << endl;
    mylist . unique (rule);
    for (auto it = mylist.begin(); it != mylist.end(); ++it)
        std::cout << *it << ' ';
    return 0;
}

Output:

1 1.2 3 4 4.5 4.6
1 3 4

Deletion of elements By Using remove()

The member function remove() of the list container removes the elements matching the parameter.

Implementation:

#include <iostream>
#include <list>
using namespace std;

int main()
{
    std::list<int> numbers { 2, 5, 2, 3, 6, 7, 8, 2, 9};
    numbers.remove(2); 
    return 0;
}

Output : List is now 5 3 6 7 8 9

Time Complexity : O(n) where (n is size of list).

Deletion of elements By Using removeif()

This function deletes the occurrences of the values that returns “true” to the condition passed in the function.

Implementation

#include <iostream>
#include <list>
using namespace std;
int main()
{
    std::list<int> mylist{ 15, 36, 7, 17, 20, 39, 4, 1 };
    //Delete all elements in the mylist container that can make the lamba expression true.
    mylist.remove_if([](int value) {return (value < 11); }); 
    for (auto it = mylist.begin(); it != mylist.end(); ++it)
        std::cout << ' ' << *it;
    return 0;
}

Output:

15 36 17 20 39

Time Complexity : O(n)

Remove elements from a list while iterating in C++

Idea:
The idea is to use the basic iterative concept and iterate over the list and call to the list::erase to remove the required element.

Implementation:

#include <iostream>
#include <list>
#include <iterator>
using namespace std;

int main()
{
	list<string> input = { "naruto", "asta", "Kirito", "Deku", "Tanjiro" };

	for (auto itr = input.cbegin(); itr != input.end(); itr++)
	{
		if (itr->length() == 4) {
			input.erase(itr--);
		}
	}

	copy(input.begin(), input.end(), ostream_iterator<string>(cout, "\n"));

	return 0;
}

Output :

naruto
Kirito
Tanjiro

Understanding the code:
Here we have used the postfix decrement operator to decrement the iterator. In the above program we have tried to removed all elements of list with string length = 4.
Then we printed the new list with the removed elements.

Time complexity : O(n) where (n is size of list).

Conclusion

In this article at OpenGenus, we learned the basic concepts of lists. Studied various member functions like pop_front(), pop_back() and clear(), erase() and remove(). And also techniques like using iteration and the member functions together for use in various applications.

Sign up for FREE 3 months of Amazon Music. YOU MUST NOT MISS.