不正なアロケータの実装

Question

私はかなり単純な問題があります。私はスレッドセーフでないアロケータを作成しています。アロケータはかなり単純なメモリアリーナ戦略です。大きなチャンクを割り当て、その中にすべてのアロケーションを入れ、アロケーションのために何もしないで、アリーナ破壊の全体を取り除きます。ただし、実際にはにしようとすると、このスキームはアクセス違反をスローします。

static const int MaxMemorySize = 80000; 
template <typename T> 
class LocalAllocator 
{ 
    public: 
     std::vector<char>* memory; 
     int* CurrentUsed; 
     typedef T value_type; 
     typedef value_type * pointer; 
     typedef const value_type * const_pointer; 
     typedef value_type & reference; 
     typedef const value_type & const_reference; 
     typedef std::size_t size_type; 
     typedef std::size_t difference_type; 

    template <typename U> struct rebind { typedef LocalAllocator<U> other; }; 

    template <typename U> 
    LocalAllocator(const LocalAllocator<U>& other) { 
     CurrentUsed = other.CurrentUsed; 
     memory = other.memory; 
    } 
    LocalAllocator(std::vector<char>* ptr, int* used) { 
     CurrentUsed = used; 
     memory = ptr; 
    } 
    template<typename U> LocalAllocator(LocalAllocator<U>&& other) { 
     CurrentUsed = other.CurrentUsed; 
     memory = other.memory; 
    } 
    pointer address(reference r) { return &r; } 
    const_pointer address(const_reference s) { return &r; } 
    size_type max_size() const { return MaxMemorySize; } 
    void construct(pointer ptr, value_type&& t) { new (ptr) T(std::move(t)); } 
    void construct(pointer ptr, const value_type & t) { new (ptr) T(t); } 
    void destroy(pointer ptr) { static_cast<T*>(ptr)->~T(); } 

    bool operator==(const LocalAllocator& other) const { return Memory == other.Memory; } 
    bool operator!=(const LocalAllocator&) const { return false; } 

    pointer allocate(size_type n) { 
     if (*CurrentUsed + (n * sizeof(T)) > MaxMemorySize) 
      throw std::bad_alloc(); 
     auto val = &(*memory)[*CurrentUsed]; 
     *CurrentUsed += (n * sizeof(T)); 
     return reinterpret_cast<pointer>(val); 
    } 
    pointer allocate(size_type n, pointer) { 
     return allocate(n); 
    } 
    void deallocate(pointer ptr, size_type n) {} 

    pointer allocate() { 
     return allocate(sizeof(T)); 
    } 
    void deallocate(pointer ptr) {} 
}; 

私はMaxMemorySizeにリサイズされたベクトルを指すようにmemoryを初期化してきた、と私はまたゼロであるint型を指すようにCurrentUsed初期化しました。これらの値を持つアロケータをstd::unordered_mapのコンストラクタに渡しましたが、STL内部でアクセス違反が発生し続けます。助言がありますか？

編集：

std::vector<char> memory; 
int CurrentUsed = 0; 
memory.resize(80000); 
std::unordered_map<int, int, std::hash<int>, std::equal_to<int>, LocalAllocator<std::pair<const int, int>>> dict(
    std::unordered_map<int, int>().bucket_count(), 
    std::hash<int>(), 
    std::equal_to<int>(), 
    LocalAllocator<std::pair<const int, int>>(&memory, &CurrentUsed) 
); 
// start timer 
QueryPerformanceCounter(&t1); 

for (int i=0;i<10000;i++) 
    dict[i]=i; // crash 

編集：ブラッディ地獄ここに私の使い方です。サイズを1MBに増やしたときにうまくいった。それを投げずに動作させるには、80万バイト以上に増やさなければならなかった。

Answer 1

このコードをテストすると、rebindが同じメモリブロックに対して複数のアロケータを要求するために使用されています。私は（size_type）を割り当てるの上部に

cout << n << " " << sizeof(T) << " " << typeid(T).name() << endl; 

を入れて、私はunordered_mapに三つの要素を追加したときに得た：

1 64 struct std::_List_nod<...> 
16 4 struct std::_List_iterator<...> 
1 64 struct std::_List_nod<...> 
1 64 struct std::_List_nod<...> 
1 64 struct std::_List_nod<...> 

実装が偶然に素敵なラウンド64バイトの要求、これを使用していない場合クラスは誤整列割り当てを返します。

Answer 2

MSVC10のハッシュテーブル型は、小さな値の型にはわずかなスペースオーバーヘッドしかありません。あなたが予約してbad_allocを投げているスペースの量を超えてしまいます。

すべての要素を保持するlist<value_t>と要素あたり2〜16スロットのハッシュバケットvector<list<value_t>::iterator>として実装されています。

これは、1要素あたり合計4〜18ポインターのオーバーヘッドです。

この実装のようなものは、おそらく標準で必要です。ベクトルとは異なり、unordered_mapには、コンテナに一度追加された要素は移動しないという要件があります。