Thinking in C++ Vol 2 - Practical Programming |
Prev |
Home |
Next |
A list is implemented as a doubly linked list data
structure and is thus designed for rapid insertion and removal of elements anywhere
in the sequence, whereas for vector and deque this is a much more
costly operation. A list is so slow when randomly accessing elements that it
does not have an operator[ ]. It s best used when you re traversing
a sequence, in order, from beginning to end (or vice-versa), rather than
choosing elements randomly from the middle. Even then the traversal can be
slower than with a vector, but if you aren t doing a lot of traversals,
that won t be your bottleneck.
The memory overhead of each link in a list requires a
forward and backward pointer on top of the storage for the actual object. Thus,
a list is a better choice when you have larger objects that you ll be
inserting and removing from the middle of the list.
It s better not to use a list if you think you might
be traversing it a lot, looking for objects, since the amount of time it takes
to get from the beginning of the list which is the only place you can
start unless you ve already got an iterator to somewhere you know is closer to
your destination to the object of interest is proportional to the number of
objects between the beginning and that object.
The objects in a list never move after they are
created. Moving a list element means changing the links, but never copying or
assigning the actual objects. This means that iterators aren t invalidated when
items are added to the list as it was demonstrated earlier to be the case vector.
Here s an example using a list of Noisy objects:
//: C07:ListStability.cpp {-bor}
// Things don't move around in lists.
//{L} Noisy
#include <algorithm>
#include <iostream>
#include <iterator>
#include <list>
#include "Noisy.h"
using namespace std;
int main() {
list<Noisy> l;
ostream_iterator<Noisy> out(cout, "
");
generate_n(back_inserter(l), 25, NoisyGen());
cout << "\n Printing the list:"
<< endl;
copy(l.begin(), l.end(), out);
cout << "\n Reversing the list:"
<< endl;
l.reverse();
copy(l.begin(), l.end(), out);
cout << "\n Sorting the list:"
<< endl;
l.sort();
copy(l.begin(), l.end(), out);
cout << "\n Swapping two elements:"
<< endl;
list<Noisy>::iterator it1, it2;
it1 = it2 = l.begin();
++it2;
swap(*it1, *it2);
cout << endl;
copy(l.begin(), l.end(), out);
cout << "\n Using generic reverse():
" << endl;
reverse(l.begin(), l.end());
cout << endl;
copy(l.begin(), l.end(), out);
cout << "\n Cleanup" << endl;
} ///:~
Operations as seemingly radical as reversing and sorting the
list require no copying of objects because, instead of moving the objects, the
links are simply changed. However, notice that sort( ) and reverse( ) are member functions of list, so they have special knowledge of the
internals of list and can rearrange the elements instead of copying
them. On the other hand, the swap( ) function is a generic
algorithm and doesn t know about list in particular, so it uses the
copying approach for swapping two elements. In general, use the member version
of an algorithm if that is supplied instead of its generic algorithm
equivalent. In particular, use the generic sort( ) and reverse( )
algorithms only with arrays, vectors, and deques.
If you have large, complex objects, you might want to choose
a list first, especially if construction, destruction,
copy-construction, and assignment are expensive and if you are doing things
like sorting the objects or otherwise reordering them a lot.
Special list operations
The list has some special built-in operations to make
the best use of the structure of the list. You ve already seen reverse( )
and sort( ). Here are some of the others:
//: C07:ListSpecialFunctions.cpp
//{L} Noisy
#include <algorithm>
#include <iostream>
#include <iterator>
#include <list>
#include "Noisy.h"
#include "PrintContainer.h"
using namespace std;
int main() {
typedef list<Noisy> LN;
LN l1, l2, l3, l4;
generate_n(back_inserter(l1), 6, NoisyGen());
generate_n(back_inserter(l2), 6, NoisyGen());
generate_n(back_inserter(l3), 6, NoisyGen());
generate_n(back_inserter(l4), 6, NoisyGen());
print(l1, "l1", " "); print(l2,
"l2", " ");
print(l3, "l3", " "); print(l4,
"l4", " ");
LN::iterator it1 = l1.begin();
++it1; ++it1; ++it1;
l1.splice(it1, l2);
print(l1, "l1 after splice(it1, l2)",
" ");
print(l2, "l2 after splice(it1, l2)",
" ");
LN::iterator it2 = l3.begin();
++it2; ++it2; ++it2;
l1.splice(it1, l3, it2);
print(l1, "l1 after splice(it1, l3, it2)",
" ");
LN::iterator it3 = l4.begin(), it4 = l4.end();
++it3; --it4;
l1.splice(it1, l4, it3, it4);
print(l1, "l1 after
splice(it1,l4,it3,it4)", " ");
Noisy n;
LN l5(3, n);
generate_n(back_inserter(l5), 4, NoisyGen());
l5.push_back(n);
print(l5, "l5 before remove()", "
");
l5.remove(l5.front());
print(l5, "l5 after remove()", "
");
l1.sort(); l5.sort();
l5.merge(l1);
print(l5, "l5 after
l5.merge(l1)", " ");
cout << "\n Cleanup" << endl;
} ///:~
After filling four lists with Noisy objects,
one list is spliced into another in three ways. In the first, the entire list l2
is spliced into l1 at the iterator it1. Notice that after the
splice, l2 is empty splicing means removing the elements from the source
list. The second splice inserts elements from l3 starting at it2
into l1 starting at it1. The third splice starts at it1
and uses elements from l4 starting at it3 and ending at it4.
The seemingly redundant mention of the source list is because the elements must
be erased from the source list as part of the transfer to the destination list.
The output from the code that demonstrates remove( ) shows that the list does not have to be sorted in order for all the elements
of a particular value to be removed.
Finally, if you merge( ) one list with another,
the merge only works sensibly if the lists have been sorted. What you end up
with in that case is a sorted list containing all the elements from both lists
(the source list is erased that is, the elements are moved to the
destination list).
A unique( ) member function removes all duplicates, but only if you sort the list first:
//: C07:UniqueList.cpp
// Testing list's unique() function.
#include <iostream>
#include <iterator>
#include <list>
using namespace std;
int a[] = { 1, 3, 1, 4, 1, 5, 1, 6, 1 };
const int ASZ = sizeof a / sizeof *a;
int main() {
// For output:
ostream_iterator<int> out(cout, " ");
list<int> li(a, a + ASZ);
li.unique();
// Oops! No duplicates removed:
copy(li.begin(), li.end(), out);
cout << endl;
// Must sort it first:
li.sort();
copy(li.begin(), li.end(), out);
cout << endl;
// Now unique() will have an effect:
li.unique();
copy(li.begin(), li.end(), out);
cout << endl;
} ///:~
The list constructor used here takes the starting and
past-the-end iterator from another container and copies all the elements from
that container into itself. Here, the container is just an array, and the
iterators are pointers into that array, but because of the design of the STL,
the list constructor works with arrays just as easily as with any other
container.
The unique( ) function will remove only adjacent
duplicate elements, and thus sorting is typically necessary before calling unique( ).
The exception is when the problem you re trying to solve includes eliminating
adjacent duplicates according to the current ordering.
Four additional list member functions are not
demonstrated here: a remove_if( ) that takes a predicate, which
decides whether an object should be removed; a unique( ) that takes
a binary predicate to perform uniqueness comparisons; a merge( )
that takes an additional argument which performs comparisons; and a sort( )
that takes a comparator (to provide a comparison or override the existing one).
list vs. set
Looking at the previous example, you might note that if you
want a sorted sequence with no duplicates, you could get that result with a set.
It s interesting to compare the performance of the two containers:
//: C07:ListVsSet.cpp
// Comparing list and set performance.
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <iterator>
#include <list>
#include <set>
#include "PrintContainer.h"
using namespace std;
class Obj {
int a[20]; // To take up extra space
int val;
public:
Obj() : val(rand() % 500) {}
friend bool
operator<(const Obj& a, const Obj& b) {
return a.val < b.val;
}
friend bool
operator==(const Obj& a, const Obj& b) {
return a.val == b.val;
}
friend ostream&
operator<<(ostream& os, const Obj& a) {
return os << a.val;
}
};
struct ObjGen {
Obj operator()() { return Obj(); }
};
int main() {
const int SZ = 5000;
srand(time(0));
list<Obj> lo;
clock_t ticks = clock();
generate_n(back_inserter(lo), SZ, ObjGen());
lo.sort();
lo.unique();
cout << "list:" << clock() -
ticks << endl;
set<Obj> so;
ticks = clock();
generate_n(inserter(so, so.begin()),
SZ, ObjGen());
cout << "set:" << clock() -
ticks << endl;
print(lo);
print(so);
} ///:~
When you run the program, you should discover that set
is much faster than list. This is reassuring after all, it is set s
primary job description to hold only unique elements in sorted order!
This example uses the header PrintContainer.h, which
contains a function template that prints any sequence container to an output
stream. PrintContainer.h is defined as follows:
//:
C07:PrintContainer.h
// Prints a
sequence container
#ifndef
PRINT_CONTAINER_H
#define
PRINT_CONTAINER_H
#include
"../C06/PrintSequence.h"
template<class
Cont>
void
print(Cont& c, const char* nm = "",
const char* sep = "\n",
std::ostream&
os = std::cout) {
print(c.begin(), c.end(), nm, sep, os);
}
#endif ///:~
The print( ) template defined here just calls
the print( ) function template we defined in the previous chapter
in PrintSequence.h.
Thinking in C++ Vol 2 - Practical Programming |
Prev |
Home |
Next |