Re: [glob2-devel] question about std::list

[Kai Antweiler]

> vector is better when you need random access, and are adding/removing
> relativly few times. A memory conservative implementation has to
> reallocate for every add/remove, which can get costly quickly.

Depends:  Adding and at the end has amortized constant time complexity.
That is very efficient.  Removing at the end takes constant in time.


> Most
> optimized implementations allocate more than nesseccarry, for this
> reason. Thats also why they have std::vector::reserve.

That gives an additional speedup - theoretically up to a factor of 2.
But this won't help when adding or removing in the middle or the beginning.


> queue is based on a different container (provided as a template
> argument, defaults usually to std::list) so is no better than using
> std::list or std::deque. Its more of a facade.

No. Queue is implemented by default as a deque which is implemented as an
array.  You can assume it when you read:

http://www.sgi.com/tech/stl/Deque.html

 All of deque's members are defined in the Random access container,
Front insertion
 sequence, and Back insertion sequence requirements.

(lists are no Random access containers)

 Inserting an element at the beginning or end of a deque takes
amortized constant time.
 Inserting an element in the middle is linear in n

(list have "real" constant time in both cases)


Also:
http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/stl__deque_8h-source.html

00562    *  Here's how a deque<Tp> manages memory.  Each deque has 4 members:
00563    *
00564    *  - Tp**        _M_map
00565    *  - size_t      _M_map_size
00566    *  - iterator    _M_start, _M_finish
00567    *
00568    *  map_size is at least 8.  %map is an array of map_size
00569    *  pointers-to-"nodes".  (The name %map has nothing to do with the
00570    *  std::map class, and "nodes" should not be confused with
00571    *  std::list's usage of "node".)



> list is probably the best when you add/remove allot but only iterate
> in forward/backward direction.

Depends on where you add remove.  Vectors use the cache better.

When you only do this at the back: use vector
When you do this at the front and the back: use deque
In other cases: use list.

By the way: vectors don't reduce their allocated memory automatically.
This can be bad.

--
Kai Antweiler