Lists in STL
The notes have already introduced you to the STL and some introduction to the STL list. Recall in the previous discussion that the library <list> needs to be included in a program that uses the STL list. Further since this is a template recall that to define an instance of this template class you would need definitions like the following:
 |
list<short> list1; list<double> list2; list<Date> list3;
|
The STL list like the other containers has several constructors as described in the following table that show their prototypes:
|
| Constructor | Purpose |
|---|---|
| list( ); | Creates an empty list object of the specified data type. |
| list(long n); | Creates a list object of the specified data type with capacity for n elements. |
| list(long n, datatype val); | Creates a list object of the specified data type with n copies of the data element val of type datatype‥ |
| list(datatype* firstptr, datatype* lastptr) | Creates a list object of the specified data type that contains copies of elements in the memory locations from iterator: firstptr up to iterator: lastptr. |
Open table as spreadsheet |
Using these constructors we could have definitions like the following:
|
list<short> l1; // creates an empty short list l1 list<double> l2(20); // creates a double list l2 with // a capacity for 20 doubles. list<long> l3(5, 3443); // creates a long list l3 with 5 // copies of 3443. list<char> l4(ptr, ptr+4); // creates a char list l4 // whose elements are // the chars beginning at the address // contained in the iterator ptr // and going to // the address contained in the // iterator ptr + 4.
|
Some of the list member functions are the following:
|
| Function | Purpose |
|---|---|
| begin( ) | returns an iterator to the beginning of the list for iterating forward through the list. |
| end( ) | returns an iterator to past-the-end location of the list used to move from the end toward the beginning. |
| rbegin( ) | returns a reverse iterator to the end of the container for iterating backward through the list. |
| rend( ) | returns a reverse iterator to the beginning of the list used to end backward iteration. |
| empty( ) | returns true if no elements and false otherwise |
| size( ) | returns the number of elements in the list. |
| front( ) | returns the element at the front of the list. |
| back( ) | returns the element at the back of the list.. |
| L1.merge(L2) | moves all of the elements of L2 into L1 leaving L2 empty. |
| push_front(datetype s1) | adds an element s1 to the list at the front. |
| push_back(datatype s2) | adds an element s2 to the list at the back |
| pop_back( ) | removes an element from the back of the list. |
| pop_front( ) | removes an element from the front of the list. |
| erase(pos) | erases the element at position pos in the list. |
| erase(pos1, pos2) | erases the elements between position pos1 and pos2. |
| reverse( ) | reverses the order of the elements of the list. |
| sort( ) | sorts the elements of the list using the operator <. |
| insert(pos, datatype value) | inserts value into a list at position pos. |
| insert(pos, n, value) | inserts n copies of the value into a list beginning at position pos |
| insert(pos, iter1, iter2) | inserts the elements between iter1 and iter2 into the list beginning at position pos. |
| unique( ) | replaces all multiple occurrences with one element of that value. |
|
In addition to the above member functions, lists support the following operators:
|
| Operator |
|---|
| ==( ) |
| <( ) |
| =( ) |
|
In a later section of this lecture, the three different types of iterators will be discussed: random access, bi-directional and forward. Lists have bi-directional iterators. Therefore if an iterator is defined like the following:
|
slist<double>::iterator iterator1;
|
Then iterator1 would be a bi-directional iterator on a double list and could be used to move in both directions in the list. Notice that the [ ] operator is not defined on lists. As a result, not all algorithms are defined on lists. For example lists have their own sort( ) because of the limitations on the list iterators.
The list iterators have the following operators:
|
| Operator |
|---|
| ==( ) |
| !=( ) |
| =( ) |
| *( ) |
| ++( ) |
| --( ) |
|
Examples of lists:
-
See list_a.cpp for an example that demonstrates the use of a list that uses the default constructor and adds elements to both the front and back followed by removal from the front.
-
See list_b.cpp for an example that demonstrates a list that is defined by the constructor that uses two pointers as arguments to input the data between these pointers into the list and then shows how some of the member functions work. This program uses merge() from the <list> methods rather than the merge() from <algorithm>. This time there was no warning about this merge() in .NET 2005.
-
See list_c.cpp for an example that demonstrates a list that is defined by the constructor that uses two pointers as arguments to input the data between these pointers into the list and then shows how an iterator may be used to access and change the values of the elements.
-
See list_d.cpp for an example that demonstrates a list that is defined by the constructor that specifies the number elements and then uses an iterator to point into the list to show and to change the elements followed by using the algorithm find( ) to find a specific element.
The following table is a reminder of the containers we have studied, some of their properties and some of their advantages and disadvantages:
|
| Container | Characteristics | Advantages and Disadvantages |
|---|---|---|
| array | Fixed size | Quick random access (by index number). |
| vector | Relocating, likean expandable array | Quick random access (by index number). Slow to insert or erase in the middle. Quick to insert or erase at ends. |
| list | Doubly linked list | Only sequential access and no random access. Quick to insert or delete at any location. Quick access to both ends. Slow random access. High overhead. |
| deque | Like vector, but can be accessed at either end. | Quick random access (using index number). Slow to insert or erase in the middle. Quick to insert or erase (push and pop) at either the beginning or the end. |
|
EAN: N/A
Pages: 142