Wal*_*ter 6 c++ containers memory-management
我需要一些内存管理,并希望我可以将它建立在一些std容器上.我的要求是:
所以,我需要一些可以通过添加块来扩展的东西,比如std::deque.但是std::deque,我不能保证通过8个元素进行扩展会给我一个连续的块.而且std::deque没有,capacity所以我无法"适应" std::deque.
这意味着我必须自己写,对吗？(注意:我不想知道如何写我自己的,但只有我必须).
编辑澄清:只有在每次扩展时获得的元素块必须是连续的,而不是整个容器 - 这显然与其他要求相矛盾.
编辑为jalf所以这是什么:用于"排序"3D点的空间八度树.树节点指的是立方体单元,并形成与使用指针链接的父母和女儿的链接结构.同级节点未链接,但在内存中相邻.事先不知道节点的总数(因为每个最终节点的点数> 1),但是可以获得估计.在树构建期间,当划分非最终节点时,必须获得最多8个新节点的连续块,然后将其链接到树中.移动或复制这些节点会使任何现有链接(指针)无效.
另一个编辑只是为了澄清一些讨论.任何基于的设计都std::vector<T>不得使用resize()和/或reserve().两者都需要T在某些条件下复制或移动构造函数.即使从未在这些条件下调用过,代码也无法编译.
有一个捕获,std::vector是给你的.
它完全是连续的,不仅仅是块状的,而且可以扩展,保持连续(第2点).扩展可能意味着重新分配(因此无效的先前获得的指针/迭代器和移动),但如果您事先知道总大小(第3点),则可以reserve()不进行重新分配.
给出一个迭代i矢量的v,则可以得到由运行编号(位置)i - v.begin(); 类似地,给定指向p元素的指针,通过p - &v[0](点4).
捕获是你的观点1.有emplace_back(),但由于与异常安全相关的原因,std::vector仍然试图在某处暂时构建元素,然后将它们移动到永久位置.
假设你有这门课
struct A
{
A() { }
A(A&&) = delete;
A(const A&) = delete;
};
我可以看到两个解决方法:
派生另一个B默认构造的类而不是复制/移动构造:
struct B : A
{
B() : A() { }
B(B&&) : A() { }
B(const B&) : A() { }
};
如果你不能这样做,那么创建一个为你做这个的allocator对象:
template<typename T>
struct allocator : std::allocator<T>
{
using std::allocator<T>::allocator;
using std::allocator<T>::construct;
template<typename U>
void construct(U* p, U&&) { construct(p); }
template<typename U>
void construct(U* p, const U&) { construct(p); }
template<typename U>
struct rebind { using other = allocator<U>; };
};
template<>
struct allocator<void> : std::allocator<void> { };
两种情况的使用如下所示(实例):
template<typename C, size_t N = 100>
void test()
{
C c;
c.reserve(N);
for (size_t i = 0; i < N; ++i)
c.emplace_back();
}
int main ()
{
test<std::vector<B> >();
test<std::vector<A, allocator <A> > >();
}
请记住,通过这种方式仍然A可以构建然后丢弃的实例.这是使用的不幸后果std::vector.如果A足够小并且其默认构造没有任何奇怪的副作用,这应该不是问题.
如果你仍然需要超出最初的扩展reserve(),那么我建议使用这种向量的容器作为块.如果你仍然希望将这个元容器视为具有自己的迭代器的单个容器,那么相关的是我自己的join视图和它的迭代器只是为了一个想法,但这仍然是非常实验性的.我敢打赌Boost也有这个目的,但我不是那么熟悉.
简而言之，似乎没有一个标准容器可以完成这项工作，您必须编写自己的.
事实证明，这比我想象的要困难，因为指向生成对象的指针必须在内存管理器的生命周期内保持有效（在原始问题中通过对象不能移动或复制的请求来实现）的限制。std::vector::resize()这排除了和的使用std::vector::reserve()。设计sequence_container<std::vector<T>>仍然是可能的，但要么需要为每个新对象块创建另一个对象vector，要么预先构建整个对象块，然后将它们分发出去，直到块耗尽。
为了避免这种情况，似乎必须编写一些chunk类（以代替vector）并处理allocator问题。这是一个实现：
#include <list>
#include <memory>
template<typename type, typename allocator=std::allocator<type>,
template<typename,typename> class sequence_container = std::list>
class chunk_allocator
{
public:
using object = type;
using pointer = object*;
using size_type = std::size_t;
using alloc_traits = std::allocator_traits<allocator>;
private:
struct chunk
{
allocator alloc;
const pointer beg_data, end_capacity;
pointer end_data;
chunk(size_type cap, const allocator&all)
: alloc(all)
, beg_data(alloc_traits::allocate(alloc,cap))
, end_capacity(beg_data+cap)
, end_data(beg_data) {}
~chunk()
{
if(beg_data==nullptr) return;
for(; --end_data>=beg_data; --end_data)
alloc_traits::destroy(alloc,end_data);
alloc_traits::deallocate(alloc,beg_data,capacity());
}
size_type size() const noexcept { return end_data - beg_data; }
size_type capacity() const noexcept { return end_capacity - beg_data; }
pointer make(size_type n)
{
if(end_data + n > end_capacity)
return nullptr;
auto ptr = end_data;
for(; n; --n,++end_data)
alloc_traits::construct(alloc,end_data);
return ptr;
}
};
using chunk_alloc = typename alloc_traits::template rebind_alloc<chunk>;
using chunk_container = sequence_container<chunk,chunk_alloc>;
using chunk_iterator = typename chunk_container::iterator;
chunk_container chunks;
chunk_iterator last_chunk;
/// no default constructor
chunk_allocator() = delete;
/// no copy
chunk_allocator(chunk_allocator const&) = delete;
chunk_allocator&operator=(chunk_allocator const&) = delete;
public:
/// allow move
chunk_allocator(chunk_allocator&&) = default;
chunk_allocator&operator=(chunk_allocator&&) = default;
/// constructor
explicit
chunk_allocator(size_type initial_capacity, allocator const&alloc=allocator())
: chunks(alloc)
, last_chunk(chunks.emplace(chunks.end(),initial_capacity,alloc)) {}
/// invalid index
static constexpr size_type invalid = ~size_type(0);
/// find index for element, return invalid if not ours
size_type index(const object*ptr) const noexcept
{
size_type n=0;
for(auto c=chunks.begin(); c!=chunks.end(); ++c)
if(c->beg_data <= ptr && ptr < c->end_data)
return n + size_type(ptr-c->beg_data);
else
n += c->size();
return invalid;
}
/// obtain contiguous chunks of objects
/// \param[in] n \# objects in returned chunk
/// \param[in] chunk_size \# objects to allocate should we not have enough
/// \return pointer to first of n contiguous objects
object*create(const size_type n, size_type chunk_size=0)
{
if(n==0)
return nullptr;
if(last_chunk->end_data + n > last_chunk->end_capacity) {
if(chunk_size==0) chunk_size = last_chunk->capacity();
if(chunk_size< n) chunk_size = n;
last_chunk = chunks.emplace(chunks.end(),chunk_size,last_chunk->alloc);
}
return last_chunk->make(n);
}
};
// test
#include <iostream>
struct foo
{
int X;
static int C;
foo() : X(C++) { std::cout<<"foo::foo(): X="<<X<<std::endl; }
foo(foo const&) = delete;
foo&operator=(foo const&) = delete;
foo(foo &&) = delete;
foo&operator=(foo &&) = delete;
};
int foo::C=0;
int main()
{
std::cout<<" chunk_allocator<foo> C(3);"<<std::endl;
chunk_allocator<foo> C(3);
auto a = C.create(1);
std::cout<<" auto a=C.create(1)="<<a<<std::endl;
auto b = C.create(4);
std::cout<<" auto b=C.create(4)="<<b<<std::endl;
auto c = C.create(3);
std::cout<<" auto c=C.create(3)="<<c<<std::endl;
std::cout<<" a="<<a<<" a->X="<<a->X<<" index(a)="<<C.index(a)<<'\n'
<<" b="<<b<<" b->X="<<b->X<<" index(b)="<<C.index(b)<<'\n'
<<" c="<<c<<" c->X="<<c->X<<" index(c)="<<C.index(c)<<'\n';
}