• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 187
  • Last Modified:

Template-based container with more than one kind of key

Hi -- I would like an STL container with 'map' functionality which would allow more than one kind of key, eg, a container of objects holding sharemarket stock info which could be looked up on either their numeric code or their alpha code. Ideally, it would be templated so that it could allow an arbitrary number of different kinds of key. I can think of ugly ways of doing it, but would like a clean way. I'm not after any code as such, just an insight into how to approach it.
I'm using Micro$oft Visual C++ v6.
Thanks ...
0
johndalzell
Asked:
johndalzell
  • 2
1 Solution
 
tinchosCommented:
sorry, didnt quite understood what you're trying to achieve

if you can explain a little more or give an example please
0
 
johndalzellAuthor Commented:
Probably an example is best. Consider this collection of stock info on the Australian Stock Exchange:

StockCode  NumericID    Price   Name
BHP         80          10.50   Broken Hill Proprietary CCL         130         8.35    Coca Cola Amatil
WOW         510         4.76    Woolworths Ltd
... (etc) ...

I'd like to be able to have a template class where I could define an arbitrary number of ways to access the collection. In the above case, assuming each row is a 'stocks_t' object, I'd like to go something like the following pseudo-code. I know this won't work for an arbitrary collection of objects, but maybe there's a way of achieving the same thing with different syntax:
   
    myCollection<stocks_t> Stocks;
   
    Stocks.addindex( "StockCode" );
    Stocks.addindex( "NumericID" );

    Stocks.find( "NumericID", 130 )
    // ---> item #2 (Coca Cola Amatil)
    Stocks.find( "StockCode", "WOW" )
    // ---> item #3 (Woolworths)    

0
 
SalteCommented:
The generic way to do what you want is to do something like this:

step 0: I assume the type of data to be T and a typical key type to be K or K1, K2, K3 etc.

step 1. Create a map for each key type K that can hold a key of type K and data of type T * (pointer to T).

for a key type K you make a std::map<K,T *> m;

For example:

std::map<K1,T *> m1;
std::map<K2,T *> m2;

step 2. Whenever you add an element to the data structure you add a pointer to the element to each of the maps with their respective keys.

void add_elem(const T & v)
{
   m1[v.key1()] = & v;
   m2[v.key2()] = & v;
   etc...
}

Step 3. When you do a lookup based on a key value you get a pointer to the object, any modifications done to that object will then also affect the other maps that references the same object. Specifically if you therefore change any of the values that are used to compute a key you must first remove the element from that map or those maps, do the modification and then re-insert them in the map or maps. Maps that uses keys that are unaffected by the change does not need to be changed in this way.

void change_foo(T & v)
{
  // v is changed in a way that affect key1() and key3() but not key2() or other keys.
  m1.erase(v.key1());
  m3.erase(v.key3());
  ...do the change...
  m1[v.key1()] = & v;
  m3[v.key3()] = & v;
}

Step 4. When you want to remove an object then you must remove it from every map and then possibly delete the object if you want to do that. Don't delete the object before it is removed from all the maps.

void remove_elem(const T & v)
{
   m1.erase(v.key1());
   m2.erase(v.key2());
   m3.erase(v.key3());
   ...etc...
}

If the element was instead created on heap and the remove_elem should also delete it then it should instead be something like:

void remove_elem(T * p)
{
  m1.erase(p -> key1());
  m2.erase(p -> key2());
  m3.erase(p -> key3());
  ...etc...
  delete p;
}

Now, you can probably place this in a class if you like and have all the maps in that class etc.

Now, all the above expect all keys to be unique, if they aren't unique you must do the following changes for those keys that are not unique - unique keys can still use the code above:

A key is unique if for any two objects v1 and v2 in the map, the v1.key() == v2.key() implies that v1 == v2. I.e. they are the same objects.

If a key is not unique, i.e. there are two different objects that has the same key value for a given key, then you must do the following changes:

1. Use multimap instead of map.
2. When inserting the elements you can do exactly as before.

3. When doing lookup for this key you must make sure you get the right object. Using the lookup function you check if the object is the object you're looking for, if not, do a new lookup just past the object just found. If the next object found isn't the one you're looking for you repeat the process until you find the object.

4. When modifying the value and the modification affect a key that is not unique you must use the lookup method described above in (3) for finding the object to remove from the multimap. Use iterator to indicate exactly which object to remove from the multimap instead of the key, since the key isn't unique. Other than that, the modification and re-insertion works the same.

5. When removing a value from the set you must likewise make sure you get the right element and not just some other element that happened to have the same key. So the lookup method from (3) must be used also here. Other than that, the code is as before.

I think I have covered all issues about this subject now so you can go ahead and make a very generic map with N keys, some unique and some not unique.

Good luck with your program.

Alf
0
 
johndalzellAuthor Commented:
Sorry for delay in replying.
A very comprehensive answer. Thanks.
0

Featured Post

Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

  • 2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now