а в стд есть вообще контейнер, который работает как вектор, но при удалении элемента не сдвигает данные, а просто помнит что тут пусто, и следующую вставку сделает в это место
типа как список тока без постоянных выделений/удалений памяти

Здравствуйте, Kingofastellarwar, Вы писали:

K>а в стд есть вообще контейнер, который работает как вектор, но при удалении элемента не сдвигает данные, а просто помнит что тут пусто, и следующую вставку сделает в это место
K>типа как список тока без постоянных выделений/удалений памяти

Так делает менеджер памяти.

Здравствуйте, Kingofastellarwar, Вы писали:

K>а в стд есть вообще контейнер, который работает как вектор, но при удалении элемента не сдвигает данные, а просто помнит что тут пусто, и следующую вставку сделает в это место

Характерной особенностью массивов (и вектора) является хранение всех элементов непрерывно друг за другом в одном блоке памяти.
Дырок в нем быть не может.

K>типа как список тока без постоянных выделений/удалений памяти

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

K>а в стд есть вообще контейнер, который работает как вектор, но при удалении элемента не сдвигает данные, а просто помнит что тут пусто, и следующую вставку сделает в это место
K>типа как список тока без постоянных выделений/удалений памяти
Можно использовать хеш-таблицу.

если порядок не важет то для скорости можно переносить последний элемент на место удаленного, и удалять последний

Здравствуйте, Wawan, Вы писали:

W>... и удалять последний
можен не надо?
не лучше ли просто сдвигать указатель конца?

Здравствуйте, Kingofastellarwar, Вы писали:

K>а в стд есть вообще контейнер, который работает как вектор, но при удалении элемента не сдвигает данные, а просто помнит что тут пусто, и следующую вставку сделает в это место

А какие операции вообще требуются? index-access? обход всех живых?

K>типа как список тока без постоянных выделений/удалений памяти

Степанов рассказывал что он именно таким и хотел сделать изначальный list, и далее показывает пример реализации list_pool — как раз несколько списков поверх одного вектора.

Можно взять обычный std::list, точнее два — в одном будут живые элементы, а во втором пустые/мёртвые. Когда нужен новый — делаешь std::list::splice для переноса узла из одного списка в другой.
Чтобы не было постоянных выделений памяти (при нехватке пустых узлов) — предварительно заполни список-донор нужным количеством пустых элементов. Но естественно решение на базе vector'а было бы лучше.

Можно взять Boost.Pool — там внутри ЕМНИП есть реализация на базе массивов+freelist — его можно комбинировать со std::list, либо использовать напрямую.

Здравствуйте, Kingofastellarwar, Вы писали:

K>а в стд есть вообще контейнер, который работает как вектор, но при удалении элемента не сдвигает данные, а просто помнит что тут пусто, и следующую вставку сделает в это место
K>типа как список тока без постоянных выделений/удалений памяти

Если дорогая операция именно сдвига элементов, то делается на коленке: вектор данных (самодельная куча), и вектор индексов и вакансий.

std::vector<T> items;
std::vector<size_t> indices;  // indices.size() == items.size()
size_t count;  // indices[0..count) - данные, indices[count..indices.size()) - вакансии

T& at(size_t i) {
  assert(i < count);
  return items[indices[i]];
}

void erase(size_t i) {
  assert(i < count);
  // переносим индекс освободившегося элемента в зону вакансий, сдвигая всё влево
  std::rotate(indices.begin()+i, indices.begin()+i+1, indices.begin()+count);
  // уменьшаем количество элементов
  --count;
}

void insert(size_t i, T&& t) {
  // заполняем вакансию
  if (count == indices.size()) {  // или создаём и тут же заполняем
    items.push_back(t);
    indices.push_back(count);
  } else {
    items[indices[count]] = t;  // вот так выглядит постусловие этого шага
  }
  // увеличиваем количество элементов
  ++count;
  // переносим индекс добавленного элемента в точку вставки - сдвигаем всё вправо
  std::rotate(indices.rend()-i-1, indices.rend()-i-2, indices.rend()-count-1);
}

(писал слёту, не тестировал, — если накосячил в ±1, простите).

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

Здравствуйте, Кодт, Вы писали:

К>

К>T& at(size_t i) {
К>  assert(i < count);
К>  return items[indices[i]];
К>}
К>

Непонятно что именно нужно ТС — ибо в сабже "unordered", а видимо значит можно обойтись без дорогой items[indices[i]]. Может ему нужен просто список под которым пул узлов в векторе, а может даже и список не нужен, а просто быстрые allocate/deallocate для фиксированного размера.

Здравствуйте, niXman, Вы писали:

X>Здравствуйте, Wawan, Вы писали:

W>>... и удалять последний
X>можен не надо?
X>не лучше ли просто сдвигать указатель конца?
деструктор элемента вызывать надожеж