Jump to content
  • Advertisement
Sign in to follow this  
silverphyre673

what stl container should I use?

This topic is 4814 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
Share on other sites
No std:: container will do this. That said, a pair of them will:

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?!?

Share this post


Link to post
Share on other sites
I tried this:

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;
};



#endif



cross_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;
}



#endif



main.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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

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->13
std::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;

};

Share this post


Link to post
Share on other sites
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.



template&lt;class T1, class T2&gt;
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&lt;T1,T2&gt; firstMap;
std::map&lt;T2,T1&gt; 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 :)

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!