On 3/21/13 5:02 PM, Avinash wrote:
Given a STL map, say map<int, bool> m1. Given two value a & b that may
or may not exists in m1. Find the Least Common Ancestor in STL MAP.
Remember you don't have access to root, so you need to iterate using
iterator. Use the methods/function of MAP forex begin, end, find etc.
Solution should be efficient in terms of time complexity (forex if we
use method find, we get it in O(logN) internally) --
You received this message because you are subscribed to the Google
Groups "Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send
an email to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
STP Map is a sorted associative container. It stores key-value pair, in
sorted order.
For more information on the above read about map [1] and about sorted
associative containers. [2]
Map stores key-value pair and use iterators for traversal.
The iterators will either give you next value (forward iterator) or
previous value (reverse iterator).
The container does *NOT* know, how it is implemented underneath the hood.
Given that you have the knowledge that map is implemented as Red-Black
tree (a form of balance tree)
in libstd++ you can not abuse the container to tweak the internals.
I can write my own sorted associative container, use whatever data
structure I want underneath and release it
and it would still be correct.
SGI gives specifications. Each compiler is free to implement its own
/internal/ implementation.
The STL does not expose the internals as it would violate OOP
principles, i.e. exposing the underlying
data structures as it may lead to undesirable behavior.
Think of it like this, say N values are inserted in a map. You don't
know where is root, what is the tree structure ?
Hell, you don't even know if that is a tree. The point is you are not
supposed to know.
You basically don't know anything apart from two facts: (a) You can get
``value'' from a given ``key''. (b) You can traverse in sorted or
reverse-sorted manner.
This /nullifies/ your question. In case you are interested in LCA,
create your own "Tree structure" instead of trying to abuse the de facto
sorted associative container of the Standard Template Library.
[1] http://www.sgi.com/tech/stl/Map.html
[2] http://www.sgi.com/tech/stl/SortedAssociativeContainer.html
--
You received this message because you are subscribed to the Google Groups "Algorithm
Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.
