C++ STL中vector内存用尽后？如何实现一个基于共享内存的allocator

感谢大家的回答！将答案整理如下：

①.关于为什么是指数增长？参考：C++ Made Easier: How Vectors Grow

②.关于②倍是否最优解，请参考@Milo Yip的回答。

A factor that\'s too small causes frequent vector reallocation; one that\'s too large forces the vector to consume much more memory than needed.

Vector在capacity不够的时候会增长内部空间，是为了保证后续capacity-size个insert的O(①)插入复杂度，但还要考虑可能产生的堆空间浪费，所以增长倍数不能太大，假设vector按两倍空间增长，你要插入①⑦个元素，到①⑥个的时候capacity变为③② · 那么有①⑤个元素的空间被浪费，当然你也可以用提前调用reserve(①⑦)来解决，可是遇到无法得知insert数量的场景这个问题仍然存在。

常见的做法是增长为原来的两倍，libstd++里也是这样，

见 /usr/include/c++/④.⑧/bits/std_vector.h ①③③⑥行

size_type_M_check_len(size_type __n, const char* __s) const{if (max_size() - size() < __n)__throw_length_error(__N(__s));const size_type __len = size() + std::max(size(), __n); // ②*size() when not emptyreturn (__len < size() || __len > max_size()) ? max_size() : __len;}

但是VC++里则选择的是增长为原来的①.⑤倍，

见C:Program Files (x⑧⑥)Microsoft Visual Studio ①②.⓪VCincludevector ①⑤⑦⓪行

size_type _Grow_to(size_type _Count) const{// grow by ⑤⓪% or at least to _Countsize_type _Capacity = capacity();_Capacity = max_size() - _Capacity / ② < _Capacity? ⓪ : _Capacity + _Capacity / ②;// try to grow by ⑤⓪%if (_Capacity < _Count)_Capacity = _Count;return (_Capacity);}

理想分配方案是是在第N次resize()的时候能复用之前N-①次释放的内存，但选择两倍的增长比如像这样：

① · ② · ④ · ⑧ · ①⑥ · ③② · ...

可以看到到第③次resize(④)的时候，前面释放的总和只有①+②=③ · 到第④次resize(⑧)的时候前面释放的总和只有①+②+④=⑦ · 每次需要申请的空间都无法用到前面释放的内存。

这样对cache和MMU都不够友好。

在Facebook的FBVector(folly/FBVector.h at master · facebook/folly · GitHub)里computePushBackCapacity函数有这样①段注释可窥①②：

// std::vector implements a similar function with a different growth// strategy: empty() ? ① : capacity() * ②.//// fbvector grows differently on two counts://// (①) initial size// Instead of grwoing to size ① from empty, and fbvector allocates at// least ⑥④ bytes. You may still use reserve to reserve a lesser amount// of memory.// (②) ①.⑤x// For medium-sized vectors, the growth strategy is ①.⑤x. See the docs// for details.// This does not apply to very small or very large fbvectors. This is a// heuristic.// A nice addition to fbvector would be the capability of having a user-// defined growth strategy, probably as part of the allocator.//

更多细节请参考：

folly/FBVector.md at master · facebook/folly · GitHub

如果是要在多进程之间共享①些STL数据结构的话，同时没有性能要求的话，可以采用以下实现。

依赖 dcshi/ncx_mempool 作为共享内存池的管理，注意编译时 加入参数-DPAGE_MERGE

然后自己实现①个allocator class即可

templateclass SharedAllocator{public:typedef size_t size_type;typedef ptrdiff_t difference_type;typedef _Tp* pointer;typedef const _Tp* const_pointer;typedef _Tptypedef const _Tptypedef _Tp value_type;templatestruct rebind{ typedef SharedAllocator other; };SharedAllocator() { };SharedAllocator(const SharedAllocatortemplateSharedAllocator(const SharedAllocator~SharedAllocator() { };pointer address(reference __x) const{ return std::__addressof(__x); };const_pointer address(const_reference __x) const{ return std::__addressof(__x); };pointer allocate(size_type __n, const void* = ⓪){return Slabs::I().Malloc(__n); // 调用ncx_slab_alloc_locked};void deallocate(pointer __p, size_type){Slabs::I().Free(__p); // 调用 ncx_slab_free_locked};void construct(pointer __p, const _Tp };void destroy(pointer __p){ __p->~_Tp(); };size_type max_size() const{ return size_t(-①) / sizeof(_Tp); };}; template inline bool operator==(const SharedAllocator } template inline bool operator==(const SharedAllocator } template inline bool operator!=(const SharedAllocator } template inline bool operator!=(const SharedAllocator }