Looking For C++ Stl-Like Vector Class But Using Stack Storage

Looking for C++ STL-like vector class but using stack storage

You don't have to write a completely new container class. You can stick with your STL containers, but change the second parameter of for example std::vector to give it your custom allocator which allocates from a stack-buffer. The chromium authors wrote an allocator just for this:

https://chromium.googlesource.com/chromium/chromium/+/master/base/stack_container.h

It works by allocating a buffer where you say how big it is. You create the container and call container.reserve(buffer_size);. If you overflow that size, the allocator will automatically get elements from the heap (since it is derived from std::allocator, it will in that case just use the facilities of the standard allocator). I haven't tried it, but it looks like it's from google so i think it's worth a try.

Usage is like this:

StackVector<int, 128> s;
s->push_back(42); // overloaded operator->
s->push_back(43);

// to get the real std::vector. 
StackVector<int, 128>::ContainerType & v = s.container();
std::cout << v[0] << " " << v[1] << std::endl;

Does the stack implementation that's part of the C++ STL have a capacity?

The stack implementation you looked at in your course may have had a limit, but that's not essential to being a stack. (And your course really should have taught you this.)

The C++ standard library stack is just an adapter for any underlying collection that supports the necessary operations, so whether it has a limited capacity or not depends on that underlying type.

(The default is std::deque.)

C++ class that can be put *only* on the stack?

The following class allows only: X&& x = X::MakeInstance(); or const X& x = X::MakeInstance(); usages:

class X
{
public:
    X(const X&) = delete;
    X(X&&) = delete;
    X& operator =(const X&) = delete;
    X& operator =(X&&) = delete;

public:
    static X MakeInstance() { return {}; }

    static void* operator new     (size_t) = delete;
    static void* operator new[]   (size_t) = delete;
    static void  operator delete  (void*)  = delete;
    static void  operator delete[](void*)  = delete;

private:
    X() = default;
};

STL-like vector with arbitrary index range

Deque is very much like a vector in that it supports random access and efficient insertion at the end and it also supports efficient insertion at the beginning.

Map supports access based on arbitrary keys, you can have any range you want, or even a sparsely populated array. Iteration over the collection is slow.

Unordered map (tr1) is similar to map except it supports better iteration.

As a general rule of thumb, use a vector (in your case adapt it to the behaviour you want) and only change when you have evidence that the vector is causing slowness.

stl container of vectors of object c++

The container you are looking for is std::vector.

I was thinking about std::list because those vectors are changing theirs size, so there is a lot of reallocation.

A std::vector does not change its size when you add elements. std::vector::size() returns the number of elements, but sizeof(some_vector) is constant. A extremely simplified model of std::vector that should be sufficient to understand why is:

template <typename T>
struct fake_vector {
    T* data;
    // ... other stuff ...
};

It doesn't matter if data points to an array with 10 elements, 42, or 10000 elements, the size of the vector object is always the same.

In general instances of a given type always have the same size. Thats why you can have arrays of objects.

For the last part of the question you would need to show a complete example, but with a vector of vectors, that method would simply be:

std::vector<object>& getByIndex(size_t index)
{ 
    return data[index];
}

Often a flat std::vector<T> is better than a std::vector<std::vector<T>> because the big plus of std::vector is its data locality (elements are stored in contiguous memory), and because a std::vector adds a level of indirection this data locality is lost in nested vectors (only the inner vectors elements are stored in contiguous memory). However, if you are only working on the inner vectors, then that may not be a real disadvantage.

Is it safe to assume that STL vector storage is always contiguous?

Yes, that is a valid assumption (*).

From the C++03 standard (23.2.4.1):

The elements of a vector are stored
contiguously, meaning that if v is a
vector where T is some
type other than bool, then it obeys
the identity &v[n] == &v[0] + n for
all 0 <= n < v.size().

(*) ... but watch out for the array being reallocated (invalidating any pointers and iterators) after adding elements to it.

Why do we need stacks when we already have vectors which are even more powerful?

Why do we need for loops and while loops when we already have goto which is even more powerful? You should adhere to the principle of parsimony - use the least powerful tool that is powerful enough to achieve the desired objective.

If what you need is a stack, take a dependency on the standard library class that provides that functionality, not a more powerful one. It also communicates better to a person reading your code, what you are going to do.

c++ Vector, what happens whenever it expands/reallocate on stack?

You wrote

[...] copy itself to a new location [...]

which is not the way a vector works. The vector data is copied to a new location, not the vector itself.

My answer should give you an idea of how a vector is designed.

The common std::vector layout*

Note: The std::allocator is actually likely to be an empty class and std::vector will probably not contain an instance of this class. This may not be true for an arbitrary allocator.

In most implementations it consists of three pointers where

• begin points to the start of the data memory of the vector on the heap (always on the heap if not nullptr)
• end points one memory location past the last element of the vector data
  -> size() == end-begin
• capacity points on memory location past the last element of the vector memory -> capacity() == capacity-begin

A vector on the stack

We declare a variable of type std::vector<T,A> where T is any type and A is an allocator type for T (i.e. std::allocator<T>).

std::vector<T, A> vect1;

How does this look like in memory?

As we see: Nothing happens on the heap but the variable occupies the memory that is necessary for all of its members on the stack.
There it is and it will stay there until vect1 goes out of scope, since vect1 is just an object like any other object of type double, int or whatever. It will sit there on its stack position and wait to get destroyed, regardless of how much memory it handles itself on the heap.

The pointers of vect1 do not point anywhere, since the vector is empty.

A vector on the heap

Now we need a pointer to a vector and use some dynamic heap allocation to create the vector.

std::vector<T, A> * vp = new std::vector<T, A>;

Let's again look at the memory.

We have our vp variable on the stack and our vector is on the heap now. Again the vector itself will not move on the heap since its size is constant. Only the pointers (begin, end, capacity) will move to follow the data position in memory if a reallocation takes place. Let's have a look at that.

Pushing elements to a vector

Now we can start pushing elements to a vector. Let's look at vect1.

T a;
vect1.push_back(a);

The variable vect1 is still where it has been but memory on the heap was allocated to contain one element of T.

What happens if we add one further element?

vect1.push_back(a);

• The space allocated on the heap for the data elements will not be enough (since it is only one memory positions, yet).
• A new memory block will be allocated for two elements
• The first element will be copied/moved to the new storage.
• The old memory will be deallocated.

We see: The new memory location is different.

To have additional insight let's look at the situation if we destroy the last element.

vect1.pop_back();

The memory allocated won't change but the last element will have its destructor called and the end pointer moves one position down.

As you can see: capacity() == capacity-begin == 2 while size() == end-begin == 1

Is there some STL container for one element on the heap?

You are possibly looking for what is called deep/clone/copy/value pointer (basically a unique pointer with deep copy capabilities). There was even a proposal, don't know its actual status: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3339.pdf.

AFAIK, it has not been accepted up to now. Maybe, some external library provides it (Boost?).

Relevant question: Is there a scoped ptr that has deep copy functionality built in? In its accepted answer, there is a link to some library, which should provide the required functionality. It doesn't seem to be any more maintained, but maybe it is still usable.

You can google for some more solutions. For instance, you can copy-paste (and possibly review) this implementation: https://vorbrodt.blog/2021/04/05/stddeep_ptr/.

I believe you can find some solutions on Code Reivew site as well, such as: DeepPtr: a deep-copying unique_ptr wrapper in C++. I think it's a good idea to employ std::unique_ptr and just wrap it with the deep-copy functionality.

---

Related Topics