Saturday, January 25, 2014

list c++

list c++ : Standard Template Library Tutorial, ccplusplus.com
A list manages its elements as a doubly linked list. As usual, the C++ standard library does not specify the kind of the implementation, but it follows from the list's name, constraints, and specifications.

Figure:- Structure of a List

To use a list you must include the header file <list>:


There, the type is defined as a template class inside namespace std:


The elements of a list may have any type T that is assignable and copyable. The optional second template parameter defines the memory model. The default memory model is the model allocator, which is provided by the C++ standard library.

Abilities of Lists

The internal structure of a list is totally different from a vector or a deque. Thus, a list differs in several major ways compared with vectors and deques:
  • A list does not provide random access. For example, to access the fifth element, you must navigate the first four elements following the chain of links. Thus, accessing an arbitrary element using a list is slow.
  • Inserting and removing elements is fast at each position, and not only at one or both ends. You can always insert and delete an element in constant time because no other elements have to be moved. Internally, only some pointer values are manipulated.
  • Inserting and deleting elements does not invalidate pointers, references, and iterators to other elements.
  • A list supports exception handling in such a way that almost every operation succeeds or is a no-op. Thus, you can't get into an intermediate state in which only half of the operation is complete.
The member functions provided for lists reflect these differences compared with vectors and deques as follows:
  • Lists provide neither a subscript operator nor at() because no random access is provided.
  • Lists don't provide operations for capacity or reallocation because neither is needed. Each element has its own memory that stays valid until the element is deleted.
  • Lists provide many special member functions for moving elements. These member functions are faster versions of general algorithms that have the same names. They are faster because they only redirect pointers rather than copy and move the values.

List Operations


Create, Copy, and Destroy Operations


The ability to create, copy, and destroy lists is the same as it is for every sequence container. See table below for the list operations that do this. 


Table:- Constructors and Destructor of Lists
Operation Effect
list<Elem> c Creates an empty list without any elements
list<Elem> c1(c2) Creates a copy of another list of the same type (all elements are copied)
list<Elem> c(n) Creates a list with n elements that are created by the default constructor
list<Elem> c(n,elem) Creates a list initialized with n copies of element elem
list<Elem> c (beg,end) Creates a list initialized with the elements of the range [beg,end)
c.~list<Elem>() Destroys all elements and frees the memory

Nonmodifying Operations


Lists provide the usual operations for size and comparisons.

Table:- Nonmodifying Operations of Lists

Operation Effect
c.size() Returns the actual number of elements
c. empty () Returns whether the container is empty (equivalent to size()==0, but might be faster)
c.max_size() Returns the maximum number of elements possible
c1 == c2 Returns whether c1 is equal to c2
c1 != c2 Returns whether c1 is not equal to c2 (equivalent to ! (c1==c2))
c1 < c2 Returns whether c1 is less than c2
c1 > c2 Returns whether c1 is greater than c2 (equivalent to c2<c1)
c1 <= c2 Returns whether c1 is less than or equal to c2 (equivalent to ! (c2<c1) )
c1 >= c2 Returns whether c1 is greater than or equal to c2 (equivalent to ! (c1<c2))

Assignments


Lists also provide the usual assignment operations for sequence containers (table below)

Table:- Assignment Operations of Lists

Operation Effect
c1 = c2 Assigns all elements of c2 to c1
c.assign(n,elem) Assigns n copies of element elem
c.assign(beg,end) Assigns the elements of the range [beg,end)
c1.swap(c2) Swaps the data of c1 and c2
swap(c1,c2) Same (as global function)

As usual, the insert operations match the constructors to provide different sources for initialization.

Element Access


Because a list does not have random access, it provides only front() and back() for accessing elements directly (table below)
Table:- Direct Element Access of Lists
Operation Effect
c.front() Returns the first element (no check whether a first element exists)
c.back() Returns the last element (no check whether a last element exists)

As usual, these operations do not check whether the container is empty. If the container is empty, calling them results in undefined behavior. Thus, the caller must ensure that the container contains at least one element. For example:


Iterator Functions


To access all elements of a list, you must use iterators. Lists provide the usual iterator functions (table below).  However, because a list has no random access, these iterators are only bidirectional. Thus, you can't call algorithms that require random access iterators. All algorithms that manipulate the order of elements a lot (especially sorting algorithms) fall under this category. However, for sorting the elements, lists provide the special member function sort().

Table:- Iterator Operations of Lists
Operation Effect
c.begin() Returns a bidirectional iterator for the first element
c.end() Returns a bidirectional iterator for the position after the last element
c.rbegin() Returns a reverse iterator for the first element of a reverse iteration
c.rend() Returns a reverse iterator for the position after the last element of a reverse iteration

Inserting and Removing Elements


Table below shows the operations provided for lists to insert and to remove elements. Lists provide all functions of deques, supplemented by special implementations of the remove() and remove_if() algorithms.

