Is there a QList type datastructure in STL or Boost?

just a brief QList intro, QList is similar to QVector and STL vector but in addition it also reserves some space at the beginning; (and in the end too) I am looking for something similar in STL , if not atleast Boost

Reserving space at the beginning improves prepending or removing the first item (constant time), because the buffer can grow backwards. Insertion is improved depending on开发者_如何学运维 the position of insertion. So does anyone know of a similar data structure in STL/C++?? Thanks.

std::deque provides front and back insertion removal at constant time, if it is what you are looking for.

If you want efficient insertion and removal at the beginning and end of a sequence, use a std::deque.

If you know an upper limit on container size and don't plan on mid-container inserts you could use boost::circular_buffer.

If you are doing a lot of mid-container inserts deque would be the a better choice than vector since it (typically) groups members into fixed-size blocks, rather than one contiguous block of memory.

Note - QList actually states that it uses an array of pointers to objects, if they are non-trivial. To simulate this in C++, you would use deque<MyClass*> or (better) some smart pointer wrapper on MyClass such as unique_ptr or shared_ptr, to prevent excessive copying of MyClass in housekeeping.

Internally, QList is represented as an array of pointers to items of type T. If T is itself a pointer type or a basic type that is no larger than a pointer, or if T is one of Qt's shared classes, then QList stores the items directly in the pointer array. For lists under a thousand items, this array representation allows for very fast insertions in the middle, and it allows index-based access.