Sign in to follow this  

two questions in one regarding STL and std:: containers.

This topic is 3593 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, I've got two noob questions about c++:
std::map<std::string,GUI_widget *>::iterator it;
for(it = children.begin(); it!= children.end(); ++it)
{
	std::cout<<name<<" passing event to child widget"<<children[(*it).first]->name<<std::endl;
	children[(*it).first]->handle_event(E);
}




I'm not sure why all this is done this way. What advantage is there to this cryptic syntax? What can I do with this that is more powerful than using a foreach (if it existed)? Also, If I want to pick a random element out of the list, I don't really know how, since I'm not sure how to convert the "std::map<std::string,GUI_widget *>::iterator" into an integer to use with rand(). I've read the relevant sections on sgi's reference, but that doesn't help, and I'm not having any success with search engines. Thanks for any advice.

Share this post


Link to post
Share on other sites
1) That is essentially the same as a foreach loop. I don't personally use STL very much (I don't program at home as much anymore, and I don't use it at work since I need to keep executable sizes down), so I won't comment on the syntax of the iterator class.

2) If you want random access into a container, use a vector. Since vectors allow random access. A crude way would be to get a random integer between 0 and the number of elements and just iterate through the container and return the element at the random index. I'd just use a vector though (or wait for someone who uses STL to comment).

Share this post


Link to post
Share on other sites
Er... are you aware that the following code does the same thing (more efficiently)?

std::map<std::string,GUI_widget *>::iterator it;
for(it = children.begin(); it!= children.end(); ++it)
{
std::cout<<name<<" passing event to child widget"<<it->second->name<<std::endl;
it->second->handle_event(E);
}

Share this post


Link to post
Share on other sites
Hm, that example is pretty confusing. If I'm reading it right, it really should just be:

// This typedef would probably go in the header file...
typedef std::map<std::string,GUI_widget *> widgets_t;

// ...

for(widgets::iterator it = children.begin(); it!= children.end(); ++it)
{
std::cout << name << " passing event to child widget" <<
it->second->name << std::endl;
it->second->handle_event(E);
}


Also, there is a for_each() function in the standard library (although getting it to do what you want can occasionally require jumping through some hoops).

As for picking a random element, a map is not a random-access container, so you can't just index into it using a random value. You should however be able to achieve essentially the same thing by using std::advance().

Share this post


Link to post
Share on other sites
Quote:
Original post by jyk
Hm, that example is pretty confusing. If I'm reading it right, it really should just be:

*** Source Snippet Removed ***
Also, there is a for_each() function in the standard library (although getting it to do what you want can occasionally require jumping through some hoops).

As for picking a random element, a map is not a random-access container, so you can't just index into it using a random value. You should however be able to achieve essentially the same thing by using std::advance().


Thanks for your answers,

I tried defining a new type instead of using the std::container<types>::extra::conceptual::overhead::iterator syntax repeatedly, but got a linker error.

Is there an indexed container that allows random access?

why it->second rather than it->first? (Is that why my code has a bizarre error where I can dump all child widgets in a list but not pass stuff down the heirarchy?

The point of this (very crude: only buttons and windows) OpenGL GUI project is to learn about STL containers. I've got it drawing nicely, so not everything was a waste of time.

I'll look deeper into a c++ for_each. I would really like to just say for_each(children, GUI_widget * child){} or something similar.


Share this post


Link to post
Share on other sites
That iterator syntax is more or less standard. Like a lot of things in C++, it's very verbose but that can't be avoided. One thing you can do is jyk suggested and use a typedef to reduce the length of the map type. If you do that, you can declare the iterator inside the for statement and it looks less bulky and is easier to read.

As for your loop being inefficient, it's doing unnecessary lookups. A map is implemented as a binary tree and the iterator as (I'm guessing) a depth-first traversal. Looking up a specific element in a binary tree takes time, but the iterator has already traversed to that element so there's no need to look it up again. You can just call it->second->handle_event(E).

And picking a random element is easy. You know the size of the map from with size method, and you can get an iterator on the first element with the begin method. After that, there's an advance function you can use, or you can use a for loop and increment the iterator.


// This is needed to use advance
#include <iterator>

