LIST

LIST

The list class implements a bi-directional, sequential container . It is most often implemented as doubly-linked list and may be traversed in either direction. list provides linear-time access. Inserting and deleting elements in a list takes place in constant time. It does not matter where in the list insertion or deletion will occur. Without random access, some generic algorithms cannot be used. Hence, these operations are provided instead as member functions of the list class. The linked representation also permits some additional operations, such as splice for splicing two lists, reverse for reversing lists, unique for eliminating duplicate elements, and merge for merging two lists.

Lists should be used in preference to other sequence containers when frequent insertions and deletions are required in the middle of sequences and there is little need to jump around randomly from one position to another. Vectors are sequence containers of choice when the fastest possible random access is needed, and few if any insertions or deletions are required at any point other than the end. If insertions or deletions are needed at the beginning and the end of the sequence, the better choice is a deque.

To use list class include <list>.

The template specification for list:

template <class T, class Allocator=allocator <T> > class list

where T is the type of data being stored and Allocator specifies the allocator which defaults to the standard allocator. For most cases you will simply use the default allocator.

list has following constructors:

explicit list (const Allocator &a=Allocator() );	Constructs an empty list.
explicit list (size_type num, const T &val=T(), const Allocator &a=Allocator() );	Constructs a list that has num elements with value val
list (const list <T, Allocator> &ob);	list's copy constructor.
template <class InIter> list (InIter start, InIter end, const Allocator &a=Allocator() );	Constructs a list that contains the elements in the range specified by start and end.

The list class supports bi-directional iterator. Thus, the container can be accessed through an iterator in both forward and reverse direction. To obtain an iterator for list:

list <T>::iterator i;

Random access operations are not supported. Thus the [ ] operator is not overloaded.

The list class overloads the assignment operator =. It also defines comparison operators:

==, <, <=, !=, >, >=

Some of the most commonly used member functions:

Member	Description
iterator begin ();	Returns an iterator to the first element in the list.
iterator end ();	Returns an iterator to the end of the list.
reference back ();	Returns a reference to the last element in the list
bool empty ();	Returns true if the list contains no elements.
iterator erase (iterator i)	Removes the element pointed to by i. Returns an iterator to the element after the one removed.
iterator erase (iterator start, iterator end);	Removes the elements in range start to end. Returns an iterator to the element after the one removed.
reference front ();	Returns a reference to the first element in the list
iterator insert (iterator i, const T &val);	Inserts val immediately before the element specified by i. An iterator to the element is returned.
void insert (iterator i, size_type num, const T &val);	Inserts num copies of val immediately before the element specified by i.
template <class InIter> void insert (iterator i, InIter start, InIter end);	Inserts the sequence defined by start and end immediately before the element specified by i.
void pop_back ();	Removes the last element in the list.
void pop_front ();	Removes the first element in the list
void push_back (const T &val);	Adds an element with the value specified by val to the end of the list.
void push_front (const T &val);	Adds an element with the value specified by val to the front of the list.
void remove (const T &val)	Removes elements with the value val from the list
size_type size () const;	Returns the number of elements currently in the list.

Special members of list:

void merge (list<T, Allocator>&ob);	Merges the ordered list contained in ob with the ordered invoking list. The result is ordered. After the merge , the list contained in ob is empty.
void sort ();	Sorts the list.
void splice (iterator i, list <T, Allocator> &ob);	The contents of ob are inserted into the invoking list at the location pointed by i. After the splice, ob is empty.
void splice (iterator i, list <T, Allocator> &ob, iterator start, iterator end);	The range defined by start and end is removed from ob and stred in the invoking list beginning at the location pointed to by i.
void unique ();	Removes consecutive duplicate elements from the invoking list.

Example:

#include <list>
#include <string>
#include <assert.h>
#include <iostream>
using namespace std;

template<class T>             // template function print
void print(list<T> l) {
    list<T>::iterator it = l.begin();
    while(it != l.end())
        cout<<*it++<<"\t";
    cout<<endl;
}

main() {
    list<int> li;
    list<string> ls;

    for(int i = 0; i < 20; i++)
        li.push_back(i);
    assert(!li.empty());
    print(li);

    cout<<"Removing first 5 elements...\n";
    for(i = 0; i < 5; i++) {
        cout<<li.front()<<" removed\n";
        li.pop_front();
    }
    cout<<endl;
    print(li);

    cout<<"Removing last 5 elements...\n";
    for(i = 0; i < 5; i++){
        cout<<li.back()<<" removed\n";
        li.pop_back();
    }
    print(li);

    cout<<"Removing 7 and 12 from the list...\n";
    li.remove(7);
    li.remove(12);
    print(li);

    li.clear();
    assert(li.empty());
    cout<<endl<<endl;

    assert(ls.empty());
    ls.push_back("John");
    ls.push_front("Tom");
    ls.push_back("Anna");
    ls.push_front("John");
    assert(!ls.empty());
    print(ls);

    cout<<"\nSorting elements...\n";
    ls.sort();
    print(ls);

    cout<<"\nRemoving duplicate elements...\n";
    ls.unique();
    print(ls);

    return 0;
}