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:

image from book

 list<short> list1; list<double> list2; list<Date> list3; 

image from book

The STL list like the other containers has several constructors as described in the following table that show their prototypes:

image from book

Open table as spreadsheet

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.

image from book

Using these constructors we could have definitions like the following:

image from book

 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. 

image from book

Some of the list member functions are the following:

image from book

Open table as spreadsheet

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.

image from book

In addition to the above member functions, lists support the following operators:

image from book

Operator

==( )

<( )

=( )

image from book

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:

image from book

 slist<double>::iterator iterator1; 

image from book

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:

image from book

Operator

==( )

!=( )

=( )

*( )

++( )

--( )

image from book

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:

image from book

Open table as spreadsheet

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.

image from book




Intermediate Business Programming with C++
Intermediate Business Programming with C++
ISBN: 738453099
EAN: N/A
Year: 2007
Pages: 142

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net