Контейнер посоветуйте

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

Поиск чаще, но есть лимит (скажем 1000) элементов, после которого старые элементы удаляются, а новые добавляются в конец. Поэтому рост контейнера крайне нежелателен.

std::deque

std::deque посмотри

Подойдёт, думаю, спасибо.

std:deque

index-based access

Поиск чаще, но есть лимит (скажем 1000) элементов

можно и std:deque, если не жалко падения производительности в 1000 раз

судя по описанию, идеальная структура - массив Object x[LIMIT_HERE]; если лимит не абсолютный, а условный - std::vector.

при удалении элемента добавляешь его индекс в стек (хоть тот же std::vector), новые элементы добавляешь сначала по индексам из стека, а если стек пуст - то в конец массива.

Если порядок следования элементов не имеет значения, то std::vector<> будет быстрее всего:

std::vector<object> v;

// add elements to vector
v.push_back(obj);

//...

// remove in middle
const size_t size = v.size() - 1;
v[middle_idx] = v[size];
v.resize(size);

У вектора элементы лежат последовательно в памяти и поэтому итерация по ним получается быстрая (нет cache miss).