?
Solved

Template-based container with more than one kind of key

Posted on 2003-03-05
4
Medium Priority
?
183 Views
Last Modified: 2010-04-01
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
Comment
Question by:johndalzell
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 2
4 Comments
 
LVL 9

Expert Comment

by:tinchos
ID: 8076468
sorry, didnt quite understood what you're trying to achieve

if you can explain a little more or give an example please
0
 

Author Comment

by:johndalzell
ID: 8076846
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
 
LVL 12

Accepted Solution

by:
Salte earned 300 total points
ID: 8078910
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
 

Author Comment

by:johndalzell
ID: 8149557
Sorry for delay in replying.
A very comprehensive answer. Thanks.
0

Featured Post

VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Errors will happen. It is a fact of life for the programmer. How and when errors are detected have a great impact on quality and cost of a product. It is better to detect errors at compile time, when possible and practical. Errors that make their wa…
Templates For Beginners Or How To Encourage The Compiler To Work For You Introduction This tutorial is targeted at the reader who is, perhaps, familiar with the basics of C++ but would prefer a little slower introduction to the more ad…
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…
Suggested Courses

764 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question