Какой контейнер следует использовать для произвольного доступа, дешевого добавления и удаления (без деления/распределения) с известным максимальным размером?

Ответ 1

Как я понимаю, у вас есть две операции

Вставить/заменить элемент значение в ячейке index
Удалить элемент в ячейке index

и один предикат

Является ли ячейка index занятой в данный момент?

Это массив и растровое изображение. Когда вы вставляете/заменяете, вы вставляете значение в ячейку массива и устанавливаете бит битмарта. Когда вы удаляете, вы очищаете битмад-бит. Когда вы спрашиваете, вы запрашиваете битмад-бит.

Ответ 2

Вы можете просто использовать std::vector<int> и сделать vector.reserve(128);, чтобы вектор не выделял память. Это не позволяет вам отслеживать конкретные индексы.

Если вам нужно отслеживать "индекс", вы можете использовать std::vector<std::pair<int, int>>. Это не позволяет использовать произвольный доступ.

Ответ 3

Если вам нужны только дешевые значения настроек и стирания, просто используйте массив. Вы может отслеживать, какие ячейки используются, маркируя их в другом массиве (или растровом изображении). Или просто определяя одно значение (например, 0 или -1) как "неиспользуемое" значение.

Конечно, если вам нужно перебирать все используемые ячейки, вам нужно отсканировать весь массив. Но это компромисс, который вам нужно сделать: либо делать больше работы при добавлении и стирании, либо делать больше работы во время поиска. (Обратите внимание, что .insert() в середине vector<> будет перемещать данные вокруг.)

В любом случае, 128 элементов так мало, что сканирование по всему массиву будет незначительным. И, честно говоря, я думаю, что все более сложное, чем vector, будет полным излишеством.:)

Грубо:

unsigned data[128] = {0}; // initialize
unsigned used[128] = {0};
data[index] = newvalue; used[index] = 1; // set value
data[index] = used[index] = 0;           // unset value
// check if a cell is used and do something 
if (used[index]) { do something } else { do something else } 

Ответ 4

Я бы предложил тандем векторов, один для хранения активных индексов, другой - для хранения данных:

class Container
{
  std::vector<size_t> indices;
  std::vector<int> data;

  size_t index_worldToData(size_t worldIndex) const
  {
    auto it = std::lower_bound(begin(indices), end(indices), worldIndex);
    return it - begin(indices);
  }

public:
  Container()
  {
    indices.reserve(128);
    data.reserve(128);
  }

  int& operator[] (size_t worldIndex)
  {
    return data[index_worldToData(worldIndex)];
  }

  void addElement(size_t worldIndex, int element)
  {
    auto dataIndex = index_worldToData(worldIndex);
    indices.insert(it, worldIndex);
    data.insert(begin(data) + dataIndex, element);
  }

  void removeElement(size_t worldIndex)
  {
    auto dataIndex = index_worldToData(worldIndex);
    indices.erase(begin(indices) + dataIndex);
    data.erase(begin(indices) + dataIndex);
  }

  class iterator
  {
    Container *cnt;
    size_t dataIndex;

  public:
    int& operator* () const { return cnt.data[dataIndex]; }
    iterator& operator++ () { ++dataIndex; }
  };

  iterator begin() { return iterator{ this, 0 }; }
  iterator end() { return iterator{ this, indices.size() }; }
};

(Отказ от ответственности: код не тронут компилятором, проверки предпосылок опущены)

У этого есть логарифмический доступ к временному элементу, линейная вставка и удаление времени и позволяет выполнять итерацию по непустым элементам.

Ответ 5

Вы можете использовать двусвязный список и массив указателей node. Предварительно выделите 128 узлов списка и сохраните их на freelist. Создайте пустой itemlist. Выделите массив из 128 указателей node, называемых items

• Вставить в i: повернуть голову node с freelist, добавить его в itemlist, установите items[i], чтобы указать на него.
• Чтобы получить доступ/изменить значение, используйте items[i]->value
• Чтобы удалить в i, удалите node, на который указывает items[i], вставьте его в 'freelist'
• Чтобы продолжить, просто ходите itemlist

Все O (1), кроме итерации, которая является O (N _{active_items}). Только оговорка заключается в том, что итерация не находится в порядке индекса.

Freelist может быть односвязным или даже массивом узлов, поскольку все, что вам нужно, это pop и push.

Ответ 6

class Container {
  private:
    set<size_t> indices;
    unsigned int buffer[128];
  public:
    void set_elem(const size_t index, const unsigned int element) {
      buffer[index] = element;
      indices.insert(index);
    }
    // and so on -- iterate over the indices if necessary
};

Ответ 7

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

Наиболее доступным решением является использование нестандартных контейнеров Boost , представляющих особый интерес flat_map. По существу, flat_map предлагает интерфейс map по хранению, предоставляемому динамическим массивом.

Вы можете вызвать его reserve в начале, чтобы избежать выделения памяти.

Несколько более активное решение состоит в том, чтобы закодировать свой собственный распределитель памяти.

Интерфейс allocator относительно прост в обращении, так что кодирование распределителя довольно просто. Создайте пул-распределитель, который никогда не выпустит какой-либо элемент, не разогревает (выделяет 128 элементов), и вы готовы к работе: его можно подключить в любую коллекцию, чтобы сделать его свободным от размещения.

Особый интерес здесь, конечно, std::map.

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

Тем не менее, если у вас есть время или вы можете жить только подмножеством этих операций, то у этой дороги есть одно неоспоримое преимущество: вы можете адаптировать контейнер именно к вашим потребностям.

Особый интерес представляет идея иметь std::vector<boost::optional<int>> из 128 элементов... за исключением того, что, поскольку это представление довольно неэффективно, мы используем Data-Oriented Design, чтобы вместо этого сделать два вектора: std::vector<int> и std::vector<bool>, который является гораздо более компактным или даже...

struct Container {
    size_t const Size = 128;

    int array[Size];
    std::bitset<Size> marker;
}

который является компактным и не требует выделения.

Теперь итерация требует итерации битового набора для существующих элементов, что может показаться расточительным вначале, но указанный битсет имеет длину всего 16 байтов, так что это бриз! (потому что в таком масштабе область памяти превосходит сложность большого О)

Ответ 8

Почему бы не использовать std::map<int, int>, он обеспечивает произвольный доступ и разрежен.

Ответ 9

Если a vector (предварительно зарезервированное) недостаточно удобно, загляните в Boost.Container для различных "плоских" разновидностей индексированных коллекций. Это будет хранить все в векторе и не требует манипуляции с памятью, но добавляет слой сверху, чтобы сделать его набором или картой, индексируемым, по которым присутствуют элементы, и может сказать, что нет.