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.


Update:

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