Какой контейнер подходит для значений pu sh сверху, удаления по любому индексу и избежания перераспределения памяти?

Question

Мне нужно создать своего рода стек, в котором я смогу выложить до sh значений сверху:

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

, чем удалить их по значению, например, удалить 3:

5 8    // (size 2)

чем всегда можно получить последнее значение (т.е. 8 в примере), когда мне это нужно).

Я могу высказать sh макс. 32 значения, поэтому я знаю весь размер (избегая кучи? ).

Я думаю std::vector с:

• начальный резерв (32)
• .push_back () для вставки
• вектора. стереть (std :: remove (vector.begin (), vector.end (), value), vector.end ()) для удаления по значению
• vector [vector.size () - 1] для получения последний элемент

Но, может быть, есть какой-нибудь контейнер stl лучше для такого рода процессов? Не уверен, что вектор всегда находится в стеке и будет делать дальнейшее перераспределение памяти под капотом ...

Answer 1

Вы можете написать распределитель, который содержит ваши 32 значения и отказывается выделять любую сумму, кроме 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];
};

Тогда std::vector<T, static_allocator<T>> будет иметь свои элементы в качестве подобъектов.

Я не думаю, что можно избежать динамического выделения c и удалить сублинейный произвольный доступ.

Answer 2

, если размер ограничен 32 элементами, почему бы не использовать круговой буфер из 32 элементов, а свернуть элементы, когда их 32? Могут быть некоторые ошибки (не используйте last () или remove () в пустом контейнере, не удаляйте элемент, не вставленный ...), но он работает для тех функций, которые вы хотели. Вот идея (куча избегается)

#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_;
};

Тестовая программа

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

и результаты:

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

если вы не хотите перераспределять память, то вы также можете использовать контейнер списка, то есть связанный список ... так как он имеет в основном те же свойства, что и вектор ... просто он не поддерживает произвольный доступ или оператор [] ... иначе вектор идеален :)