Sign in to follow this  

what stl container should I use?

This topic is 4595 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
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
Quote:
Original post by Lord Bart
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.

*** Source Snippet Removed ***

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 :)


If you're going to do it that way, make operator[] return a const reference or a proxy class which handles assignment. Otherwise it's too easy to corrupt your double map by only entering values into one of the maps. Also be aware that overloading operator[] like that will make your class fail to compile if T1 is the same as T2.

Enigma

Share this post


Link to post
Share on other sites
Lord Bart:

Your code won't compile when T1 and T2 are the same type - in that case there's no way to resolve the overload of operator[].

Thats why I used named functions primaryIndex() and secondaryIndex().
Your code also contains 2 copies of the data, making your operator[] corrupt the data.

I'll hopefully get time to write an stl compliant version of this container when I get home this evening to post.

Share this post


Link to post
Share on other sites
A major bug regarding all of our reference-returning implementations:

whatever_you_named_this_container< string , int > data;
data[ "febuary" ] = 1;
data[ "febuary" ] = 2;

//The behavior we'd want/expect:
assert( data[ 2 ] == "febuary" );

//The actual behavior exhibited:
assert( data[ 1 ] == "febuary" );
assert( data[ 2 ] == string() );

The sane solution for dealing with this that I can think of is extremely nasty and involves a "reference" wrapper class which will still not make the code foolproof.

Really, the container should have the same properties as a set< pair< type1 , type2 > > - which is to say, the mapping pairs can be inserted or erased, but cannot be modified. Lookup by operator[] would return a const reference, which would allow for assert( data[ 1 ] == "january" ), but would not allow for data[ 1 ] = "january", which would have to be written as: data.insert( 1 , "january" ) or similar. The only difference would be mantaining a pair of maps to speed the lookup from one side of the problem set, giving functions akin to "lookup_1st_by_2nd", plus implementing the functions to appropriately mantinence the maps.

If we went down that very bad road of making our best effort at allowing data[ 1 ] == "january" - that is, dealing with all the possibilities except for storing a reference like so:

type1 & value = data[ 1 ];

And then later modifying it (or doing similar with pointers), the members of the class would look something like this:

typedef std::pair< type1 , type2 > value_type;
std:set< value_type > values;
std::map< type1 , value_type * > map12;
std::map< type2 , value_type * > map21;

[Edited by - MaulingMonkey on May 16, 2005 12:58:48 PM]

Share this post


Link to post
Share on other sites

This topic is 4595 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this