basic_string implementation of libstdc++ in GCC and custom pointers

Question

I tried to study libstdc++ source code (GCC 7.2) recently and was confused. Probably I have missed something important, but I started to think that it is impossible to implement basic_string class that will fully comply C++ standard.

Here is a problem that I have faced.

1. basic_string should be able to accept custom allocator class as template parameter.
2. allocate method is required as a part of allocator.
3. allocate is allowed to return objects of user-defined type that "acts like pointer to allocated data". Let's call it my_pointer.
4. my_pointer should satisfy only the requirements for NullablePointer and RandomAccessIterator. All other requirements are optional. According to standard we may be unable to cast my_pointer to CharT* type (another basic_string template parameter) because it is optional.
5. On the other hand const CharT* c_str() method should be implemented as a part of the standard, so we have to know how to make this cast.

Items 4 and 5 are conflicting and I don't know how to resolve it. Hope that you can help me to figure it out.

Thank you!

Answer 1

There are several requirements from the standard that together always ensure the conversion is possible, at least indirectly

1. Given basic_­string<charT, traits, Allocator>, the standard requires charT and allocator_traits<Allocator>::value_type be equal.

2. allocator_traits<Allocator>::pointer is required to be either Allocator::pointer or Allocator::value_type*.

   • In the former case, given a Allocator::pointer p, *p is required to be Allocator::value_type&.

   • In the latter case, everything is trivial.

3. Allocator::pointer is required to be a contiguous iterator, which requires, given a contiguous iterator q, *(q + n) == *(addressof(*q) + n)

4. Given an Allocator a, a.allocate(n) is required to return a Allocator::pointer.

Combining everything together, it means this is always correct

template<typename charT, typename traits = /* ... */, typename Allocator = /* ... */>
class basic_string
{
    typename std::allocator_traits<Allocator>::pointer _data;
    // ...

public:
    charT* c_str() { return std::addressof(*_data); }
    // ...
};

Where _data possibly stores the result from a previous call to Allocator::allocate