Are standard allocators required to allocate contiguous memory?

Question

I cannot find in the C++11 standard any indication to whether a standard-conforming allocator is required to return a pointer to a contiguous memory block or not.

The contiguous storage requirement on std::vector (23.3.6.1/1) seems to imply so (otherwise it seems like it would be impossible to use std::vector with an arbitrary standard-conforming allocator). But any clarification would be most welcome.

An equivalent question is: can I always move through the memory block returned by allocate() via pointer arithmetics (possibly after converting the generic pointer type returned by allocate() to a plain raw C++ pointer as described for instance here)?

Answer 1

Yes, it has to be contiguous, in the sense that pointer arithmetic on allocator::pointer works as expected.

If you think about it, the memory returned rarely is contiguous, physically. It only looks contiguous because modern CPU's have virtual memory, and X* is interpreted within this virtual memory.

Answer 2

Given an allocator A, I would say that A provides contiguous memory if for any p returned by A::allocate(n), std::addressof(*p) + k == std::addressof(*(p + k)) when k is in the interval [0,n) and std::addressof(*(p + n - 1)) + 1 == std::addressof(*p) + n.

I don't see this property being required in the allocator requirements (§17.6.3.5 [allocator.requirements]), but I can't imagine how to implement vector (and especially vector::data()) without it. Either (a) I'm missing something in the allocator requirements, (b) the allocator requirements are underspecified, or (c) vector is imposing an additional requirement on its allocator beyond the general requirements.

Here is a "simple" example of an allocator that does not provide contiguous memory (paste of this code):

#include <cstddef>
#include <iostream>
#include <iterator>
#include <limits>
#include <memory>

template <typename T>
class ScaledPointer : public std::iterator<std::random_access_iterator_tag, T> {
  T* ptr;
public:
  ScaledPointer() = default;
  ScaledPointer(T* ptr) : ptr(ptr) {}
  template <typename U>
  explicit ScaledPointer(U* ptr) : ptr(static_cast<T*>(ptr)) {}
  template <typename U>
  explicit ScaledPointer(const ScaledPointer<U>& other) :
    ptr(static_cast<T*>(other.ptr)) {}

  explicit operator bool () const { return bool{ptr}; }

  T& operator * () const {
    return *ptr;
  }
  T* operator -> () const {
    return ptr;
  }

  T& operator [] (std::ptrdiff_t n) const {
    return ptr[2 * n];
  }

  ScaledPointer& operator ++ () {
    ptr += 2;
    return *this;
  }
  ScaledPointer operator ++ (int) {
    ScaledPointer tmp(*this);
    ++*this;
    return tmp;
  }

  ScaledPointer& operator -- () {
    ptr -= 2;
    return *this;
  }
  ScaledPointer operator -- (int) {
    ScaledPointer tmp(*this);
    --*this;
    return tmp;
  }

  template <typename U, typename V>
  friend bool operator == (const ScaledPointer<U>& u, const ScaledPointer<V>& v) {
    return u.ptr == v.ptr;
  }
  template <typename U, typename V>
  friend bool operator != (const ScaledPointer<U>& u, const ScaledPointer<V>& v) {
    return !(u == v);
  }

  template <typename U, typename V>
  friend bool operator < (const ScaledPointer<U>& u, const ScaledPointer<V>& v) {
    return u.ptr < v.ptr;
  }
  template <typename U, typename V>
  friend bool operator > (const ScaledPointer<U>& u, const ScaledPointer<V>& v) {
    return v < u;
  }
  template <typename U, typename V>
  friend bool operator <= (const ScaledPointer<U>& u, const ScaledPointer<V>& v) {
    return !(v < u);
  }
  template <typename U, typename V>
  friend bool operator >= (const ScaledPointer<U>& u, const ScaledPointer<V>& v) {
    return !(u < v);
  }