// This is to save some typing
using namespace std;

map<string,GUI_widget*>::iterator i = children.begin();
advance(i, rand() % children.size());
cout << "Here's a random child widget: " << i->second->name << endl;

Share this post


Link to post
Share on other sites
Quote:
Original post by jonahrowley
That iterator syntax is more or less standard. Like a lot of things in C++, it's very verbose but that can't be avoided. One thing you can do is jyk suggested and use a typedef to reduce the length of the map type. If you do that, you can declare the iterator inside the for statement and it looks less bulky and is easier to read.

As for your loop being inefficient, it's doing unnecessary lookups. A map is implemented as a binary tree and the iterator as (I'm guessing) a depth-first traversal. Looking up a specific element in a binary tree takes time, but the iterator has already traversed to that element so there's no need to look it up again. You can just call it->second->handle_event(E).

And picking a random element is easy. You know the size of the map from with size method, and you can get an iterator on the first element with the begin method. After that, there's an advance function you can use, or you can use a for loop and increment the iterator.

*** Source Snippet Removed ***


Kule, this thread gives me some stuff to think about, plus a bug fix. Thanks, GDNet.

[edit]
er... I was under the impression that you can contaminate a namespace if you say using namespace? In what circumstances can this happen?

Share this post


Link to post
Share on other sites
Quote:
Original post by speciesUnknown
I tried defining a new type instead of using the std::container<types>::extra::conceptual::overhead::iterator syntax repeatedly, but got a linker error.

You probably don't want to do that. The containers in the standard library are adequate. C++ is verbose, you just have to live with it.

Quote:

Is there an indexed container that allows random access?

Define "indexed". Maps have random access like this: some_map["some key"].

Quote:

why it->second rather than it->first? (Is that why my code has a bizarre error where I can dump all child widgets in a list but not pass stuff down the heirarchy?

When you iterate over a map, you iterate over the map's pair element. If you have a map<string,int>, then the iterator points to a pair<string,int>. The pair has 2 methods of interest, first and second. The first method will return the string, the second method will return the int.

Quote:

I'll look deeper into a c++ for_each. I would really like to just say for_each(children, GUI_widget * child){} or something similar.


Sadly, you can't do that yet. The next version of C++ (called C++0x) will have lambdas (also called closures or anonymous functions). Then you'll be able to do that. Right now, you have to do something like this.


void print_pair(const pair<string,int>& p) {
cout << p.first() << ", " << p.second() << endl;
}

...
for_each( some_map.begin(), some_map.end(), print_pair );



As you can see, the actual code to be run by the for_each algorithm is disjointed from the for_each call itself. This is why people use the for loop with an iterator instead of a for_each call. This will be better in C++0x, you'll be able to do something like this.


for_each( some_map.begin(), some_map.end(), <>(const pair<string,int>& p) -> void {
cout << p.first() << ", " << p.second() << endl;
});

Share this post


Link to post
Share on other sites
Quote:
Original post by speciesUnknown
er... I was under the impression that you can contaminate a namespace if you say using namespace? In what circumstances can this happen?


That depends on your code. For small programs, there's no reason not to do it. For large programs, there are few reasons not to do it. You "contaminate" the global namespace with all the symbols from the std namespace, but that's usually not a problem. Of course, if you're using your own namespaces, importing everything from std into them is probably not a good idea.

Share this post


Link to post
Share on other sites
Quote:
Original post by speciesUnknown
I tried defining a new type instead of using the std::container<types>::extra::conceptual::overhead::iterator syntax repeatedly



typedef std::map<std::string,GUI_widget *>::iterator GUI_iterator;


Usage:

for (GUI_iterator it = children.begin(); it!= children.end(); ++it)
{
//...
}


Edit: Or, better yet

typedef std::map<std::string,GUI_widget *> GUI_map;
typedef GUI_map::iterator GUI_iterator;

GUI_map children;

for (GUI_iterator it = children.begin(); it!= children.end(); ++it)
{
//...
}

Share this post


Link to post
Share on other sites
Quote:
Original post by jonahrowley
Quote:
Original post by speciesUnknown
er... I was under the impression that you can contaminate a namespace if you say using namespace? In what circumstances can this happen?


That depends on your code. For small programs, there's no reason not to do it. For large programs, there are few reasons not to do it. You "contaminate" the global namespace with all the symbols from the std namespace, but that's usually not a problem. Of course, if you're using your own namespaces, importing everything from std into them is probably not a good idea.


My program is huge, its the game I've been working on for a couple of years, one technical challenge at a time. (OpenGL, SDL, and ODE are the libraries I'm using, as well as standard libraries.)

