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.
| 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.
| 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)
| 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)
| 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().
| 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 :
| 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.
| 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.
| 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:
-----------------------------------------------------------------
See Also:
-----------------------------------------------------------------
- Complete Tutorial of C++ Template's
- Standard Template Library Tutorial
- Inter Process Communication Tutorial
- Advance Programming in C & C++
-----------------------------------------------------------------
No comments:
Post a Comment