  ScaledPointer& operator += (std::ptrdiff_t n) {
    ptr += 2 * n;
    return *this;
  }
  friend ScaledPointer operator + (const ScaledPointer& u, std::ptrdiff_t n) {
    ScaledPointer tmp = u;
    tmp += n;
    return tmp;
  }


  ScaledPointer& operator -= (std::ptrdiff_t n) {
    ptr -= 2 * n;
    return *this;
  }
  friend ScaledPointer operator - (const ScaledPointer& u, std::ptrdiff_t n) {
    ScaledPointer tmp = u;
    tmp -= n;
    return tmp;
  }

  friend std::ptrdiff_t operator - (const ScaledPointer& a, const ScaledPointer& b) {
    return (a.ptr - b.ptr) / 2;
  }
};

template <typename T>
class ScaledAllocator {
public:
  typedef ScaledPointer<T> pointer;
  typedef T value_type;
  typedef std::size_t size_type;

  pointer allocate(size_type n) {
    const std::size_t size = (n * (2 * sizeof(T)));
    void* p = ::operator new(size);
    std::cout << __FUNCTION__ << '(' << n << ") = " << p << std::endl;
    std::fill_n((unsigned*)p, size / sizeof(unsigned), 0xFEEDFACEU);
    return pointer{p};
  }

  void deallocate(pointer p, size_type n) {
    std::cout << __FUNCTION__ << '(' << &*p << ", " << n << ')' << std::endl;
    ::operator delete(&*p);
  }

  static size_type max_size() {
    return std::numeric_limits<size_type>::max() / 2;
  }

  template <typename U, typename V>
  friend bool operator == (const ScaledAllocator<U>&, const ScaledAllocator<V>&) {
    return true;
  }
  template <typename U, typename V>
  friend bool operator != (const ScaledAllocator<U>&, const ScaledAllocator<U>&) {
    return false;
  }
};

#include <algorithm>
#include <vector>

int main() {
  using namespace std;
  cout << hex << showbase;

  vector<unsigned, ScaledAllocator<unsigned>> vec = {0,1,2,3,4};
  for_each(begin(vec), end(vec), [](unsigned i){ cout << i << ' '; });
  cout << endl;

  auto p = vec.data();
  for(auto i = decltype(vec.size()){0}, n = vec.size(); i < n; ++i)
    cout << p[i] << ' ';
  cout << endl;
}

When asked to allocate space for n items, ScaledAllocator allocates space for 2 * n. Its pointer type performs the necessary scaling for its pointer arithmetic as well. In effect, it allocates an array of 2n items and only uses the even-numbered slots for data.

Can anyone see an allocator requirement that ScaledAllocator fails to satisfy?

Edit: The answer to this question critically hinges upon the meaning of the standard's description of the effects of the member function allocate(n) in the allocator requirements table: "Memory is allocated for n objects of type T but objects are not constructed." I think we would all agree that this means given p == allocate(n) then p + k is a valid pointer for all k in [0,n] and that p + k is dereferencable for k in [0,n). In other words, a block of memory that is contiguous in the domain of the allocator's pointer type.

What isn't clear - although it's very very indirectly implied by the description of std::vector::data() - is that the memory also needs to be contiguous in the domain of raw pointers (the formal proposition detailed in my first paragraph). It would be nice if the standard would either (a) be explicit about the contiguity requirement applying to all allocators, or (b) add that requirement to a ContiguousAllocator concept and specify that std::vector requires a ContiguousAllocator.

Answer 3

It depends on what you mean by contiguous. The memory, as seen by your program will definitely be contiguous, or it won't "work right" for calculating offsets/indexes into arrays, and such like. If you allocate 10 integer values, you want ptr[0] to be the first one, and ptr[9] to be the last one - since ptr is only a single pointer, it can only point to a single, contiguous block of memory.

Under the hood, in the real physical memory, it may be contiguous or not - that's something for the OS to determine and decide, and it may well give the application memory from "anywhere".