0

Is there any associative container that is sorted both on key and value? I want this data structure in C++. In Java, there are methods containsKey and containsValue. I need an iterator of this associative data structure both ways (containsKey and containsValue) in minimum possible time. It must approach almost to log(n).

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
Mustafa Muhammad
  • 23
  • 1
  • 6
  • There is a `std::set` where each value is itself used as an key, and the elements are sorted by that value.If you want separate key and value pairs(as in case of a `std::map`) none is provided by the standard library.You will have to use Boost or write your own container class as per your custom requirement. – Alok Save Aug 29 '12 at 03:16
  • There is [this existing post](http://stackoverflow.com/questions/5749073/reverse-map-lookup) that contains the usual answer (Boost multi-index). Is your question a duplicate of that post? – jogojapan Aug 29 '12 at 03:19
  • @jogojapan not as I understand the question. Here, the OP is concerned about the iteration-ordering of keys and values, not with mapping values back to keys. – Matt Ball Aug 29 '12 at 03:21
  • I want Separate Key and Value.. Can i find this in boost? or is there any way that i can implement a container very close to this? – Mustafa Muhammad Aug 29 '12 at 03:21
  • @MattBall Ok, understood. I'd have to say, though, that Java `containsKey` and `containsValue` are not used for iteration. On a related note, `containsValue` is not required to be O(log n) in Java. – jogojapan Aug 29 '12 at 03:29

2 Answers2

1

What you're describing sounds a lot like the Boost.Bimap containers framework, which allows you to build bidirectional maps that let you look up keys and values equally efficiently. This might not exactly be what you're looking for, but the library is well-tested and might be a good starting point.

Hope this helps!

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
0

It might be that you want all the T1s for a given T2 and vice versa. That's not exactly what you said, but if that's what you want boost::bimap is the way to go.

std::set < std::pair < Tkey, Tvalue > > will do what you want in a basic kind of way. Auxiliary std::set < Tkey > and std::set < Tvalue > give you global contains_key and contains_value in O(log(n)), if that's what you want.

std::map < Tkey, std::set < Tvalue> > gives you convenient O(log(n)) access to the values for a key. Maintaining an inverted copy gives you convenient O(log(n)) access to the keys for a value.

It really all depends on what you want to do, and whether the data is an arbitrary set of key, value pairs or somehow restricted.

phunctor
  • 599
  • 3
  • 9