我可以使用 stl 分配器使整个 stl 容器及其内容（键和值）存储在我创建的内存块中吗？

Question

我想知道我是否可以使用 stl 分配器 (http://www.drdobbs.com/the-standard-librarian-what-are-allocato/184403759) 或任何其他 C++ 机制来达到我的目的。

我自己分配了一个很大的内存块。

我想创建一个像 map 这样的 stl 容器，这样容器，包括存储在容器中的键和值，都存储在这个内存块中。

明确地说，当我说 "the container, including the keys and values" 时，我指的是通常由容器内的代码在堆上分配的所有内存位。例如。图结构，以及键和值的副本。

地图对象本身（不包括上述位）在我的内存块中的存储将由我处理。显然我找不到别的东西来帮我做这件事。

我知道有些回复可能是 "don't"，但请幽默一下，假设我有充分的理由想要将所有内容存储在我预先分配的内存块中。

Answer 1

简短的回答，是的，你可以用 C++11 分配器来做到这一点。

分配器是一个有点复杂的话题。可以在 Alisdair Meredith 的 CppCon 2014 演讲中找到对 C++11 分配器的很好介绍 part 1 and part 2

C++11 引入了 scoped_allocator_adaptor，这是在嵌套 STL 类型（例如 map<string, vector<string>>.

然而，需要注意的是：没有一种好的便携方法可以提前确定您的内存块需要多大才能容纳您想要存储在其中的所有内容。为了健壮和便携，您需要预先制作一个 'best guess'，然后处理最终需要分配比您在大块中保留的内存更多的内存的情况。

Answer 2

用C++2003也可以，分配器class写起来不是很困难，下面是我在vs2005中使用的小例子，采用clang编译。它计算 unordered_map 要求的特定用法的内存字节数。

ps。你说你有一块内存，你希望你的自定义分配器从中进行分配，为了让它工作，你需要有某种分配器来处理频繁的 allocations/deallocations - 为此你可能想要检查out Doug Lea malloc 可以配置为使用这样的内存块。

http://coliru.stacked-crooked.com/a/e27368e784123954

#include <iostream>
#include <string>
#include <memory>
#include <unordered_map>
#include <limits>

int total_alloc = 0;

template <class T>
class MyAllocator {
public:
  // type definitions
  typedef T        value_type;
  typedef T*       pointer;
  typedef const T* const_pointer;
  typedef T&       reference;
  typedef const T& const_reference;
  typedef std::size_t    size_type;
  typedef std::ptrdiff_t difference_type;

  // rebind allocator to type U
  template <class U>
  struct rebind {
    typedef MyAllocator<U> other;
  };

  // return address of values
  pointer address(reference value) const {
    return &value;
  }
  const_pointer address(const_reference value) const {
    return &value;
  }

  /* constructors and destructor
  * - nothing to do because the allocator has no state
  */
  MyAllocator() throw() {
  }
  MyAllocator(const MyAllocator&) throw() {
  }
  template <class U>
  MyAllocator(const MyAllocator<U>&) throw() {
  }
  ~MyAllocator() throw() {
  }

  // return maximum number of elements that can be allocated
  size_type max_size() const throw() {
    return (std::numeric_limits<size_t>::max)() / sizeof(T);
  }

  // allocate but don't initialize num elements of type T
  pointer allocate(size_type num, const void* = 0) {
    pointer ret = (pointer)malloc(num*sizeof(T));
    total_alloc += num*sizeof(T);
    return ret;
  }

  // initialize elements of allocated storage p with value value
  void construct(pointer p, const T& value) {
    ::new((void*)p) T(value);
  }

  // destroy elements of initialized storage p
  void destroy(pointer p) {
    // destroy objects by calling their destructor
    p->~T();
  }

  // deallocate storage p of deleted elements
  void deallocate(pointer p, size_type num) {
      total_alloc -= num*sizeof(T);
    free(p);
  }
};

/// return that all specializations of this allocator are interchangeable
template <class T1, class T2>
bool operator== (const MyAllocator<T1>&,
  const MyAllocator<T2>&) throw() {
  return true;
}
template <class T1, class T2>
bool operator!= (const MyAllocator<T1>&,
  const MyAllocator<T2>&) throw() {
  return false;
}

typedef std::basic_string<char, std::char_traits<char>, MyAllocator<char> > stringx;

namespace std
{
template<>
struct hash<stringx> {
    size_t operator()(const stringx &str) const {
        std::hash<const char*> str_hash;
        return str_hash(str.c_str());
    }
};
}

typedef std::unordered_map<stringx, int,
  std::hash<stringx>,
  std::equal_to<stringx>,
  MyAllocator<std::pair<const stringx, std::pair<stringx, int> > > > sample_map_type;

int main()
{
  sample_map_type sample_map;
  sample_map["test1"] = 1;
  sample_map["test2"] = 2;
  for (auto elem : sample_map) {
    std::cout << elem.first << " -> " << elem.second << std::endl;
  }
  std::cout << "total_alloc = " << total_alloc << std::endl;
}

我可以使用 stl 分配器使整个 stl 容器及其内容（键和值）存储在我创建的内存块中吗？

Can I use stl allocators to make both an entire stl container and it's contents (keys and values) be stored inside a memory block that I created?

c++

memory-management

stl

allocator