what standard container to pick (if any)?

Question

I need some memory management and was hoping I could base it on some std container. My requirements are:

1. elements have only a default constructor (no copy, no move, nothing else)
2. The container can be expanded (at the back) by a small contiguous block of elements
3. I even know roughly how many elements I will need in total, even better, at any time how many I will need eventually. These are estimates, though.
4. I don't really need an iterator, but a way to obtain the running number of an element would be handy.

So, I would need something that can be expanded by adding chunks, like std::deque. But with std::deque, I cannot guarantee that expansion by, say, 8 elements, gives me a contiguous block. And std::deque doesn't have capacity so I cannot 'adapt' from a std::deque.

This would mean that I have to write my own, correct? (note: I don't want to know how to write my own, but only if I have to).

Edit to clarify: only the blocks of elements obtained at each expansion has to be contiguous, but not the whole container -- that would obviously contradict with the other requirements.

Edit for jalf So what is this for: a spatial oct-tree for "sorting" 3D points. The tree nodes refer to cubic cells and form a linked structure with parents and daughters linked using pointers. Sibling nodes are not linked, but are adjacent in memory. The total number of nodes is not known in advance (because the number of points per final node >1), but an estimate can be obtained. During tree building, when dividing a non-final node, a contiguous chunk of up to 8 new nodes must be obtained and will then be linked into the tree. Moving or copying those nodes would invalidated any existing links (pointers) to them.

Another Edit Just to clarify some discussions. Any design that is based on std::vector<T> must not use resize() and/or reserve(). Both would require copy or move constructor of T under certain conditions. Even if never called under these conditions, the code won't compile.

Answer 1

With one catch, std::vector is for you.

It is entirely contiguous, not just in blocks, and can be expanded, remaining contiguous (point 2). Expansion may mean reallocation (therefore invalidation of previously obtained pointers/iterators, and moving), but if you know the total size in advance (point 3), you can reserve() so that no reallocation takes place.

Given an iterator i of vector v, you can obtain a running number (position) by i - v.begin(); similarly, given a pointer p to an element, by p - &v[0] (point 4).

The catch is your point 1. There is emplace_back(), but for reasons related exception safety, std::vector still attempts to temporarily construct elements somewhere and then move them to their permanent position.

Assuming you have this class

struct A
{
    A() { }
    A(A&&) = delete;
    A(const A&) = delete;
};

I can see two workarounds:

1. Derive another class B that default-constructs instead of copy/move-constructing:

   struct B : A
   {
       B() : A() { }
       B(B&&) : A() { }
       B(const B&) : A() { }
   };
   

2. If you can't do that, then make an allocator object that does this for you:

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

The use of both cases is illustrated below (live example):

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> > >();
}

Keep in mind that this way there are still instances of A that are constructed then thrown away. This is an unfortunate consequence of using std::vector. If A is small enough and its default-construction does not have any weird side-effects, this should not be a problem.

If you still need expansion beyond the initial reserve(), then I suggest a container of such vectors to be used as blocks. And if you still want to view this meta-container as a single container with its own iterator, then relevant is my own join view and its iterator just for an idea, but this is still very experimental. I bet there's something for this purpose in Boost as well, but I'm not so familiar.

Answer 2

I would advise simply using a std::deque<std::vector<T>> as a private data member of a custom class that ensures that:

• new elements are only added at the back
• the elements are added in chunks