Vector-like container that can have instances with storages mutually contiguous?

Question

I need a container class with API as close as possible to std::vector (except no reallocation), but whose elements' storage (and not its member variables such as size) can be specified to be allocated from an existing buffer, so that I can have all vectors' held elements in a contiguous buffer. That is, .end() of one vector points to the same element in the buffer as .front() of the next.

I don't know whether I can simply use a custom allocator with std::vector, because I can't find information on whether that allocates storage for the whole class including the size and pointer data members (in which case I can't use this approach), or just the data elements it holds (in which case I can use it).

I only need an instance's storage to be allocated once, so there's no issue with reallocation. I'm posting here to see if there's already such a container published, rather than reimplementing most of the std vector interface with iterators etc. from scratch.

---

Update: I unchecked the answer that was posted because it doesn't work in debug mode in Visual C++ 2012. Example with T = float:

template<class T>
inline typename ContigAlloc<T>::pointer ContigAlloc<T>::allocate(std::size_t n)
{
    std::cout << "Alloc " << n << "; type match: " << std::boolalpha << std::is_same<T, float>::value << std::endl;
    return reinterpret_cast<T *>(_buff.alloc(T * sizeof(n)));
}

template<class T>
inline void ContigAlloc<T>::deallocate(T *p, std::size_t n) // TODO: noexcept when VC++2013
{
    std::cout << "Deall " << n << "; type match: " << std::boolalpha << std::is_same<T, float>::value << std::endl;
    _buff.dealloc(p, T * sizeof(n));
}

Test:

std::vector<float, ContigAlloc<float>> vec;
vec.push_back(1.1f);
vec.push_back(1.9f);

Result in Release build is fine:

Alloc 1; type match: true
Alloc 2; type match: true
Deall 1; type match: true
Deall 2; type match: true

Result in Debug build is not fine:

Alloc 1; type match: false
Alloc 1; type match: true
Alloc 2; type match: true
Deall 1; type match: true
Deall 2; type match: true
Deall 1; type match: false

In the first call to allocate(), T = _Container_proxy

Answer 1

An allocator is used only to allocate storage for the elements. You can use a custom allocator for this purpose.

I stand corrected by Jon in the comments below.

I think one could implement a conforming vector such that it stored everything on the heap except a pointer. The things on the heap would be either 3 pointers, plus the allocator (if not allocator is not optimized away), or 1 pointer, the size, and the capacity (and the possibly optimized away allocator).

In practice, every single implementation of std::vector that has ever shipped in any kind of volume, including:

• HP
• SGI
• libstdc++ (gcc)
• libc++ (llvm)
• Dinkumware
• Microsoft
• Rogue Wave
• CodeWarrior
• STLPort
• I'm sure I'm forgetting some others...

has placed all of the supporting members within the vector class itself, and used the allocator only for allocating the data. And there seems to be little motivation to do otherwise.

So this is a de facto standard, not an official one. With the history above, it is a pretty safe one.

Note that one could not make the same claim for string, which conceptually has an identical layout. C++11 implementations of string will typically use a "short string" optimization where the allocator is not used at all for "short" strings, but rather the value is embedded within the string class. This optimization is effectively forbidden for vector by 23.2.1 General container requirements [container.requirements.general]/10:

(Unless otherwise specified) no swap() function invalidates any references, pointers, or iterators referring to the elements of the containers being swapped.

Answer 2

If I understand your question correctly, you are using vectors of fixed size. If these sizes and the number of the vectors are compile time constants, I would suggest using std::array.

EDIT: Just to clarify what I mean, here an example:

struct Memory {
    std::array<int, 2> a1; 
    std::array<int, 2> a2;
} memory; 


int main() {         
    std::array<int, 2>& a1 = memory.a1;
    std::array<int, 2>& a2 = memory.a2; 

    a1[0] = 10; 
    a1[1] = 11;  
    a2[0] = 20;
    a2[1] = 21;  

    int *it=&(a1[0]); 

    for (size_t i = 0; i < 4; ++i){
        std::cout << *(it++) << ",";
    }
}

Output: 10,11,20,21, Depending on your requirements, you can also implement Memory as a singleton. Of course it's just a guess from my side, whether this matches your current usage pattern.