標準的なアロケータは連続したメモリを割り当てる必要がありますか？

Question

C++ 11標準では、標準に準拠するアロケータが連続したメモリブロックへのポインタを返す必要があるかどうかを確認できません。

std::vector（23.3.6.1/1）の連続ストレージ要件はそうであるように思われます（それ以外の場合は、std::vectorを任意の標準準拠アロケータで使用することは不可能です）。しかし、どんな説明も大歓迎です。

同等の質問は：私はいつも（おそらくは例えばhereについて記載したよう++ポインタ普通生Cにallocate()によって返さジェネリックpointerタイプを変換した後）、ポインタ算術演算を介しallocate()によって返されたメモリブロックを移動することができますか？

Answer 1

はい、allocator::pointerのポインタ演算が期待どおりに機能するという意味で、連続している必要があります。

考えてみると、返されるメモリは物理的に連続していることはめったにありません。最新のCPUには仮想メモリがあり、はこの仮想メモリ内で解釈されるため、連続して見えるだけです。

Answer 2

contiguousの意味によって異なります。あなたのプログラムに見られるようなメモリは、必ず連続しているか、オフセット/配列を配列に計算するために "うまく動作しません"。 10の整数値を割り当てる場合は、ptr[0]を最初のものにし、最後にptr[9]とします。ptrは1つのポインタに過ぎないため、1つの連続したメモリブロックを指すことができます。

実際の物理メモリでは、OSが判断して決定するもので、連続していてもいなくてもかまいません。アプリケーションメモリを「どこからでも」得ることができます。アロケータAを考えると

Answer 3

は、私がA::allocate(n)によって返されたすべてのpのためならばk間隔[0,n)とstd::addressof(*(p + n - 1)) + 1 == std::addressof(*p) + nにあるときAがstd::addressof(*p) + k == std::addressof(*(p + k))、連続しメモリを提供することを言うでしょう。

アロケータ要件（§17.6.3.5[allocator.requirements]）ではこのプロパティが必要ではありませんが、vector（特にvector::data()）を実装する方法は想像できません。 （a）アロケータ要件に何か不足している、（b）アロケータ要件が不十分である、または（c）vectorがアロケータに一般要件を超えて追加要件を課している。ここ

は、連続したメモリ（paste of this code）を提供しないアロケータの「単純な」の例である：nアイテムのためのスペースを割り当てるように求められたら

#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; 
} 

、ScaledAllocatorは2 * nためのスペースを割り当てます。そのポインタ型は、ポインタ演算にも必要なスケーリングを実行します。実際には、2n項目の配列を割り当て、偶数番目のスロットのみをデータに使用します。

ScaledAllocatorが満たしていないアロケータ要件を誰でも見ることができますか？

編集：この質問への答えは、批判的にアロケータ要件テーブルのメンバ関数allocate(n)の効果の標準の説明の意味にかかっ：「メモリがnタイプTのオブジェクトが、オブジェクトが構築されていないために割り当てられています。 "私はすべてが、p == allocate(n)を指定し、p + kはkを[0,n]に、p + kをに、逆参照できることを意味するということにすべて同意すると思います。言い換えれば、アロケータのポインタ型の領域内で連続しているメモリブロック。

std::vector::data()の説明で非常に間接的に暗示されていますが、明示されていませんが、メモリもローポインタの領域で連続している必要があります（正式な命題は最初の段落で詳しく説明しています）。 （a）すべてのアロケータに適用される連続性要件を明示するか、（b）そのコンセプトをContiguousAllocatorコンセプトに追加し、std::vectorにContiguousAllocatorが必要であると指定するとよいでしょう。