LCA of two map::const_iterators

[John]

The lowest common ancestor of two nodes in a red black tree can be
computed
in O(log n) time. Is there an implementation of LCA for two map
iterators? If not,
does anyone know how to implement this on std::map? Has anyone else
done
something similar?

Thanks,
--j

 

[=?ISO-8859-1?Q?Erik_Wikstr=F6m?=]

The lowest common ancestor of two nodes in a red black tree can be
computed in O(log n) time. Is there an implementation of LCA for two
map iterators? If not, does anyone know how to implement this on
std::map? Has anyone else done something similar?

Do you have any guarantee that std::map will use a red-black tree? Sure,
it probably is but I don't think that there is anything in the
specification saying that it should be. So if such an implementation
existed it would have to be purely platform-specific. You might have
better luck in a forum specific for you platform.

Out of curiosity, why would you want such a thing? It seems to me you
are misusing std::map, if you want a tree-structure you have to make one
your self, std::map is an associative container, not a tree-structure.

 

[Mark P]

The lowest common ancestor of two nodes in a red black tree can be
computed
in O(log n) time. Is there an implementation of LCA for two map
iterators? If not,
does anyone know how to implement this on std::map? Has anyone else
done
something similar?

Thanks,
--j

This is all implementation dependent and therefore there's no portable
solution. While it's typically the case, there's no requirement that a
map be implemented as a red-black tree, and in any event the tree
structure is not visible from the map interface.

 

[Michiel.Salters]

Erik Wikström schreef:

Do you have any guarantee that std::map will use a red-black tree? Sure,
it probably is but I don't think that there is anything in the
specification saying that it should be.

There isn't. The only requirement is on the complexity of each member.

Now, I'm fairly certain that it's possible to put more than one map
element
in each node of a tree, e.g. 1 to 4 elements (this adds only O(1)
complexity,
due to the finite upper bound) in which case the 'ancestor' really
makes no
sense. Would that make sense? Perhaps for a std::map with 4 byte keys,
to improve locality.

Michiel Salters