Tuesday, April 3, 2012

Standard Allocator Problems

As I have mentioned before, I do not consider myself an expert on allocators, but I do know a little about them.  In a previous post I explained their purpose, and in a future post I plan to show how to make your own container that uses them.  If I am not an expert, though, what qualifies me to express my concerns about a problem I think that I found in the C++ standard concerning allocators?  Well, starting the topic should be fine, but I think that I will leave the actual "do something about it" to somebody with more experience in such things.

When I say C++ standard, I am referring to "Working Draft, Standard for Programming Language C++", document number N3225=10-0215, dated 2010-11-27.  Why am I using such an old version?  Because it suffices for my needs, I do not wish to take the time to download a more up-to-date (and probably extremely similar) version, and I would rather get the free working draft than the not-free actual standard.  This, of course, does mean that it is possible that, if there was a problem, it was fixed.

What are the allocator requirements?

Section 20.2.5 covers this topic.  It is rather long, so I will only point out the requirements pertinent to the problem.  Let X be an allocator type.  X::value_type and X::pointer must be defined, and all of the pointer-returning functions must return an X::pointer (table 44).  X::reference is mentioned nowhere in the requirements.

Section 20.9.4 covers allocator_traits, which can be used to get information about an allocator.  It, too, only mentions pointer and value_type typedefs in its required interface.  It, too, does not mention a reference typedef.

From the above two sections, one can conclude that it is foolish to assume that an allocator defines a reference typedef.  Instead, value_type& should be used for a reference type.

What about the default allocator?

Section 20.9.5 defines the default allocator.  The default allocator meets all of the above requirements for allocators, and it also implements a reference typedef.  So, if X is the default allocator, X::reference is a valid type and is the same thing as X::value_type&.

The fact that the default allocator does have a reference typedef whereas the requirements don't specify such a thing is not a problem.  It is fine to expand upon stuff and add functionality.

So, what is the problem?

The problem is with unordered_map (section 23.6.1), unordered_multimap (section 23.6.2), unordered_set (section 23.6.3), and unordered_set (section 23.6.4).  These four containers have the following bit of header code:
typedef typename allocator_type::reference reference;
typedef typename allocator_type::const_reference const_reference;
If allocator_type is the default allocator, these will work.  If allocator_type is not the default allocator, these may fail!  Indeed, with a custom allocator that does not define reference types, my compiler will not compile the code.

I glanced at the other containers I knew, and I performed several different searches through the document.  The other containers define a reference as value_type& and should have no problems.

What should be done?

If this error has not been fixed in the final release of the C++11 standard, I suggest it be considered.  If my lack of expertise has instead caused me to imagine issues, please explain the logic behind what I thought to be a problem.

I may contact somebody from the designers of C++ to see what their response is, but that may have to wait until I can condense this description and have time to find out how to contact them and to compose an email.


It seems as though there have been mentions of these allocator references: 1375 and 1318.  Both of these issues were closed after my latest version of the C++ standard documentation.  I do not know if the issue was resolved.

No comments:

Post a Comment