Multi key Maps
in [C++]
|
From: arunuj on 6 Feb 2006 08:46 Hi , I always find the usage of "if" statement annoying.. Just as it is the source for good amount of bugs... The regular map has a key and a value. I can find a value by the key. Is there any standard data structure which can stores two Keys, and when I ask with one key it gives me other Key? i.e: map[k1] gives me k2 and map[k2] gives me k1. This kind of data structure can remove lot of "if"s in the code.. Any idea if such a datastructure available? Or any Idea how I can implement it easily using map. Ofcourse using two maps is not so good idea. -Arun Joseph [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: James Hopkin on 6 Feb 2006 09:55 arunuj(a)gmail.com wrote: > The regular map has a key and a value. I can find a value by the key. > Is there any standard data structure which can stores two Keys, and > when I ask with one key it gives me other Key? > Try bimap: www.codeproject.com/vcpp/stl/bimap.asp James [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Clark S. Cox III on 6 Feb 2006 17:31 On 2006-02-06 08:46:32 -0500, arunuj(a)gmail.com said: > Hi , > > I always find the usage of "if" statement annoying.. Just as it is the > source for good amount of bugs... > > The regular map has a key and a value. I can find a value by the key. > Is there any standard data structure which can stores two Keys, and > when I ask with one key it gives me other Key? > > i.e: map[k1] gives me k2 and map[k2] gives me k1. > > This kind of data structure can remove lot of "if"s in the code.. > > Any idea if such a datastructure available? Or any Idea how I can > implement it easily using map. > > Ofcourse using two maps is not so good idea. What's wrong with using two maps? Just keep two maps, and wrap them in a single class that abstracts this away. If it is too expensive to store two copies of each object in the maps, then you could instead have two sets, storing pairs of iterators into a vector of pairs containing the actual objects, one set sorted on the first object in the pair, and the other set sorted on the second object in the pair. Properly abstracted, this should provide you with exactly what you want. -- Clark S. Cox, III clarkcox3(a)gmail.com [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Éric Malenfant on 6 Feb 2006 17:31 You may be interested in boost.MultiIndex: http://www.boost.org/libs/multi_index/doc/index.html It's documentation includes an example of how it can be used for exactly what you seem to be looking for: http://www.boost.org/libs/multi_index/doc/examples.html#example4 HTH, ?ric [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ]
From: Dakka <"news at electro dot mine dot on 6 Feb 2006 18:41
arunuj(a)gmail.com wrote: > Hi , > > I always find the usage of "if" statement annoying.. Just as it is the > source for good amount of bugs... > > The regular map has a key and a value. I can find a value by the key. > Is there any standard data structure which can stores two Keys, and > when I ask with one key it gives me other Key? > > i.e: map[k1] gives me k2 and map[k2] gives me k1. > > This kind of data structure can remove lot of "if"s in the code.. > > Any idea if such a datastructure available? Or any Idea how I can > implement it easily using map. > > Ofcourse using two maps is not so good idea. > > -Arun Joseph I have had this problem come up many times and finally decided to write a template which did it. See code below. C++ purists will no doubt object to the inheritance from STL however it works and the classes are trivial enough to ignore the risks. The implementation is also quite trivial - BiMapper has a fwd and a bckwd map. Inserts and deletes effect both maps. -- --dakka Dykstra's Observation: If debugging is the process of removing bugs, then programming must be the process of putting them in. //------------------------------------------------------------------------------------------------- #include <map> template<typename A, typename B, typename C> class MapperBase : public map <A, B, C> { public: bool Find(A a, B& result); typename MapperBase<A, B, C>::iterator Search(A a); bool Insert(A a, B b); bool ForceInsert(A a, B b); bool Replace(A a, B b); void Print(ostream& os); }; template<typename A, typename B> class Mapper : public MapperBase <A, B, less<A> > { }; template<typename A, typename B> class BiMapper { public: bool FindFwd(A a, B& result); bool FindBck(B b, A& result); bool Insert(A a, B b); int Size(); void Print(ostream& os); private: Mapper <A, B> fwd_; Mapper <B, A> bck_; }; [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] |