Another factor, which affects the constant Mikhail is talking about, is if the vector can fit into cache. This will make a huge difference. If you could allocate your nodes to be close together in memory (ie. use Cory's suggestion of boost::pool), you should be able to reap more cache coherency benefit in your list too.
On 7/12/06, Mikhail Kubzin <mikhail.kubzin@legion.biz> wrote:
There is a simple rule for choosing a container. If the number of elements
in it is not huge then use vector.
The reason is that although the complexity of for instance deleting an
element from a vector is greater than one from a list, but O-differences
(here linear-time vs. logarithmic-time) only matter if the containers are
big enough to swamp the constant factor, which for containers of small
objects like doubles frequently doesn't happen until after container sizes
exceed several thousand elements.
_______________________________________________
Boost-users mailing list
Boost-users@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/boost-users