Allocators For Nested Container

Following a talk about allocators at CppCon, I came across the following piece of code:

#include <iostream>
#include <string>
#include <utility>
#include <vector>

namespace {

template <typename T>
class MyAllocator {
 public:
  using value_type = T;

  MyAllocator(std::string iType) : _type(std::move(iType)) {}

  T* allocate(const std::size_t iNo) { return new T[iNo]; }
  void deallocate(T* iPtr, const std::size_t) { delete[] iPtr; }

  constexpr bool operator!=(const MyAllocator& oth) const {
    return _type != oth._type;
  }

  const std::string& getType() const noexcept { return _type; }

 private:
  std::string _type;
};

using MyString =
    std::basic_string<char, std::char_traits<char>, MyAllocator<char>>;

}  // anonymous namespace

int main(int, char**) {
  ::MyString str1(::MyAllocator<char>("ForStr1"));
  ::MyString str2(::MyAllocator<char>("ForStr2"));
  ::MyString str3(::MyAllocator<char>("ForStr3"));

  std::vector<::MyString> aVector;
  aVector.reserve(1024);

  aVector.push_back(str1);
  aVector.push_back(str2);

    std::cout << "[0]: " << aVector[0].get_allocator().getType() << "\n"
              << "[1]: " << aVector[1].get_allocator().getType() << "\n";


  aVector.insert(aVector.begin(), str3);

  const auto& type0 = aVector[0].get_allocator().getType();
  const auto& type1 = aVector[1].get_allocator().getType();
  const auto& type2 = aVector[2].get_allocator().getType();

  std::cout << "[0]: " << type0 << "\n"
            << "[1]: " << type1 << "\n"
            << "[2]: " << type2 << "\n";

  return 0;
}

I guess the general topic here is about "allocators in nested containers". Although functionally speaking, I get the issue, I cannot understand what happened in the code.

In the code, we have a custom allocator which, essentially, behaves like the default allocator except it stores a kind of data internally.

I build three different strings with three different instances of the same allocator:

using MyString = 
    std::basic_string<char, std::char_traits<char>, MyAllocator<char>>;

::MyString str1(::MyAllocator<char>("ForStr1"));
::MyString str2(::MyAllocator<char>("ForStr2"));
::MyString str3(::MyAllocator<char>("ForStr3"));

Now I have a simple std::vector<MyString>:

std::vector<::MyString> aVector;
aVector.reserve(1024);

I reserved the space in order to avoid reallocation.

Now I push the first two strings:

aVector.push_back(str1);
aVector.push_back(str2);

std::cout << "[0]: " << aVector[0].get_allocator().getType() << "\n"
          << "[1]: " << aVector[1].get_allocator().getType() << "\n";

// As expected, it prints:
//       [0]: ForStr1
//       [1]: ForStr2

The result of the print is what I expect. I assume the allocator is owned by the std::string container.

However if I force some copy/movements (rearrangement) with an:

aVector.insert(aVector.begin(), str3);

// Now we have vector be like:
//  [str3:ForStr3]    [str1:ForStr1]    [str2:ForStr2]

Then, the allocators associated with the strings inside the vector seem to be corrupted:

const auto& type0 = aVector[0].get_allocator().getType();
const auto& type1 = aVector[1].get_allocator().getType();
const auto& type2 = aVector[2].get_allocator().getType();

std::cout << "[0]: " << type0 << "\n"
          << "[1]: " << type1 << "\n"
          << "[2]: " << type2 << "\n";

It prints:

[0]: ForStr1
[1]: ForStr2
[2]: ForStr2

I expect:

[0]: ForStr3
[1]: ForStr1
[2]: ForStr2

---

Why this behaviour? Is there an UB that I missed? The allocator associated with a std::string is part of the object itself, isn't?

It is a consequence of horizontal propagation of allocators, which is performed by the container depending on POCCA, POCMA and POCS for copy assign, move assign and swap operation, respectively.

In your example, the insert() member function moves the two already-existing elements to free the first position for the new element. The process can be summarized in the following scheme.

1. The str2 object is move constructed at the end of the array, leaving the original object in a valid but undefined state (*str2). During the move construction, the allocator is also moved. It is important to note that the moved-from allocator is guaranteed to compare equal the moved-to allocator, and therefore the *str2 object still contains its original allocator.

  +-----------------------------------
  | str1(a1) | *str2(a2) | str2(a2) |
  +-----------------------------------

2. The str1 object is move assigned to the *str2 object. The container checks for the propagate_on_container_move_assignment type trait through the std::allocator_traits interface. Since the allocator does not provide such a type, the class will select its defaulted one, which evaluates to false. This means that the allocator can not propagated to the target object, and it is necessary to adopt its allocator.

  +-----------------------------------
  | *str1(a1) | str1(a2) | str2(a2) |
  +-----------------------------------

3. The str3 object is copy assigned to the *str1 object. Similarly to the previous step, the container checks for the propagate_on_container_copy_assignment type trait through the std::allocator_traits interface. Since the allocator does not provide such a type, the class will select its defaulted one, which evaluates to false. This means that the allocator can not propagated to the target object, and it is necessary to adopt its allocator.

  +----------------------------------
  | str3(a1) | str1(a2) | str2(a2) |
  +----------------------------------