On 2007-01-03 14:57, John wrote:
>
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.
--
Erik Wikström
--
[ See
http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]