list
A
list
is implemented as a doubly-linked list and is thus designed for rapid insertion
and removal of elements in the middle of 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 end to beginning) rather than choosing elements randomly
from the middle. Even then the traversal is significantly slower than either a
vector
or
a
deque,
but if you aren’t doing a lot of traversals that won’t be your
bottleneck.
Another
thing to be aware of with a
list
is the memory overhead of each link, which 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 a
held iterator never moves when you add new things to a list as it was
demonstrated to do in
vector.
Here’s an example using the
Noisy
class:
//: C20:ListStability.cpp
// Things don't move around in lists
#include "Noisy.h"
#include <list>
#include <iostream>
#include <algorithm>
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 perform the pointer movement instead of copying. On the other hand, the
swap( )
function is a generic algorithm, and doesn’t know about
list
in particular and so it uses the copying approach for swapping two elements.
There are also generic algorithms for
sort( )
and
reverse( ),
but if you try to use these you’ll discover that the generic
reverse( )
performs lots of copying and destruction (so you should never use it with a
list)
and the generic
sort( )
simply doesn’t work because it requires random-access iterators that
list
doesn’t provide (a definite benefit, since this would certainly be an
expensive way to sort compared to
list’s
own
sort( )
).
The generic
sort( )
and
reverse( )
should only be used with arrays,
vectors
and
deques. If
you have large and complex objects you may 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 operations that are built-in to make the best use of the
structure of the
list.
You’ve already seen
reverse( )
and
sort( ),
and here are some of the others in use:
//: C20:ListSpecialFunctions.cpp
#include "Noisy.h"
#include <list>
#include <iostream>
#include <algorithm>
using namespace std;
ostream_iterator<Noisy> out(cout, " ");
void print(list<Noisy>& ln, char* comment = "") {
cout << "\n" << comment << ":\n";
copy(ln.begin(), ln.end(), out);
cout << endl;
}
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;The
print( )
function is used to display results. After filling four
lists
with
Noisy
objects, one list is spliced into another in three different 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).
There’s
also a
unique( )
member function that removes all duplicates, but only if the
list
has been sorted first:
//: C20:UniqueList.cpp
// Testing list's unique() function
#include <list>
#include <iostream>
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 it copies all the elements from that container into itself (a
similar constructor is available for all the containers). Here, the
“container” is just an array, and the “iterators” are
pointers into that array, but because of the design of the STL it works with
arrays just as easily as any other container.
If
you run this program, you’ll see that
unique( )
will only remove
adjacent
duplicate elements, and thus sorting is necessary before calling
unique( ). There
are four additional
list
member
functions that are not demonstrated here: a
remove_if( )
that takes a predicate which is used to decide 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 may note that if you want a sorted list with no
duplicates, a
set
can give you that, right?
It’s
interesting to compare the performance of the two containers:
//: C20:ListVsSet.cpp
// Comparing list and set performance
#include <iostream>
#include <list>
#include <set>
#include <algorithm>
#include <ctime>
#include <cstdlib>
using namespace std;
class Obj {
int a[20];
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;
}
};
template<class Container>
void print(Container& c) {
typename Container::iterator it;
for(it = c.begin(); it != c.end(); it++)
cout << *it << " ";
cout << endl;
}
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!
Swapping
all basic sequences
It
turns out that all basic sequences have a member function
swap( )
that’s designed to switch one sequence with another (however, this
swap( )
is only defined for sequences of the same type). The member
swap( )
makes use of its knowledge of the internal structure of the particular
container in order to be efficient:
//: C20:Swapping.cpp
// All basic sequence containers can be swapped
#include "Noisy.h"
#include <list>
#include <vector>
#include <deque>
#include <iostream>
#include <algorithm>
using namespace std;
ostream_iterator<Noisy> out(cout, " ");
template<class Cont>
void print(Cont& c, char* comment = "") {
cout << "\n" << comment << ": ";
copy(c.begin(), c.end(), out);
cout << endl;
}
template<class Cont>
void testSwap(char* cname) {
Cont c1, c2;
generate_n(back_inserter(c1), 10, NoisyGen());
generate_n(back_inserter(c2), 5, NoisyGen());
cout << "\n" << cname << ":" << endl;
print(c1, "c1"); print(c2, "c2");
cout << "\n Swapping the " << cname
<< ":" << endl;
c1.swap(c2);
print(c1, "c1"); print(c2, "c2");
}
int main() {
testSwap<vector<Noisy> >("vector");
testSwap<deque<Noisy> >("deque");
testSwap<list<Noisy> >("list");When
you run this, you’ll discover that each type of sequence container is
able to swap one sequence for another without any copying or assignments, even
if the sequences are of different sizes. In effect, you’re completely
swapping the memory of one object for another.
The
STL algorithms also contain a
swap( ),
and when this function is applied to two containers of the same type, it will
use the member
swap( )
to achieve fast performance. Consequently, if you apply the
sort( )
algorithm to a container of containers, you will find that the performance is
very fast – it turns out that fast sorting of a container of containers
was a design goal of the STL.
Robustness
of lists
To
break a
list,
you have to work pretty hard:
//: C20:ListRobustness.cpp
// lists are harder to break
#include <list>
#include <iostream>
using namespace std;
int main() {
list<int> li(100, 0);
list<int>::iterator i = li.begin();
for(int j = 0; j < li.size() / 2; j++)
i++;
// Walk the iterator forward as you perform
// a lot of insertions in the middle:
for(int k = 0; k < 1000; k++)
li.insert(i++, 1); // No problem
li.erase(i);
i++;
*i = 2; // Oops! It's invalidWhen
the link that the iterator
i
was pointing to was erased, it was unlinked from the list and thus became
invalid. Trying to move forward to the “next link” from an invalid
link is poorly-formed code. Notice that the operation that broke
deque
in
DequeCoreDump.cpp
is perfectly fine with a
list.
Contact: webmaster@codeguru.com
CodeGuru - the website for developers.