|
 |
Warp wrote:
> Do you want the imperative solution, or the template metaprogramming
> solution? ;)
Hmm... should I even get into this at 10:30 PM on a Saturday night? ;-)
> 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.)
Right, I see. So erase() is the function for removing stuff. (VC++
kindly tells me all the available members functions, but not what the *do*.)
I presume the reason for iterators is that some collections might be
"unordered", and without iterators there would therefore be no way to
iterate all elements? (And, similarly, that's why erase() wants an
iterator.)
> Note that erase() is an O(n) operation.
Yeah, that's kind of unavoidable.
> 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.
Is there a "set" type laying around somewhere? The thing I'm processing
*is* notionally a set, not an ordered collection.
> 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);
So... does that mean the iterator is a nested class then? (Just trying
to understand the syntax.) Clearly each container type would end up
needing a completely different iterator implementation...
> 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).
OK.
> 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.)
Sounds good... ;-)
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
