Использование deque: производительность в порядке.
Стандарт гласит: «deque - это выбранная структура данных, когда большинство вставок и удалений происходит в начале или в конце последовательности» (23.1.1). В вашем случае все вставки и удаления выполняются в конце, удовлетворяя критерию для использования deque.
http://www.gotw.ca/gotw/054.htm содержит некоторые подсказки о том, как вы можете измерить производительность, хотя, по-видимому, вы имеете в виду конкретный вариант использования, поэтому вам следует это измерить.
Редактировать: ОК, если ваше возражение против deque на самом деле не "Я не уверен, насколько быстрым является deque", но "тип элемента не может быть элементом в стандартном контейнере", тогда мы может исключить любой стандартный контейнер. Нет, такого зверя не существует. deque "никогда не копирует элементы", но создает и копирует их из других объектов.
Следующим лучшим вариантом, вероятно, является создание массивов элементов, созданных по умолчанию, и поддержка контейнера указателей на эти элементы. Что-то в этом роде, хотя это, вероятно, можно значительно изменить.
template <typename T>
struct C {
vector<shared_array<T> > blocks;
vector<T*> elements; // lazy, to avoid needing deque-style iterators through the blocks.
T &operator[](size_t idx) { return *elements[idx]; }
void resize(size_t n) {
if (n <= elements.size()) { /* exercise for the reader */ }
else {
boost::shared_array<T> newblock(new T[elements.size() - n]);
blocks.push_back(newblock);
size_t old = elements.size();
// currently we "leak" newblock on an exception: see below
elements.resize(n);
for (int i = old; j < n; ++i) {
elements[i] = &newblock[i - old];
}
}
void clear() {
blocks.clear();
elements.clear();
}
};
Когда вы добавляете больше функций и операторов, он приближается к deque, но избегает всего, что требует копирования типа T.
Редактировать: если подумать, мое «упражнение для читателя» не может быть выполнено совершенно правильно в тех случаях, когда кто-то делает resize(10); resize(20); resize(15);. Вы не можете наполовину удалить массив. Поэтому, если вы хотите правильно воспроизвести семантику контейнера resize(), немедленно уничтожив лишние элементы, вам придется выделить элементы индивидуально (или познакомиться с новым размещением):
template <typename T>
struct C {
deque<shared_ptr<T> > elements; // or boost::ptr_deque, or a vector.
T &operator[](size_t idx) { return *elements[idx]; }
void resize(size_t n) {
size_t oldsize = elements.size();
elements.resize(n);
if (n > oldsize) {
try {
for (size_t i = oldsize; i < n; ++i) {
elements[i] = shared_ptr<T>(new T());
}
} catch(...) {
// closest we can get to strong exception guarantee, since
// by definition we can't do anything copy-and-swap-like
elements.resize(oldsize);
throw;
}
}
}
void clear() {
elements.clear();
}
};
Хороший код, не особо увлекающийся шаблонами доступа к памяти (но тогда я не уверен, является ли производительность проблемой или нет, так как вы беспокоились о скорости deque.)