Re: map or set for handling struct with a key?

On Aug 8, 4:05 pm, Digital Puer <digital_p...@hotmail.com> wrote:


What people often forget in O() notation is that there is a
coefficient k which goes in front of it and reflects the cost of the
overhead for specific implementations of an algorithm. This value can
be important. A vector has the following benefits over a map/set:

1) Much less overhead per item. A map/set is usually a red/black tree
and each node has left, right, and parent pointers plus data for the
item.

2) Fewer allocations. Each item in a map/set is kept as an
individually allocated node whereas a vector is usually allocated in
chunks which can hold several nodes.

3) Quicker movement from one item to the next. After a comparison to
get to the next node, a pointer has to be read from memory, with a
vector you often just add two registers together.

4) Locality of reference. Since vectors are allocated in large chunks
of contiguous memory, you are much likelier to get a cache hit while
navigating through the vector than you would in navigating a set/map.

Maps/sets have the following benefits over a vector:

1) Existing iterators don't get invalidated by inserts and only the
iterators directly involved get invalidated by deletes.

2) Vectors may possibly require a lot of data shifting during inserts/
deletes.

3) More natural interface. You have to use the std algorithms to
manipulate the vectors whereas the map/set containers have them built-
in.

These are the kinds of factors that often make a sorted vector better
than a map or set if the data is mostly static. How much the data
changes is where the trade off occurs. If you have insertions and
deletions occurring frequently, then the cost of constantly keeping
the vector sorted will make a map or set more attractive. If
insertions/deletions can be batched and/or kept infrequent then a
vector is generally faster.

joe