So far, nothing has had such verbosity as STL.

[edit]
oh, by indexed I mean you can pick an element by its index, e.g.:
std::map<std::string,float> properties;

properties["temperature']=37.5;
properties["size"]=14;

std::cout<<"Size of elephant = "<<properties["size"]<< feet, temperature of elephant = "<<properties["temperature"]<<std::endl;

rather than just viewing certain elements. I'm using this as the properties of an event in my game. (e.g. the mouse move event has the properties "XREL" and "YREL")

Share this post


Link to post
Share on other sites
Well, thanks to this thread I've finally fixed my STL implementation of widgets. Buttons and windows are the only widgets, as now I'm at the stage of adding more event handling to the system. (Currently, only moving the mouse generates events).

I have the base class GUI_widget, which is inherited by GUI_surface (a passive widget designed as an invisible root for the GUI tree) a GUI_window, and a GUI_button.

Here is a screenshot of the system rendered with the OPenGL renderer (which inherits the GUI_renderer base class :-) )

window with some buttons

Just need to add text (I've already got a class for bitmap fonts.)


Thanks alot.

Share this post


Link to post
Share on other sites
Quote:
Original post by speciesUnknown
I'll look deeper into a c++ for_each. I would really like to just say for_each(children, GUI_widget * child){} or something similar.


The closest to that at the moment is an ugly hack, which fortunately is well done and cleanly interfaced to look like nothing of the sort.

See Boost.Foreach

That said, you'd still be iterating over the likes of (std::pair<std::string,GUI_Widget *>) instead of just GUI_Widget.

Share this post


Link to post
Share on other sites
Quote:
Original post by jonahrowley
The next version of C++ (called C++0x) will have lambdas (also called closures or anonymous functions). Then you'll be able to do that.

...

you'll be able to do something like this.

*** Source Snippet Removed ***

Or more simply use a range-based for loop - essentially a for-each loop. Alternatively there's the auto keyword to reduce the verbosity, in this case still preferable to lambda functions IMO.

Share this post


Link to post
Share on other sites
Quote:
Original post by speciesUnknown
What advantage is there to this cryptic syntax?


Here's the English translation:


'it' is an iterator for a (std::map from std::string to pointer-to-GUI_widget).
Starting 'it' at the begin() of 'children', and until it reaches the end() of 'children', incrementing it each time:
output name, " passing event to child widget", the 'name' of the GUI_widget pointed to by (the element of 'children' indexed by the 'first' member of the thing pointed at by 'it'), end of line.
Tell the element of 'children' indexed by the 'first' member of the thing pointed at by 'it' to handle_event 'E'.



It's not really that cryptic, but it certainly is more verbose than is required, and involves a couple of words you might not be familiar with.

An iterator is a thing which iterates. The English verb "to iterate" (they didn't just make this name up!) means something like "to repeat; to do repeatedly". (Note that the more common word "reiterate" is usually redundant, meaning "iterate again".) What C++ iterators really do is to act like pointers, but (using some internal magic) let you treat a container as if it were an array.

Arrays are easy to "iterate over" in the "old fashioned" C way; you take a (normal) pointer to the zeroth element, and each time you increment it, it points to the next element, until you hit a value that points just past the end of the array (you can compare against that value, but you can't properly try to check what's there - anything can legally happen as a result). To look at an element, you just dereference the pointer. Iterators let you treat standard library containers in the same way, even though their elements aren't necessarily anywhere near each other in memory. (They also mean that, with a couple of carefully chosen typedefs, you can often change a container type - especially between list/vector/deque - without breaking your code.)

With the array, the "pointer to the zeroth element" is simply the name of the array, used as a pointer. The "pointer to just past the last element" is that pointer, plus the number of elements of the array. (Make sure you understand why it's really that simple.) For containers, though, we can't do it like that. Instead, the standard library containers provide .begin() and .end() member functions, which give you the corresponding iterators.

So, now, what's wrong with the code you were given? [smile]

- Typedefs probably would come in handy.
- There's no need to separate out the declaration of 'it'; in C++, we can, and normally should, declare a counter variable directly in the for-loop initializer.
- But for performance reasons, it's often a good idea to calculate the ".end()" first. You know it won't change (assuming you're not trying to insert or remove elements! BTW, this is very tricky to do manually), but it's hard for the compiler to be sure.
- Iterators provide the interface of pointers in all respects; there's no need to use something like '(*it).first', because 'it->first' - the natural syntax - works just fine.
- You're probably wondering what the "elements" of a std::map are, and what the ".first" member is. The answer is, the map stores each key together with the corresponding value, in a templated structure called std::pair. That struct simply has two members, .first and .second. The std::map puts keys into .first and the corresponding values into .second.

So, the provided code is grabbing the key found in each element, and then using it to look up the value (with the map's operator[]). Well, that's a bit silly, don't you think? [smile] We already have the element, so we can get at the value directly: it's just the .second member.

- Meanwhile, let's not repeat ourselves: there are two places where we look up a GUI_widget* and then dereference it. We can factor that out easily: just use a reference. (That will factor out the dereferencing step, too. But don't just use a value! Your thought process might go "dereferencing GUI_widget* yields GUI_widget", but actually it yields "GUI_widget&". Otherwise, we make a copy of the widget!)


typedef std::map<std::string, GUI_widget*> widget_map;
typedef widget_map::iterator widget_iterator;
widget_iterator end = children.end();
for (widget_iterator it = children.begin(); it != end; ++it) {
GUI_widget& widget = *(widget_iterator->second);
std::cout << name << " passing event to child widget" << widget.name << std::endl;
widget.handle_event(E);
}



(Of course, after taking out the debugging statement, making the reference no longer makes sense [smile] But you should practise making this kind of transformation.)

Quote:
What can I do with this that is more powerful than using a foreach (if it existed)?


It does exist, in a sense, but it's not very easy to use. What you do is call a library function, which accepts two iterators (representing beginning and end points) and a function pointer. Since you then (typically) need to move the body of the loop into a new function, it's often not worth the effort. But, since you asked:


typedef std::pair<std::string, GUI_widget*> widget_map_pair;
struct eventDelegator {
// I'm going to use pointers inside here to avoid copies (reference
// data members are often tricky). This means we can't store instances
// of the eventDelegator; we have to make sure the supplied string and
// event will outlive it.
Event* E;
std::string* name;
eventDelegator(const std::string& name, const Event& E): name(&name), E(&E) {}

void delegateEvent(const widget_map_pair& pair) {
GUI_widget& widget = *(pair->second);
std::cout << *name << " passing event to child widget" << widget.name << std::endl;
widget.handle_event(*E);
}
};

// But now we can write the loop more easily:
std::for_each(children.begin(), children.end(), eventDelegator(name, E));
// Notice how we no longer have to care about complicated type names at this point.



Quote:

Also, If I want to pick a random element out of the list, I don't really know how, since I'm not sure how to convert the "std::map<std::string,GUI_widget *>::iterator" into an integer to use with rand().


What list? You have a map.

Quote:
I've read the relevant sections on sgi's reference


Did you try searching the table of contents page for "random"? [smile]

Way down at the bottom, you will find the free function random_sample_n, which copies a random sample of n elements, chosen from an input range, into an output range (i.e. beginning at some iterator, and sequentially afterward). To get one element, we let n = 1, and use a pointer to some variable of the element type be our iterator:


std::pair<std::string, GUI_widget*> random_pair;
std::random_sample_n(children.begin(), children.end(), &random_pair, 1);
// notice the '&', getting a pointer to our variable. Pointers are iterators;
// after all, it's not really that iterators provide the pointer interface, but
// that pointers provide the "iterator interface" modelled after them!
GUI_widget& widget = random_pair->second;



Share this post


Link to post
Share on other sites

This topic is 3593 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this