Re: Lists and back() Question.

From: Martijn Lievaart (m_at_remove.this.part.rtij.nl)
Date: 12/17/03 

Date: Wed, 17 Dec 2003 15:21:46 +0100

On Tue, 16 Dec 2003 16:36:29 -0800, Larry Lindstrom wrote:

>>> Is there a method to point an iterator at the
>>>last element without traversing the list?
>>
>>
>> test_iterator = test_list.end();
>> --test_iterator;
>
> Thanks Martijn:
>
> Since STL lists are probably implemented as double
> linked lists, I assumed end() would return NULL. So
> decrementing it's return value would be meaningless.
> How do they do that? Is there an open source STL I
> somewhere I can look at?

Iterators are abstractions of pointers (but are /not/ pointers!). They
come in different flavors (input, output, forward, bidirectional,
random access, and I think some more).

For standard containers, iterators are always input, output and
bidirectional. That means that you can treat them all in exactly the same
way. You can increment them, decrement them, retrieve the value from the
container and store a new value in the container. It does not matter if
the iterator points to a list, a vector, or whatever.

For every container, you can get an iterator for the first element with
begin(), and one for the element one beyond the end with end() (that is
why I decremented the iterator, one beyond the end minus one is the last
element). The 'one beyond the end' is used througout the STL and the end
of a range is always designated with the element following the last.

So to sort a vector, you can simply say:

std::sort(vec.begin(), vec.end());

To sort the first 10 elements (assuming the vector has that many elements,
otherwise you're off into booboo land):

std::sort(vec.begin(), vec.begin()+10);

(Note you cannot use std::sort for a list as std::sort requires random
access iterators which a list does not have. You can use std::list::sort()
though)

There are some subtle differences between iterators for different
containers, which have to do with when an iterator becomes invalid.

Iterators can become invalid when the container changes. Look at this as
if iterators where pointers (which they are not, but the analogy is good).
If you have a pointer into an array, and then reallocate or delete the
array, the pointer is invalid. It does not point into the array anymore.
You cannot use it anymore. Iterators are just like that, but knowing when
they become invalid is an art in itself at first.

For instance, inserting into a vector invalidates all iterators that point
into the vector (technical reason, insertion may mean reallocation, so the
underlying memory addresses may change). Deletion from vector also has
some rules (all iterators after the deleted element become invalid iirc).

A list on the other hand, never invalidates its iterators. The price you
pay for this: lists take more memory, have a worse locality of reference
(don't worry if you don't understand that), offer no random access and are
often slower than vectors. That is not to say they are useless, they offer
different tradeofs.

Other containers offer different tradeofs. A dequeue invalidates it
iterators less often, allows efficient insertion on the front /and/ the
back and allows random access. The price is slightly more memory
consumption.

Sets, multisets, maps and multimaps are different again. Look up your
documentation for more information about them, they serve different
purposes than vectors, lists and dequeues. They also have rules about
iterators though.

I suggest you get a good tutorial on the STL. That should give much more
insight than I can give in one post. Search this group (through Google)
for recommendations, the subject comes up fairly often.

When you have read the tutorial, get "Effective STL", by Scott Meyers. It
may be a bit over your head at first, but is a very good book on how to
use the STL effectively and safely so you'll certainly get value out of it
and will keep rereading it when you progress.

A good open source STL is STLport. It has the added advantage that it
offers a debug mode that catches all kinds of errors with iterators (but
obviously is much slower in debug mode). Another good open STL is made by
SGI.

Also have a look at www.boost.org. They offer a lot of libraries, many
which extend the STL and many other goodies. Most importantly for
beginners is boost::shared_ptr, a very good smart pointer, but there are
many treasures there. I'm personally particularly pleased with their
regular expression library.

HTH,
M4

Relevant Pages

  • Re: do you see the bug?
    ... refer to the deque instance, so after the first call to insert, current is ... consult SGI's STL web site. ... > I'm new to STL and iterators and I saw this in some book trying to teach ... > are invalidated and use an invalid iterator. ...
    (microsoft.public.vc.stl)
  • abstract containers: does such a thing exist, conceptually?
    ... code implementing that pattern? ... behaviour by the additional pointers. ... trigger adding- or removing-operations of other iterators... ... 2)graph = list of lists: The same as above but with its own allocator ...
    (comp.object)
  • Re: question about True values
    ... Not all empty objects have zero length, or even a length at all. ... example, iterators. ... lists, but the "if a:" doesn't work for them, so it's moot. ...
    (comp.lang.python)
  • Re: Effective STL Item 4 (size() vs. empty())
    ... >> Any other practical obstacle you have been encountering? ... The Osize leads to an Osplice ... source and destination lists are the same, ... to be able to keep iterators to specific items. ...
    (comp.lang.cpp)
  • Re: stl-list in 2 dimensions
    ... > is the usual way to cope with this portability-problem? ... you are trying to pretend that STL lists ... The STL is very elegant, you seem to be interested in some very inelegant ...
    (comp.lang.cpp)