what stl container should I use?
Author
I need something like a doubly-linked list, where a container essentially has two parts, like a std::map, but instead of having a single key that references some other value, both values can reference each other. For example:
DoublyLinked < std::string, int> doublylinkedlist;
doublylinkedlist["january"] = 1;
doublylinkedlist["february"] = 2;
std::cout << doublylinkedlist["january"] << std::endl; //displays "1"
std::cout << doublylinkedlist[2] << std::endl; //displays "february"
Thanks
I don't believe that, in general, there's a container specifically designed to do what you want to do. I'm not sure whether you actually want doubly linked list behaviour in the normal sense, but what you're describing is probably most easily implemented using two different maps. One mapping one way, one mapping the other.
Takes up extra space, but if you're trying to preserve lookup speed I don't think there's much choice. If you're more concerned about space than speed you could just have a vector of pairs. Sorting the vector by the most commonly looked up type would allow you to search one type of key quickly, searching the other way would be linear.
If you really want it to work exactly like what you have below you can wrap the two maps (or vectors, or whatever) with another template layer that is implements the [] operator for both types and looks up in the correct map based on the type.
Anyway, just some random ideas.
Takes up extra space, but if you're trying to preserve lookup speed I don't think there's much choice. If you're more concerned about space than speed you could just have a vector of pairs. Sorting the vector by the most commonly looked up type would allow you to search one type of key quickly, searching the other way would be linear.
If you really want it to work exactly like what you have below you can wrap the two maps (or vectors, or whatever) with another template layer that is implements the [] operator for both types and looks up in the correct map based on the type.
Anyway, just some random ideas.
No std:: container will do this. That said, a pair of them will:
You could implement an operator[], but you may run into problems if type_a is similar to type_b:
template < typename type_a , typename type_b >class cross_referenced_map{ std::map< type_a , type_b > map_a_to_b; std::map< type_b , type_a > map_b_to_a;public: type_b & lookup1st( const type_a & key ) { return map_a_to_b[ key ]; } type_a & lookup2nd( const type_b & key ) { return map_b_to_a[ key ]; }};cross_referenced_map< std::string , int > data;data.lookup1st( "january" ) = 1;data.lookup1st( "febuary" ) = 2;std::cout << data.lookup1st( "january" ) << std::endl;std::cout << data.lookup2nd( 2 ) << std::endl;You could implement an operator[], but you may run into problems if type_a is similar to type_b:
cross_referenced_map< int , int > data;cout << data[ 1 ] << endl; //which is meant?!?
Author
I tried this:
cross_map.h
cross_map.cpp
main.cpp
But it gives me a bunch of linker errors about undefined references to each of the member functions of cross_map. Thanks.
cross_map.h
#ifndef CROSSREFMAP_HPP#define CROSSREFMAP_HPP#include <map>template< typename A, typename B >class cross_map{ public: cross_map(); ~cross_map(); B & lookup_first( const A & key ); A & lookup_second( const B & key ); void add ( A first, B second ); private: std::map < A, B > first_map; std::map < B, A > second_map;}; #endifcross_map.cpp
#ifndef CROSSREFMAP_CPP#define CROSSREFMAP_CPP#include "cross_map.h"template< typename A, typename B >cross_map<A, B>::cross_map(){}template< typename A, typename B >cross_map<A, B>::~cross_map(){}template< typename A, typename B >B & cross_map<A, B>::lookup_first( const A & key ){ return second_map[key];}template< typename A, typename B >A & cross_map<A, B>::lookup_second( const B & key ){ return first_map[key];}template< typename A, typename B >void cross_map<A, B>::add ( A first, B second ){ first_map[first] = second; second_map[second] = first;}#endifmain.cpp
#include <cstdlib>#include <iostream>using namespace std;#include <string>#include "cross_map.h"int main(int argc, char *argv[]){ cross_map < char*, unsigned > calendar; calendar.add( "january", 1 ); calendar.add( "february", 2 ); calendar.add( "march", 3 ); std::cout << "january-> " << calendar.lookup_first("january" ) << std::endl; std::cout << "february-> " << calendar.lookup_first("february" ) << std::endl; std::cout << "3-> " << calendar.lookup_second(3) << std::endl; system("PAUSE"); return EXIT_SUCCESS;}But it gives me a bunch of linker errors about undefined references to each of the member functions of cross_map. Thanks.
Because your class is templated, you won't be able to put your implementation into a separate .cpp file that way. If you really want to "hide" it, consider using a .inl file which is #included at the end of your .h.
Author
I think that helped... except now it just gives me this:
[Build Error] [rpg.exe] Error 1
[Build Error] [rpg.exe] Error 1
Your code creates two copies of the data.
That makes it take twice the space it needs for your lookup operations.
If you add a function that allows you to change values then only one copy will get changed:
assuming you added a function primaryIndex that returns a reference:
cross_map < std::string, unsigned int> calendar;calendar.add( "january", 1 );calendar.add( "february", 2 );calendar.primaryIndex["january"] = 13; std::cout << "january-> " << calendar.lookup_first("january" );//prints january->13std::cout << "1-> " << calendar.lookup_second(1);//prints 1->january.instead try basing your container on this:
template<class T1, class T2>class cross_map{public: T2& primaryIndex(const T1&); const T2& primaryIndex(const T1&)const; T1& secondaryIndex(const T2&); const T1& secondaryIndex(const T2&)const;private: std::map<T1,T2> firstMap; std::map<T1*,T2*> secondMap;};
Hello silverphyre67,
Like the others say you have to create your own class.
With that, you should be able to overload the [ ] operator so it handle both
string and int.
cross_map<string,int> cm;
cm.add("jan",1);
cm.add("feb",2);
cout << cm[1] << endl;
cout << cm["feb"] << endl;
should give you:
jan
2
you could even do:
cm["may"]=5; but would also have to do cm[5]="may";
Lord Bart :)
Like the others say you have to create your own class.
With that, you should be able to overload the [ ] operator so it handle both
string and int.
template<class T1, class T2>class cross_map{public: cross_map() {} ~cross_map() {} void add ( T1 first, T2 second ) { fristMap[first]=second; secondMap[second]=first; } T2 & operator [] (const T1& key){ return firstMap[key]; } T1 & operator [] (const T2& key){ return secondMap[key]; } T2 & operator [] (const T1& key) const { return firstMap[key]; } T1 & operator [] (const T2& key) const { return secondMap[key]; }private: std::map<T1,T2> firstMap; std::map<T2,T1> secondMap;};cross_map<string,int> cm;
cm.add("jan",1);
cm.add("feb",2);
cout << cm[1] << endl;
cout << cm["feb"] << endl;
should give you:
jan
2
you could even do:
cm["may"]=5; but would also have to do cm[5]="may";
Lord Bart :)
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