As usual by using the STL, you must ensure that the arguments are valid. Iterators must refer to valid positions, the beginning of a range must have a position that is not behind the end, and you must not try to remove an element from an empty container.

Inserting and removing happens faster if, when working with multiple elements, you use a single call for all elements rather than multiple calls.

For removing elements, lists provide special implementations of the remove() algorithms. These member functions are faster than the remove() algorithms because they manipulate only internal pointers rather than the elements. So, in contrast to vectors or deques, you should call remove() as a member function and not as an algorithm. To remove all elements that have a certain value, you can do the following :


Table:- Insert and Remove Operations of Lists
Operation Effect
c.insert (pos, elem) Inserts at iterator position pos a copy of elem and returns the position of the new element
c.insert (pos,n, elem) Inserts at iterator position pos n copies of elem (returns nothing)
c. insert (pos, beg,end) Inserts at iterator position pos a copy of all elements of the range [beg,end) (returns nothing)
c.push_back(elem) Appends a copy of elem at the end
c.pop_back() Removes the last element (does not return it)
c.push_front(elem) Inserts a copy of elem at the beginning
c.pop_front () Removes the first element (does not return it)
c. remove (val) Removes all elements with value val
c.remove_if (op) Removes all elements for which op(elem) yields true
c. erase (pos) Removes the element at iterator position pos and returns the position of the next element
c.erase (beg,end) Removes all elements of the range [beg,end) and returns the position of the next element
c. resize (num) Changes the number of elements to num (if size() grows, new elements are created by their default constructor)
c.resize (num, elem) Changes the number of elements to num (if size ( ) grows, new elements are copies of elem)
c. clear () Removes all elements (makes the container empty)

You can use remove_if() to define the criterion for the removal of the elements by a function or a function object. remove_if() removes each element for which calling the passed operation yields true. An example of the use of remove_if() is a statement to remove all elements that have an even value:


remove() and remove_if().

Splice Functions


Linked lists have the advantage that you can remove and insert elements at any position in constant time. If you move elements from one container to another, this advantage doubles in that you only need to redirect some internal pointers (figure below).
Figure:- Splice Operations to Change the Order of List Elements

To support this ability, lists provide not only remove() but also additional modifying member functions to change the order of and relink elements and ranges. You can call these operations to move elements inside a single list or between two lists, provided the lists have the same type. Table below lists these functions. 

Table:- Special Modifying Operations for Lists
Operation Effect
c.unique() Removes duplicates of consecutive elements with the same value
c.unique(op) Removes duplicates of consecutive elements, for which op() yields true
c1.splice(pos,c2) Moves all elements of c2 to c1 in front of the iterator position pos
c1.splice(pos,c2,c2pos) Moves the element at c2pos in c2 in front of pos of list c1 (c1 and c2 may be identical)
c1.splice(pos,c2,c2beg,c2end) Moves all elements of the range [c2beg,c2end) in c2 in front of pos of list c1 (c1 and c2 may be identical)
c.sort() Sorts all elements with operator <
c.sort(op) Sorts all elements with op()
c1.merge(c2) Assuming both containers contain the elements sorted, moves all elements of c2 into c1 so that all elements are merged and still sorted
c1.merge(c2,op) Assuming both containers contain the elements sorted due to the sorting criterion op(), moves all elements of c2 into c1 so that all elements are merged and still sorted according to op()
c.reverse() Reverses the order of all elements

Exception Handling


Lists have the best support of exception safety of the standard containers in the STL. Almost all list operations will either succeed or have no effect. The only operations that don't give this guarantee in face of exceptions are assignment operations and the member function sort() (they give the usual "basic guarantee" that they will not leak resources or violate container invariants in the face of exceptions), merge(), remove(), remove_if(), and unique() give guarantees under the condition that comparing the elements (using operator == or the predicate) doesn't throw. Thus, to use a term from database programming, you could say that lists are transaction safe, provided you don't call assignment operations or sort() and ensure that comparing elements doesn't throw. Table below lists all operations that give special guarantees in face of exceptions. 

Table:- List Operations with Special Guarantees in Face of Exceptions
Operation Guarantee
push_back() Either succeeds or has no effect
push_front() Either succeeds or has no effect
insert () Either succeeds or has no effect
pop_back() Doesn't throw
pop_front() Doesn't throw
erase() Doesn't throw
clear() Doesn't throw
resize() Either succeeds or has no effect
remove() Doesn't throw if comparing the elements doesn't throw
remove_if() Doesn't throw if the predicate doesn't throw
Unique() Doesn't throw if comparing the elements doesn't throw
splice() Doesn't throw
Merge() Either succeeds or has no effect if comparing the elements doesn't throw
reverse() Doesn't throw
swap() Doesn't throw

Examples of Using Lists


The following example in particular shows the use of the special member functions for lists:


The program has the following output:












-----------------------------------------------------------------
See Also:
-----------------------------------------------------------------

-----------------------------------------------------------------

No comments:

Post a Comment