STL introduces containers, which are quite useful in many cases and also -- with the help of iterators -- you can implement functions defined in <Algorithm> header to operate on these containers. There are different types of containers including: Vectors, Deques and Lists. In this tutorial we are going to describe Lists.
Benefit of List over Vector/Deque
Since Lists use unrelated memory locations to store data, they allow you to efficiently insert/remove/move elements in different locations of the List, not only Beginning or End of it.
Drawback
You cannot directly access elements of a List by their index. So if you want to, let's say, access the 100th element of the List, you have to start iterating from either beginning or end, and then access it... So in this case, Vector and Deque work more efficient.
Initialization
Now the usage examples of a list. First of all, we have to initialize an instance of list. Which means we are calling its constructor. We can do this in different ways:
#include <iostream>
#include <list>
using namespace std;
int main() {
list<int> list1; //an empty list of integers
list<int> list2(3, 7); //a list containing 3 integers with value of 7
list<int> list3(list2); //a list which has all members list2 has
list<int> list4(list3.begin(), list3.end()); //a list containing elements of list3 from its beginning to its end
return 0;
}
Those are different ways of initializing a list. Now I want to write a little useful function which helps a lot, it prints out the contents of a container... so it's also general and can be used with vectors etc.
#include <iostream>
#include <list>
using namespace std;
template <typename Container>
void print(const Container& cntn) {
typename Container::const_iterator i = cntn.begin(); //when initializing an object of a member type of the template, you have to use typename like this
for(; i != cntn.end(); ++i) { //iterate through the container
cout<<*i<<endl; //print each element
}
}
int main() {
list<int> list1; //an empty list of integers
list<int> list2(3, 7); //a list containing 3 integers with value of 7
list<int> list3(list2); //a list which has all members list2 has
list<int> list4(list3.begin(), list3.end()); //a list containing elements of list3 from its beginning to its end
print(list4); //prints 7 three times
return 0;
}
Assign
The assign member function has a syntax like the constructor you saw. It's useful when you want to re-assign values to a list. Look at this example:
#include <iostream>
#include <list>
using namespace std;
template <typename Container>
void print(const Container& cntn) {
typename Container::const_iterator i = cntn.begin(); //when initializing an object of a member type of the template, you have to use typename like this
for(; i != cntn.end(); ++i) { //iterate through the container
cout<<*i<<endl; //print each element
}
}
int main() {
list<int> list1; //an empty list of integers
list1.assign(2, 13);
print(list1); //prints 13 two times
return 0;
}
There is also an operator= member function, it can assign a list to another one. Look at the following example:
#include <iostream>
#include <list>
using namespace std;
template <typename Container>
void print(const Container& cntn) {
typename Container::const_iterator i = cntn.begin(); //when initializing an object of a member type of the template, you have to use typename like this
for(; i != cntn.end(); ++i) { //iterate through the container
cout<<*i<<endl; //print each element
}
}
int main() {
list<int> list1(3, 1);
list<int> list2 = list1; //list2 will contain three 1s like list1
print(list2);
return 0;
}
Manipulating Elements At Both Ends
If you have worked with deque before, you have seen these functions. push_back adds an element to the end of the list while push_front adds an element to the beginning of a list:
#include <iostream>
#include <list>
using namespace std;
template <typename Container>
void print(const Container& cntn) {
typename Container::const_iterator i = cntn.begin(); //when initializing an object of a member type of the template, you have to use typename like this
for(; i != cntn.end(); ++i) { //iterate through the container
cout<<*i<<endl; //print each element
}
}
int main() {
list<int> list1(3, 1);
list1.push_back(5);
list1.push_back(2);
list1.push_front(40);
print(list1); //prints 40 1 1 1 5 2
return 0;
}
There are two more functions, pop_front which removes the first element, and pop_back which removes the last element:
#include <iostream>
#include <list>
using namespace std;
template <typename Container>
void print(const Container& cntn) {
typename Container::const_iterator i = cntn.begin(); //when initializing an object of a member type of the template, you have to use typename like this
for(; i != cntn.end(); ++i) { //iterate through the container
cout<<*i<<endl; //print each element
}
}
int main() {
list<int> list1(3, 1);
list1.push_back(5);
list1.push_back(2);
list1.push_front(40);
print(list1); //prints 40 1 1 1 5 2
list1.pop_back();
print(list1); //prints 40 1 1 1 5
list1.pop_front();
print(list1); //prints 1 1 1 5
return 0;
}
Insert and Erase
As we talked about it at the start of this tutorial, the main benefit of list over vector and deque is that you can efficiently insert elements in any place and erase from any place. Here efficient means that list can allocate memory in different locations, and this enables a list to use linking between elements of the list, so there is no moving of elements needed while inserting/erasing.
#include <iostream>
#include <list>
using namespace std;
template <typename Container>
void print(const Container& cntn) {
typename Container::const_iterator i = cntn.begin(); //when initializing an object of a member type of the template, you have to use typename like this
for(; i != cntn.end(); ++i) { //iterate through the container
cout<<*i<<endl; //print each element
}
}
int main() {
list<int> list1;
list1.push_back(3);
list1.push_back(4);
list1.push_back(5);
//contains: 3 4 5
print(list1);
list<int>::iterator it = list1.begin(); //it points to number 3
it++; //it points to number 4
list1.insert(it, 1); //insert in place where number 4 is
//contains: 3 1 4 5
print(list1);
list1.insert(it, 2); //it still points place of number 4
//contains: 3 1 2 4 5
print(list1);
it--; //now it points to number 2
list<int>::iterator it2 = it;
advance(it2, 2); //it2 points to number 5 now
list1.erase(it, it2); //erase 2 and 4
print(list1); //prints 3 1 5
return 0;
}
Note: in the erase function, the first iterator itself is deleted, but the second iterator itself doesn't get deleted as you can see in the above code.
Sort
List provides a sort member function which sorts the elements in the list from lower to higher. It works like the sort function defined in algorithm header: By default it uses operator< to compare the elements. For your own objects/classes you can define a compare function yourself, or just define an operator< for them.
#include <iostream>
#include <list>
using namespace std;
template <typename Container>
void print(const Container& cntn) {
typename Container::const_iterator i = cntn.begin(); //when initializing an object of a member type of the template, you have to use typename like this
for(; i != cntn.end(); ++i) { //iterate through the container
cout<<*i<<endl; //print each element
}
cout<<endl;
}
int main() {
list<int> list1;
list1.push_back(100);
list1.push_back(1);
list1.push_back(10);
list1.push_back(5);
list1.sort();
print(list1); //prints 1 5 10 100
return 0;
}
What if you want to sort vice-versa ? You can define a compare function yourself, like the following:
#include <iostream>
#include <list>
using namespace std;
template <typename Container>
void print(const Container& cntn) {
typename Container::const_iterator i = cntn.begin(); //when initializing an object of a member type of the template, you have to use typename like this
for(; i != cntn.end(); ++i) { //iterate through the container
cout<<*i<<endl; //print each element
}
cout<<endl;
}
bool compare(const int& left, const int& right) {
return left>right;
}
int main() {
list<int> list1;
list1.push_back(100);
list1.push_back(1);
list1.push_back(10);
list1.push_back(5);
list1.sort(compare);
print(list1); //prints 100 10 5 1
return 0;
}
Remove
This is different than erase function mentioned before. Erase function is used to remove elements using their position, whereas the Remove function is used to remove the elements using their value. Have a look at the following:
#include <iostream>
#include <list>
using namespace std;
template <typename Container>
void print(const Container& cntn) {
typename Container::const_iterator i = cntn.begin(); //when initializing an object of a member type of the template, you have to use typename like this
for(; i != cntn.end(); ++i) { //iterate through the container
cout<<*i<<endl; //print each element
}
cout<<endl;
}
int main() {
list<int> list1(4, 1);
list1.push_back(2);
list1.push_back(3);
list1.remove(1); //remove all elements which have a value of 1
print(list1); //prints 2 3
return 0;
}
There is also another version, remove_if, which removes elements when a certain condition is met. For example, look at the following code which removes all elements greater than 100:
#include <iostream>
#include <list>
using namespace std;
template <typename Container>
void print(const Container& cntn) {
typename Container::const_iterator i = cntn.begin(); //when initializing an object of a member type of the template, you have to use typename like this
for(; i != cntn.end(); ++i) { //iterate through the container
cout<<*i<<endl; //print each element
}
cout<<endl;
}
bool condition(const int& a) {
return a>100; //returns true if a is bigger than 100
}
int main() {
list<int> list1;
list1.push_back(10);
list1.push_back(100);
list1.push_back(1000);
list1.remove_if(condition);
print(list1); //prints 10 100
return 0;
}
This can be much useful in some situations
Size
Member function size returns the current number of elements in the list. Have a look:
#include <iostream>
#include <list>
using namespace std;
int main() {
list<int> list1(3, 4);
cout<<list1.size()<<endl; //prints 3
return 0;
}
Maximum Size
The member function max_size returns the maximum size the list can reach, meaning the list cannot contain more than that.
#include <iostream>
#include <list>
using namespace std;
int main() {
list<int> list1;
cout<<list1.max_size()<<endl;
return 0;
}
Mine prints 4611686018427387903
Now the article ends here
Most of the useful stuff were mentioned however there are a couple more things you may wish to learn about. For a complete reference on them, visit [ Here ].Hope it was helpful for you!
MultiQuote
| 