# 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.

## 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 on other sites
Quote:
Original post by SiCrane
Quote:
 Original post by Phillip MartinOff 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.

1. 1
2. 2
Rutin
20
3. 3
khawk
18
4. 4
A4L
14
5. 5

• 12
• 16
• 26
• 10
• 44
• ### Forum Statistics

• Total Topics
633762
• Total Posts
3013727
×