What's the suited container to push values on top, remove at whatever index and avoid memory reallocation?

Question

I need to build a sort of stack where I can push values on top:

5      // (size 1)
5 3    // (size 2)
5 3 8  // (size 3)

than remove them by value, such as removing 3:

5 8    // (size 2)

than be able to always get the last value (i.e. 8 in the example), when I need it).

I can push max 32 values, so I know the whole size (avoiding heap?).

I think to std::vector with:

• initial reserve(32)
• .push_back() for insert
• vector.erase(std::remove(vector.begin(), vector.end(), value), vector.end()) for remove by value
• vector[vector.size() - 1] to retrieve the last element

But maybe there are some stl container better for this kind of process? Not sure if vector are always in the stack and will do further memory reallocation under the hood...

Answer 1

You can write an allocator that contains your 32 values, and refuses to allocate any amount other than 32

template <typename T, std::size_t N = 32>
struct static_allocator 
{
    T* allocate(std::size_t n) { if (n != N) throw std::bad_alloc(); return arr; }
    void deallocate(T *, std::size_t) {}

    using pointer = T*;
    using const_pointer = const T*;
    using void_pointer = void*;
    using const_void_pointer = const void*;

    using value_type = T;
    using size_type = std::size_t;
    using difference_type = std::ptrdiff_t;

    template <typename U>
    struct rebind
    {
         using other = static_allocator<U, N>;
    };

    static_allocator select_on_container_copy_construction() { return {}; }
    using propagate_on_container_copy_assignment = std::true_type;
    using propagate_on_container_move_assignment = std::true_type;
    using propagate_on_container_swap = std::true_type;
private:
    T arr[N];
};

Then a std::vector<T, static_allocator<T>> will have it's elements as subobjects.

I don't think it's possible to avoid dynamic allocation and have sublinear random-access remove.

Answer 2

if size is limited to 32 elements why not use a circular buffer of 32 elements, and roll the elements when they are 32 ? There may be some bugs (don't use last() or remove () on an empty container, don't remove an element not inserted...) ,but it works for the functions you wanted. Here is the idea (heap is avoided)

#include <iostream>

template <typename T>
class Container {
public :
  static const int smax_ = 32;
  void erase () {
    T* pt ((T*) val_);
    for (int i (0); i != smax_; ++i, ++pt) *pt = 0; 
    size_ = 0;
  }
  Container () : size_ (0) { erase ();}
  ~Container () {}
  void copy (const Container& c)  {
    size_ = c.size_;
    T* pt ((T*) val_);
    const T* qt ((const T*) c.val_);
    for (int i (0); i != size_; ++i, ++pt, ++qt) *pt++ = *qt++; 
  }
  Container (const Container& c) {
    copy (c);
  }
  void push_back (const T& t) {
    if (size_ == smax_) {
      T* pt ((T*) val_);
      const T* qt ((const T*) val_);
      ++qt;
      for (int i (0); i != size_ -1; ++i, ++pt, ++qt) {
        *pt = *qt;
      }
      *pt = t;
    }
    else {
      val_ [size_] = t;
      ++size_;
    }
  }
  int size () const {
    return size_;
  }
  void remove (const T& t) {
    if (!size_) return;
    int i (0);
    T* pt ((T*)val_);
    while ((i < smax_) && (*pt != t)) {
      ++pt; ++i;
    }
    if (i != smax_) {
      T* qt (pt);
      ++qt;
      for (; i != size_ -1; ++i, ++pt, ++qt) {
        *pt = *qt;
      }
    }
    --size_;
  }
  void write (std::ostream& os) const {
    const T* pt ((const T*) val_);
    for (int i (0); i != size_; ++i, ++pt) os << *pt << "  ";
  }
  bool operator == (const Container& c) const {
    if (size_ != c.size_) return false;
    const T* pt ((const T*) val_), *qt ((const T*) c.val_);
    for (int i (0); i != size_; ++i, ++pt, ++qt) if (*pt != *qt) return false;
    return true;
  }
  bool operator != (const Container& c) const {
    return !operator == (c);
  }
  T& operator = (const Container& c) {
    copy (c);
    return *this;
  }
  T last () const {
    return val_ [size_ -1];
  }
  T val_ [smax_];
  int size_;
};

Test Program

int main (int argc, char* argv []) {
  Container<int> c;
  std::cout << "pushing back 5..." << std::endl;
  c.push_back (5);
  c.write (std::cout);
  std::cout << std::endl;
  std::cout << "c.last == " << c.last () << std::endl;

  std::cout << "pushing back 3..." << std::endl;
  c.push_back (3);
  c.write (std::cout);
  std::cout << std::endl;
  std::cout << "c.last == " << c.last () << std::endl;

  std::cout << "pushing back 8..." << std::endl;
  c.push_back (8);
  c.write (std::cout);
  std::cout << std::endl;
  std::cout << "c.last == " << c.last () << std::endl;

  std::cout << "erasing 3..." << std::endl;
  c.remove (3);
  c.write (std::cout);
  std::cout << std::endl;
  std::cout << "c.last == " << c.last () << std::endl;  
}

and the results :

pushing back 5...
5  
c.last == 5
pushing back 3...
5  3  
c.last == 3
pushing back 8...
5  3  8  
c.last == 8
erasing 3...
5  8  
c.last == 8

Answer 3

if you dont want memory reallocation then you can also use list container i.e linked list ..as it has mostly same properties to the vector..just it do not support random access or []operator ...else vector is perfect:)