Jump to content
  • Advertisement
Sign in to follow this  
Phillip Martin

std::maps, sets and allocators

This topic is 5126 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

Just a short story on how std::maps and custom allocations don't necessarily play nice together in VC7.1. We hit a small pocket of non-standard behaviour (at least in mine and another persons interpretation, so we could easily be wrong) when using a pool-style allocator and std::maps. The standard defined an allocators max_size() as the largest value of N such that allocate(N, 0) will succeed. In our custom pool allocator, it only ever worked for single element allocates, since it was a very niche allocator, so max_size() should techincially return 1. However this isn't what the VC7.1 implementation expects. Now scoot over to the implementation of the trees in VC7.1, and its got this in the _Tree class:
size_type max_size() const
{   // return maximum possible length of sequence
    return (this->_Alval.max_size());
Where _Alval is the allocator instance. It returns the allocators max_size, which is incorrect behavious, because an allocators max_size() could possibly: a) Change over time due to limited memory constraints b) Be a small number, as it was in our case, always returning 1, because it doesn't deal with array allocations So the Allocators max_size doesn't necessarily map onto the tree's max size. But the bit which is actually causing the problems was this part here, the _Tree::insert method
    iterator _Insert(bool _Addleft, _Nodeptr _Wherenode,
        const value_type& _Val)
        {   // add node with value next to _Wherenode, to left if _Addnode
        if (max_size() - 1 <= _Mysize)
            _THROW(length_error, "map/set<T> too long");
Which checks max_size() - 1 against _Mysize. This is wrong for a number of reasons: 1) assumes that _Alval.max_size() returns the maximum number of nodes 2) That the rebinded _Alnod.allocate(1) will behave as _Alval.max_size() expects. So the workaround is to have custom allocators return a large number of max_size(), even though allocate() may only work for small values, and assert on allocates of values that don't work.

Share this post

Link to post
Share on other sites
From the other thread:
Original post by SiCrane
Original post by Phillip Martin
Off topic:
Although for anyone interested, we hit a wrinkle in the STL implementation of maps and sets for VC7.1. The red black tree implementation makes a few non-standard assumptions with the tree's max_size() method vs the allocator's max_size() method. Pretty interesting stuff (at least for me :D)

That standard provides practically no guarantees for the behavior of max_size(), so it's hard for it to make any non-standard assumptions.

Well, I said it was hard, not impossible. :P But, IIRC, this kind of thing is regarded as a problem in the standard itself and there some discussion in the standards committee about it. I have to go on memory since the ISO/IEC JTC1/SC22/WG21 website doesn't seem to responding right now.

Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!