Page 1 of 1

STL List Rate Topic: ***** 1 Votes

#1 Anarion  Icon User is offline

  • The Persian Coder
  • member icon

Reputation: 305
  • View blog
  • Posts: 1,507
  • Joined: 16-May 09

Posted 12 February 2010 - 11:53 AM

Preface: An understanding of the language - Functions - STL & Iterators


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 :w00t:


Now the article ends here :D 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!

Is This A Good Question/Topic? 4
  • +

Page 1 of 1