6

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

(23.3.6.1/1)の連続したストレージ要件は、std::vectorそうであることを暗示しているようです (そうでなければstd::vector、任意の標準準拠のアロケーターでは使用できないようです)。しかし、明確化は大歓迎です。

allocate()同等の質問は次のとおりです:ポインター演算を介してpointer返されたメモリ ブロックを常に移動できますallocate()か?

4

3 に答える 3

5

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

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

于 2013-07-26T10:23:44.457 に答える
4

アロケータAが与えられた場合、が間隔内にAあり.pA::allocate(n)std::addressof(*p) + k == std::addressof(*(p + k))k[0,n)std::addressof(*(p + n - 1)) + 1 == std::addressof(*p) + n

このプロパティがアロケーターの要件 (§17.6.3.5 [allocator.requirements]) で必要とされているとは思えませんが、それなしで実装する方法vector(特にvector::data()) を想像することはできません。(a) アロケーターの要件に欠けているものがある、(b) アロケーターの要件が指定されていない、または (c)vectorアロケーターに一般的な要件を超える追加の要件を課している。

連続したメモリを提供しないアロケーターの「単純な」例を次に示します (このコードを貼り付けます)。

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

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

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

編集: この質問への答えは、アロケーター要件テーブルのメンバー関数の効果に関する標準の説明の意味に大きく依存します:「メモリは型のオブジェクトにallocate(n)割り当てられますが、オブジェクトは構築されません。」この手段が与えられた場合、すべてのinの有効なポインターであり、inの参照解除可能であることに、私たちは皆同意すると思います。つまり、アロケータのポインタ型のドメイン内で連続するメモリ ブロックです。nTp == allocate(n)p + kk[0,n]p + kk[0,n)

明確ではないのは - の記述によって非常に間接的に暗示されていますがstd::vector::data()- メモリは生ポインタのドメインでも連続している必要があるということです (正式な命題は私の最初の段落で詳述されています)。標準が、(a) すべてのアロケーターに適用される隣接要件について明示的であるか、または (b) その要件をContiguousAllocator概念に追加してstd::vector、ContiguousAllocator.

于 2013-07-26T17:53:46.093 に答える