Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

User-provided std::allocator specialization

Class templates in the ::std namespace can generally be specialized by programs for user-defined types. I did not find any exception to this rule for std::allocator.

So, am I allowed to specialize std::allocator for my own types? And if I am allowed to, do I need to provide all members of std::allocator's primary template, given that many of them can be provided by std::allocator_traits (and are consequently deprecated in C++17)?

Consider this program

#include<vector>
#include<utility>
#include<type_traits>
#include<iostream>
#include<limits>
#include<stdexcept>

struct A { };

namespace std {
    template<>
    struct allocator<A> {
        using value_type = A;
        using size_type = std::size_t;
        using difference_type = std::ptrdiff_t;
        using propagate_on_container_move_assignment = std::true_type;

        allocator() = default;

        template<class U>
        allocator(const allocator<U>&) noexcept {}

        value_type* allocate(std::size_t n) {
            if(std::numeric_limits<std::size_t>::max()/sizeof(value_type) < n)
                throw std::bad_array_new_length{};
            std::cout << "Allocating for " << n << "\n";
            return static_cast<value_type*>(::operator new(n*sizeof(value_type)));
        }

        void deallocate(value_type* p, std::size_t) {
            ::operator delete(p);
        }

        template<class U, class... Args>
        void construct(U* p, Args&&... args) {
            std::cout << "Constructing one\n";
            ::new((void *)p) U(std::forward<Args>(args)...);
        };

        template<class U>
        void destroy( U* p ) {
            p->~U();
        }

        size_type max_size() const noexcept {
            return std::numeric_limits<size_type>::max()/sizeof(value_type);
        }
    };
}

int main() {
    std::vector<A> v(2);
    for(int i=0; i<6; i++) {
        v.emplace_back();
    }
    std::cout << v.size();
}

The output of this program with libc++ (Clang with -std=c++17 -Wall -Wextra -pedantic-errors -O2 -stdlib=libc++) is:

Allocating for 2
Constructing one
Constructing one
Allocating for 4
Constructing one
Constructing one
Allocating for 8
Constructing one
Constructing one
Constructing one
Constructing one
8

and the output with libstdc++ (Clang with -std=c++17 -Wall -Wextra -pedantic-errors -O2 -stdlib=libstdc++) is:

Allocating for 2
Allocating for 4
Constructing one
Constructing one
Allocating for 8
Constructing one
Constructing one
Constructing one
Constructing one
8

As you can see libstdc++ does not always honor the overload of construct that I have provided and if I remove the construct, destroy or max_size members, then the program doesn't even compile with libstdc++ complaining about these missing members, although they are supplied by std::allocator_traits.

Does the program have undefined behavior and are therefore both standard libraries correct, or is the program's behavior well-defined and the standard library required to use my specialization?


Note that there are some members from std::allocator's primary template that I still left out in my specialization. Do I need to add them as well?

To be precise, I left out

using is_always_equal = std::true_type

which is provided by std::allocator_traits since my allocator is empty, but would be part of std::allocator's interface.

I also left out pointer, const_pointer, reference, const_reference, rebind and address, all of which are provided by std::allocator_traits and deprecated in C++17 for std::allocator's interface.

If you think that it is required to define all of these to match std::allocator's interface, then please consider them added to the code.

like image 699
walnut Avatar asked Apr 11 '20 01:04

walnut


1 Answers

According to 23.2.1 [container.requirements.general]/3:

For the components affected by this subclause that declare an allocator_type, objects stored in these components shall be constructed using the allocator_traits<allocator_type>::construct function

Also, according to 17.6.4.2.1:

The program may add a template specialization for any standard library template to namespace std only if the declaration depends on a user-defined type and the specialization meets the standard library requirements for the original template and is not explicitly prohibited.

I don't think the standard prohibits specializing std::allocator, since I read through all sections on std::allocator and it didn't mention anything. I also looked at what it looks like for the standard to prohibit specialization and I didn't find anything like it for std::allocator.

The requirements for Allocator are here, and your specialization satisfies them.

Therefore, I can only conclude that libstdc++ actually violates the standard (perhaps I made a mistake somewhere). I found that if one simply specializes std::allocator, libstdc++ will respond by using placement new for the constructor because they have a template specialization specifically for this case while using the specified allocator for other operations; the relevant code is here (this is in namespace std; allocator here is ::std::allocator):

  // __uninitialized_default_n_a
  // Fills [first, first + n) with n default constructed value_types(s),
  // constructed with the allocator alloc.
  template<typename _ForwardIterator, typename _Size, typename _Allocator>
    _ForwardIterator
    __uninitialized_default_n_a(_ForwardIterator __first, _Size __n, 
                _Allocator& __alloc)
    {
      _ForwardIterator __cur = __first;
      __try
    {
      typedef __gnu_cxx::__alloc_traits<_Allocator> __traits;
      for (; __n > 0; --__n, (void) ++__cur)
        __traits::construct(__alloc, std::__addressof(*__cur));
      return __cur;
    }
      __catch(...)
    {
      std::_Destroy(__first, __cur, __alloc);
      __throw_exception_again;
    }
    }

  template<typename _ForwardIterator, typename _Size, typename _Tp>
    inline _ForwardIterator
    __uninitialized_default_n_a(_ForwardIterator __first, _Size __n, 
                allocator<_Tp>&)
    { return std::__uninitialized_default_n(__first, __n); }

std::__uninitialized_default_n calls std::_Construct which uses placement new. This explains why you don't see "Constructing one" before "Allocating for 4" in your output.

EDIT: As OP pointed out in a comment, std::__uninitialized_default_n calls

__uninitialized_default_n_1<__is_trivial(_ValueType)
                             && __assignable>::
__uninit_default_n(__first, __n)

which actually has a specialization if __is_trivial(_ValueType) && __assignable is true, which is here. It uses std::fill_n (where value is trivially constructed) instead of calling std::_Construct on each element. Since A is trivial and copy assignable, it would actually end up calling this specialization. Of course, this does not use std::allocator_traits<allocator_type>::construct either.

like image 190
Leonid Avatar answered Nov 09 '22 22:11

Leonid