Generic User #2

sorry to ask such a simple question, but....

what happens when you try to retrieve the value from a key that was never inserted into a map container?

also, if i delete a map container and all the values are pointers, will the referenced objects be deleted too?


i would just test this out normally, but i'm having 'technical issues' with my main comp and the one i'm currently using is prehistoric.


also, another Q:

somewhat concerning the assignment operator and more so with custom data structures.

in the situation of a data structure object being assigned the value of another data structure object, what would happen if the left-hand object returned a null value? what if the right-hand object was returned a null value?

sorry if i'm being too vague, i'll provide more details if necessary.

Sane

I'm sorry if this comes off as being unhelpful, but this is a skill you could quite obviously benefit from: experimentation.

All of these questions you could answer through experimenting with little snippets of code. Even though you can always reference the documentation or ask for help, experimentation can sometimes be faster!

For example, for your first question, write a simple program that tries to access a non-existent item in a map. If I recall correctly, it should return 0 or NULL.

Using this skill effectively can often save you a lot of time and frustration when you aren't so sure about how something works. It also eliminates the need to elaborate or clarify in response to anyone's misunderstanding of your problem(s).

Edit: I just noticed that you said you're having technical issues with your main comp. Well then. Nevermind. But it still makes sense to experiment with all of these things once you get a chance (it sounds like you won't be coding until then either way).

__________________
Waterloo's Canadian Computing Competition (CCC) - Stage 2 Problems, Solutions, and Test Data

mbd

using the operator[] to access a key in a map will create that key. the value returned will depend on the value type. it will use the default constructor to create the value type. if a map contains pointers, it will not automatically delete the objects referenced by those pointers.

Generic User #2

um...is there any way to prevent the operator[] from creating a key?? or is there a similiar data structure to a map?

also, not related, but how do you put in the 'line-numbering' on the 'margins' of the main text window in visual c++ 2008?

mbd

you can check if a key exists using the find method.

Sane

Sorry to hijack, but this could explain why maps haven't been working well for me. It seems that find runs in logarithmic time. Does the operator[] take logarithmic time as well? Under amortized analysis, could it ever be constant?

__________________
Waterloo's Canadian Computing Competition (CCC) - Stage 2 Problems, Solutions, and Test Data

mbd

searching for a key takes log(n) in a map. it would easily be possible to implement map as a hash table, but that will have to wait for a new standard. sgi provides a hash_map.

Sane

Damn associative containers. Useless!

One of my algorithms was timing out because I was making 7,000,000 logarithmic calls to the STL map. No wonder. I'll need to avoid maps from now on. With a proper hash table, maps seem to be completely useless.

__________________
Waterloo's Canadian Computing Competition (CCC) - Stage 2 Problems, Solutions, and Test Data

Generic User #2

thanks for the help guys


ps those last few posts confused me. are you saying that as the number of elements increases, the marginal amount of time per subsequent element increases?

Sane

Yes. But only very slightly. The slow down in lookup won't even be measurable until you get in the hundred's of thousands to millions of insertions within the span of a few seconds. But sometimes that is necessary. For most general applications, an STL map will be the simple and clean solution.

__________________
Waterloo's Canadian Computing Competition (CCC) - Stage 2 Problems, Solutions, and Test Data