Getting indexed value from std::map

It should crash. You're actually treating the iterator as a pointer, adding index onto it and dereference the result. That's some random address.

You can do this:

std::map::iterator it( map.begin() );
std::advance( it, index );

// now access it->first and it->second

Yeah, but I assume that's the same as doing

std::map<xx,yy>::iterator it = map.begin():for (int i = 0; i < index; i++)    it++;

Which is fine.. but it's still O(n).. I'd ideally like O(1).

The fact that the array notation exists in debugs more suggests that the pair are contiguous in memory? If that's the case, it should be possible to access them by reference, if not... well... darn :p

Edit: Now that I look at it, the order of the pairs in memory is alphabetical, not input order... so it's probably just the debugger being fancy on it's display.

std::map is not a random access container, and so random access to its elements is not possible (as far as the standard goes). The fact that the debugger can display it as a contiguous list only means the debugger can display it as a contiguous list, nothing more.

edit to your edit: MSVC's debugger can display custom containers in special ways. Some apaprently undocumented but quite handy feature. So yes, it can display containers with their useful content only, without the implementation details.

You can not do it because the elements in the map are saved in a tree sorted by key.
This way you can find an element in O(log n) and insert in constant time when you know the right position. The elements can not be contiguous in memory because insert would take O(n) to shift all elements next to the inserted one (or reallocate all elements).

What are you exactly trying to achieve? There might be a good solution using a different container or combination of containers.

For example, if you need indexing elements by order of input, and also need key based lookup for a type T then you can construct two views of the same data:

1. std::vector - provides random access
2. std::map - provides key-based access and ordering*

*if you only need key-based lookup and don't need ordering, you can consider unordered_map instead of map

When determining what container to use, always start with specifying your requirements. So, what are your requirements exactly?

Quote:

Original post by Nyarlath ... insert in constant time when you know the right position. ...

Insertion is O(log(n)), not constant time.

It is constant if you know the position. Also linear for range insertion if the range is already sorted (eg use std::sort on a vector<> then use set::insert( vector::begin(), vector::end()).

Quote:

Complexity guarantees The range constructor, and range constructor with compare, are in general O(N * log(N)), where N is the size of the range. However, they are linear in N if the range is already sorted by value_comp(). Insert with hint is logarithmic in general, but it is amortized constant time if t is inserted immediately before p.

sgi link

Quote:

Original post by chairthrower It is constant if you know the position. Also linear for range insertion if the range is already sorted (eg use std::sort on a vector<> then use set::insert( vector::begin(), vector::end()). Quote: Complexity guarantees The range constructor, and range constructor with compare, are in general O(N * log(N)), where N is the size of the range. However, they are linear in N if the range is already sorted by value_comp(). Insert with hint is logarithmic in general, but it is amortized constant time if t is inserted immediately before p. sgi link

You're right, it's amortized constant time, but that's still not the same as O(c). But we're veering off topic here.

Oh, well, I just switched from vectors to maps, since I decided to ease up on the scripters and reference everything by strings, not ID numbers.

The only other thing is that I was thinking that for condensing these data structure to be sent by packets I could use a ID number and just have the lists be the same on client and server. But now that I think about it, it makes mroe sense to hash the string, use that as a look up on the client and not have to have the entire list stored.

Note that stl could have implemented lg(n) advance and 'get kth element' in a map/set for the cost of some memory overhead, and an additional small amount of work on each insert/delete (that doesn't change the order of it).

I cannot figure out, however, how to have amortised constant time for insert-with-hint (heck, I cannot figure out how they did this currently!)

Quote:

Original post by NotAYakk Note that stl could have implemented lg(n) advance and 'get kth element' in a map/set for the cost of some memory overhead, and an additional small amount of work on each insert/delete (that doesn't change the order of it). I cannot figure out, however, how to have amortised constant time for insert-with-hint (heck, I cannot figure out how they did this currently!)

The hint is an iterator, so it already points to a particular position in the tree. They just verify that this is a proper insertion point, and call the underlying insert_before() function. This is amortized O(1) for the same reason that the range constructor is O(n) for already sorted input. :) Although actually, now that I think about it, it doesn't seem right to me either, considering how much hand-waving I'm doing there o_O

I can get how I can write a range constructor into a binary tree if I can do last-first. I can sort of believe that you can do it without the last-first, but even that is beyond my ken.

But imagine if you have a huge huge tree. And then you insert a bunch of elements right into the middle of it.

This will cause rotation of the entire tree. Somehow the total number of rotations done is a constant factor times the number of insertions.

I guess only 1 in 2 inserts (on average) cause your parent to be rebalanced. And only 1 in 2 of those cause your parent's parent to be rebalanced. Etc. And each such rebalance costs 1 unit of effort.

That sums to 1/2 + 1/2*1/2 + 1/2*1/2*1/2 + ... = 1.

But still, it seems spooky.

Quote:

Oh, well, I just switched from vectors to maps, since I decided to ease up on the scripters and reference everything by strings, not ID numbers. The only other thing is that I was thinking that for condensing these data structure to be sent by packets I could use a ID number and just have the lists be the same on client and server. But now that I think about it, it makes mroe sense to hash the string, use that as a look up on the client and not have to have the entire list stored.

Sharsnik,

Seriously - don't worry about it at this point. Try and get the assets(?) management sytem you are using working and then exposed to the scripting language, and everything else working together. The scripting bit is going to be the more complicated thing - if that is the goal. It is common advice here, but refine these things later, if/when you can demonstrate a specific bottleneck, and once the design has settled down, and after you are comfortable with it. It's true that sorted sets and hashtables behave quite different theoretically - but both are good choices here. For what its worth, I went down the rabbit hole too, and testing showed very little practical difference for std::map vs ext::hash_table for mapping strings at least for my specific context. My hypothesis was that the short circuit involved in string comparison is an advantage compared with the need to always iterate the length (or reasonable fixed ammount) of the string in computing a hash. In any case it's probably it is arguably less important than getting the overall picture working.

Yeah, I just got bored, and figured I'd switch it up before the code got bigger and bigger :p

And in general, nothing wrong with trying to get rid of O(n) when you're looking at pretty huge n's in the future :p

I still use vectors for the per-object lists, since those n's will never exceded 50ish.

Quote:

Original post by NotAYakk I guess only 1 in 2 inserts (on average) cause your parent to be rebalanced. And only 1 in 2 of those cause your parent's parent to be rebalanced. Etc. And each such rebalance costs 1 unit of effort. That sums to 1/2 + 1/2*1/2 + 1/2*1/2*1/2 + ... = 1. But still, it seems spooky.

I'm pretty sure that restoring balance to a red-black tree after a single insert, can always be done in exactly two rotates.
I suspect that it's more a case of it sometimes taking longer to find those points of rotation (as per the limit equation you've shown).