Introduction to C++ List
Definition and Overview
C++ List is a built-in sequence container with STL(Standard Template Library) that allows non-contiguous memory allocation. It is part of the Standard Template Library (STL), defined in the header file <list>.
The list uses non-contiguous memory allocation, so traversal is slower than vector in C++.
The list allows insertion and deletion operation anywhere within a sequence in constant time.
A C++ list provides several valuable features, including constant time insertions and deletions, efficient random access, and dynamic memory management.
However, the list doesn’t provide fast random access and only supports sequential access in both directions.
C++ Lists can shrink or expand from both ends at run time. The storage requirement is fulfilled automatically by the internal allocator.
By default, the list is doubly linked. Since it is a doubly-linked list, the insertion and deletion are fast on the list.
Elements of the list can be scattered in different chunks of memory. The container stores the necessary information to allow sequential access to its data.
Zero-sized lists are also valid. In that case, list.begin() and list.end() points to the same location. But the behavior of calling front() or back() is undefined.
Advantages of Using C++ List
-
Dynamic Memory Management: The list class manages memory dynamically, automatically resizing its memory allocation as elements are added and removed, eliminating the need for manual memory management.
- Efficient Insertions and Deletions: The C++ list provides constant time insertions and deletions at both the front and back of the list, making it an ideal choice for situations where frequent insertions and deletions are required.
- Ordering of Elements: The list class stores elements in the order in which they are added, making it easy to maintain the order of elements even when frequent insertions and deletions occur.
- Random Access: The C++ list provides efficient random access to its elements through iterators, enabling it to traverse the list and access elements at specific positions easily.
- Reusability: The C++ list is part of the Standard Template Library (STL), allowing it to be used as a reusable component in multiple projects, reducing development time and effort.
-
Stable Sorting: C++ list provides a sort() method that can be used to sort the elements in the list, making it possible to easily maintain sorted lists, even when elements are added and removed.
Syntax
Basic syntax
The definition of the list from its header file is as follows.
template < class T, class Alloc = allocator<T> > class list;
Parameters
-
T − Type of the element contained.
Any other data type, including a user-defined type, may substitute T.
-
Alloc − Type of allocator object.
The allocator class template is used by default, which defines the simplest memory allocation model and is value-independent.
If we want to make a list of integers, we can use the following code.
list<int> integer_list;
Methods and Member Functions of C++ List
Member types in C++ List
Member functions can use the following member types as parameters or return types.
| Sr.No. | Member types | Definition |
|---|---|---|
| 1 | value_type | T (First parameter of the template) |
| 2 | allocator_type | Alloc (Second parameter of the template) |
| 3 | reference | value_type& |
| 4 | const_reference | const value_type& |
| 5 | pointer | value_type* |
| 6 | const_pointer | const value_type* |
| 7 | iterator | the random-access iterator to value_type |
| 8 | const_iterator | the random-access iterator to const value_type |
| 9 | reverse_iterator | std::reverse_iterator <iterator> |
| 10 | const_reverse_iterator | std::reverse_iterator <const_iterator> |
| 11 | size_type | size_t |
| 12 | difference_type | ptrdiff_t |
List Constructors
See the following constructors in the C++ list.
- (1) empty container constructor (default constructor)
- constructs an empty container with no elements.
- (2) fill constructor
- It constructs a container with n elements. Each element is a copy of val.
- (3) range constructor
- It constructs a container with as many elements as the range [first, last), with each element constructed from its corresponding element in that range in the same order.
- (4) copy constructor
- It constructs a container with a copy of each element in x, in the same order.
Destructor
The C++ destructor std::list::~list() destroys the list object by deallocating its memory.
You can define the c++ destructor using the following code.
~list();
push_back()
They are used for adding a new element at the end of a list. For example, suppose the list is L, and we want to insert an element at its end. It can be done like this.
L.push_back(element);
push_front()
They add a new element at the start of a list. For example, suppose the list is L, and we want to insert an element at its front. It can be done like this.
L.push_front(element);
pop_back()
They are used for removing an element from the end of the list. Reduces the size of the list by one. For example, suppose the list is L. It can be done like this.
L.pop_back();
pop_front()
They are used for removing an element from the start of the list. Reduces the size of the list by one. For example, suppose the list is L.
L.pop_front();
front()
It returns the first element from the list. So if we want to check the value of the first element of the list, it can be used.
L.front();
back()
It returns the last element from the list. So if we want to check the value of the last element of the list, it can be used.
L.back();
empty()
It returns one if the list is empty. Otherwise, it returns 0.
L.empty();
insert()
It is used to insert the elements at any position of the list. It takes three parameters to position, several elements, and a value to insert. By default, the number of elements is set to 1.
L.insert(iterator, num_of_elements, element);
erase()
It erases one element or a range of elements from the list. An integer position is passed to delete one element, which will be deleted. To delete a range, starting iterator and an ending iterator must be given.
L.erase(list_iterator); // to delete one element L.erase(start_iterator, last_iterator); // for range
assign()
It is used to assign new elements to the list by replacing current elements and resizing the list. Two parameters are the number of values to be assigned, and the second is the value to be assigned.
L.assign(number of times, value);
remove()
It takes a value as a parameter and removes all the elements having this value from the list.
L.remove(value);
reverse()
As the name says, it reverses the order of elements in the list.
L.reverse();
size()
It returns the number of elements present in the list.
L.size();
begin()
It returns the iterator to the first element in the list.
List <data_type>::iterator = L.begin();
end()
It returns the iterator pointing to the theoretical last element, which follows the last element.
L.end();
sort()
It is used to sort the elements of a list in increasing order.
L.sort();
clear()
It is used to remove all the elements of the list container. So the size of the list becomes 0.
L.clear();
Let’s see the following example code.
// list.cpp
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
void showTheContent(list<int> l)
{
list<int>::iterator it;
for(it=l.begin();it!=l.end();it++)
{
cout << *it << " ";
}
cout << "\n";
}
int main()
{
// Sample Code to show List and its functions
list<int> list1,list2;
int i;
// inserting at the back
for(i=0;i<10;i++)
list1.push_back(i+1);
//inserting at the front
for(i=0;i<10;i++)
list2.push_front(i+1);
cout << "Content of List 1: ";
showTheContent(list1);
cout << "Content of list 2: ";
showTheContent(list2);
// sorting the second list
list2.sort();
cout << "Sorted List2 : ";
showTheContent(list2);
//Removing five elements from front in list1.
int times = 5;
while(times--)
{
list1.pop_front();
}
cout << "Content of List 1: " ;
showTheContent(list1);
//Removing five elements from the back in list2.
times=5;
while(times--)
{
list2.pop_back();
}
cout << "Content of List 2: ";
showTheContent(list2);
//seek the first element of list 1
cout << list1.front() << " is now at the front in list 1\n";
// seek the last element in list 2
cout << list2.back() << " is now the last element in list 2\n";
//Inserting elements in list 1.
list1.insert(list1.begin(),5,10);
cout << "After Insertion list 1: ";
showTheContent(list1);
//remove() to remove all the elements with value 10.
list1.remove(10);
cout << "After Removal list 1: ";
showTheContent(list1);
// size() to know the number of elements
cout << "No. of elements in list 1: ";
cout << list1.size() << "\n";
//Reversing the content of list 2
list2.reverse();
cout << "Reversed list 2: ";
showTheContent(list2);
//erasing first element of list 2
list2.erase(list2.begin());
cout << "After erasing from list 2: ";
showTheContent(list2);
//Removing all elements from list 1.
list1.clear();
// Use of empty() function
if(list1.empty()) cout << "List 1 is now empty\n";
else cout << "Not Empty\n";
// use of assign function
list1.assign(5,2); // 2 2 2 2 2
cout << "List 1: ";
showTheContent(list1);
return 0;
}
See the following output.
Use Cases for C++ List
Ordering of elements
C++ list elements are stored in the order in which they are added.
This means that when elements are inserted or deleted from the list, the order of the remaining elements is maintained. This makes a list an ideal choice for situations where maintaining the order of elements is important, such as linked lists or undo/redo stacks.
Frequent Insertions and Deletions
C++ list class provides constant time insertions and deletions at both the front and back of the list, making it an ideal choice for frequent insertions and deletions. This is because the list class uses doubly linked nodes to store its elements, allowing constant time insertions and deletions at any position in the list.
Dynamic Memory Management
The C++ list class manages memory dynamically, automatically resizing its memory allocation as elements are added and removed. The list can grow or shrink as needed without manual memory management.
Conclusion
Summary of C++ List
The C++ list is a container class in the Standard Template Library (STL) that stores elements in a linked list data structure.
Importance of C++ List in Software Development
-
Flexibility: The ability to insert and remove elements at any position in the list provides a high degree of flexibility in the storage and manipulation of data.
- Efficient Data Structures: The linked list data structure used by the C++ list provides efficient memory management and constant time insertions and deletions, making it an ideal choice for situations where performance is a concern.
-
Improved Code Readability: The list class provides a simple and intuitive interface for storing and manipulating data, making code easier to read and understand, especially in complex algorithms and data structures.
That’s it for this tutorial.
