 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v8 <voi### [at] dev null> 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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> Californians have a reputation for being... uh... "unusual". Which would
> certainly explain... for example... your nick is "slime"? o_O And also
> some of the wacky things you've rendered over the years.
Hah, well, in my defense I've only lived here 3 years. "Slime" comes from
the Dragon Warrior games.
- Slime
[ http://www.slimeland.com/ ]
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> Anyways, these are technical details you don't have to worry about.
On the other hand, my computer science 2 class focused almost entirely on
the STL data structures and how to implement them yourself. It was a good
way to learn the intricacies of making a class that has to deal with
cleaning itself up, thus needing copy constructors and assignment operators
and destructors. Understanding how this all works gets you closer to
understanding how your code is compiled and the sort of things that are
allowed (such as how a vector of vectors works internally).
Another way to learn that sort of thing is to do it the C way first, where
you have a struct with some pointers in it, and you write your own functions
to initialize the data, copy the data, and destroy the data. Then you learn
why those functions are necessary and what happens if you try to avoid using
them. Finally you see why C++'s approach is so nice, even though it's so
hard to learn. The POV-Ray source was helpful when I was learning this, but
I don't know how well it's split between C and C++ anymore.
However, all of this should wait until you're comfortable with pointers.
- Slime
[ http://www.slimeland.com/ ]
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v8 wrote:
> Is there a "set" type laying around somewhere? The thing I'm processing
> *is* notionally a set, not an ordered collection.
Yes: std::set.
> 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...
Yes, each container has its own iterator. For a vector, it could even be a
plain old pointer instead of a class. And you don't even have to worry
about that :)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> Is there a "set" type laying around somewhere? The thing I'm processing
> *is* notionally a set, not an ordered collection.
std::set, I believe. Internally it uses a binary tree so it can quickly
search for things. This means that whatever type you use it on has to work
with the < operator; it uses < to know how to order the tree. (This is
relevant because it means you have to define the < operator if you want to
use it with your own class.)
You can google "std set" for documentation. This works for most or all STL
types. The useful member function here is find( value ), which returns an
iterator to the element with the given value, or returns yourset.end()
otherwise. (Oh, insert() is useful too.)
- Slime
[ http://www.slimeland.com/ ]
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Slime wrote:
>> Is there a "set" type laying around somewhere? The thing I'm processing
>> *is* notionally a set, not an ordered collection.
>
> std::set, I believe. Internally it uses a binary tree so it can quickly
> search for things. This means that whatever type you use it on has to work
> with the < operator; it uses < to know how to order the tree. (This is
> relevant because it means you have to define the < operator if you want to
> use it with your own class.)
Heh. Exactly like Haskell's Data.Set ;-)
Question: What happens if your class doesn't have the comparison operator?
> You can google "std set" for documentation. This works for most or all STL
> types. The useful member function here is find( value ), which returns an
> iterator to the element with the given value, or returns yourset.end()
> otherwise. (Oh, insert() is useful too.)
I'm more likely to be iterating the whole set and removing elements from
it, but yeah. ;-)
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On Sun, 28 Sep 2008 10:41:43 +0200, Orchid XP v8 <voi### [at] devnull> wrote:
>
> Heh. Exactly like Haskell's Data.Set ;-)
>
> Question: What happens if your class doesn't have the comparison
> operator?
You create a set with some other predicate as comparator.
I wonder: Do you not have access to documentation that explains this?
--
FE
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v8 <voi### [at] devnull> wrote:
> > Note that erase() is an O(n) operation.
> Yeah, that's kind of unavoidable.
If the vector doesn't need to preserve the order of the elements then
you can remove the element in O(1) like this:
theVector[smallestInd] = theVector.back();
theVector.pop_back();
In other words, copy the last element over the element to be removed,
and then remove the last element.
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v8 <voi### [at] devnull> wrote:
> Question: What happens if your class doesn't have the comparison operator?
If there's no way you can add an operator<() for your class, then you
can give std::set a comparator. A comparator is a functor used to compare
two elements of the same type (it takes two parameters of the type in
question, and returns a boolean telling if the first parameter is less
than the second parameter). This happens, for example, like this:
struct MyComparator
{
// Note that this member function must be of 'const' type:
bool operator()(const MyClass& lhs, const MyClass& rhs) const
{
return /* is lhs less than rhs? */;
}
};
int main()
{
// Make a type alias, to simplify the usage:
typedef std::set<MyClass, MyComparator> TheSetType;
TheSetType theSet;
...
}
If your comparator has some state which may be different between sets,
you can give an initialized instance of your comparator to the set:
TheSetType theSet(MyComparator(initialization, values));
It is also possible to create a comparison function and use as a functor
(as you might remember). However, the syntax of the TheSetType definition
becomes a bit complicated.
By the way, std::set (as well as std::map) *always* takes a comparator
(rather than using the < operator directly). When none is specified, the
default comparator used is std::less which, by template magic, makes it
completely equivalent to comparing the elements with the < operator
directly.
This is good to know because you might sometimes want the elements
sorted in some other way. For example, if you want to sort them in
decreasing order, you can use the std::greater comparator (provided
by the standard C++ library). For example:
typedef std::set<int, std::greater<int> > TheSetType;
All integers added to this set will be in decreasing order rather than
in increasing one.
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
|
|
