Is there an equivalent of vector::reserve() for an std::list?
c++, list, stl, vector
Solution
I think you are using wrong the container.
If you want fast push back then don't automatically assume that you need a linked list, a linked list is a slow container, it is basically suitable for reordering.
A better container is a std::deque. A deque is basically a array of arrays. It allocates a block of memory and occupies it when you push back, when it runs out it will allocate another block. This means that it only allocates very infrequently and you do not have to know the size of the container ahead of time for efficiency like std::vector and `reserver`.
Problem
I have a class that looks like this: ``` typedef std::list<char*> PtrList; class Foo { public: void DoStuff(); private: PtrList m_list; PtrList::iterator m_it; }; ``` The function `DoStuff()` basically adds elements to `m_list` or erases elements from it, finds an iterator to some special element in it and stores it in `m_it`. It is important to note that each value of `m_it` is used in every following call of `DoStuff()`. So what's the problem? Everything works, except that profiling shows that the operator `new` is invoked too much due to `list::push_back()` called from `DoStuff()`. To increase performance I want to preallocate memory for `m_list` in the initialization of `Foo` as I would do if it were an `std::vector`. The problem is that this would introduce new problems such as: - Less efficient `insert` and `erase` of elements. - `m_it` becomes invalid as soon as the vector is changed from one call to `DoStuff()` to the next. EDIT: Alan Stokes suggested to use an index instead of an iterator, solving this issue. My solution: the simplest solution I could think of is to implement a pool of objects that also has a linked-list functionality. This way I get a linked list and can preallocate memory for it. Am I missing something or is it really the simplest solution? I'd rather not "re-invent the wheel", and use a standard solution instead, if it exists. Any thoughts, workarounds or enlightening comments would be appreciated!