Orchid XP v8 <voi### [at] devnull> wrote:
> What would be the correct way to iterate over a vector of integers and 
> find + remove the lowest element?

  Do you want the imperative solution, or the template metaprogramming
solution? ;)

  There are two ways of iterating a vector: By indexing it and by using
iterators. The latter method can also be used for any other STL container
as well. The indexing method might be a bit clearer:

size_t smallestIndex = 0;
for(size_t ind = 1; ind < theVector.size(); ++ind)
    if(theVector[ind] < theVector[smallestInd])
        smallestIndex = ind;

  When the loop ends, smallestIndex will be an index to the (first)
smallest value inside the vector. Now the only trick is how to remove it:

theVector.erase(theVector.begin() + smallestIndex);

  (The erase() function requires an iterator. It doesn't work directly with
index values. The begin() function returns an iterator to the first element
in the vector. The reason why you can get an iterator to the nth element
with an addition like that is that std::vector iterators are random access
iterators and they support jumping to any location in the vector by adding
an index value to them.)

  Note that erase() is an O(n) operation.

  You can also implement the same thing using iterators. The advantage is
that the exact same code will work with any STL data container, not just
vectors. For example, if you wanted to use an std::list instead, the
iterator solution would work with that too.

  To simplify the syntax it's usually a good idea to typedef the data
container type:

typedef std::vector<int> Cont; // Could also be eg. an std::list<int> etc.

  Then you can perform the operation like this:

Cont::iterator smallestIter = theVector.begin();
for(Cont::iterator iter = theVector.begin(); iter != theVector.end(); ++iter)
    if(*iter < *smallestIter)
        smallestIter = iter;

theVector.erase(smallestIter);

  Iterators work a bit like pointers. The prefix-* operator dereferences
the iterator, ie. returns the value it's pointing to. The ++ operator
changes the iterator to point to the next element in the container.
The iterator returned by the end() function is a special iterator which
points "past the end" (ie. to an imaginary element which is after the
last element in the data container). When the iterator gets to the end()
iterator, it means that the data container has no more values.

  If the type stored in the data container was a class with member
functions, you could call such a member function with iter->function();
(in the same way as with pointers).

  Iterators are used a lot in STL containers and algorithms because they
are a good way of abstracting away the actual container: An algorithm
usually doesn't need to even know what type of container it's dealing
with, nor does it need the container itself. It's enough for it to deal
with the iterators.

  Also iterators are a handy way of specifying sub-ranges of values inside
the container. There are also special iterators, for example reverse
iterators which work like regular ones, but act like the entire container
had been reversed. (Also more exotic iterators exist, such as stream
iterators, insert iterators, etc.)

-- 
                                                          - Warp

Post a reply to this message