Search data using different keys

Question

I am not an expert in C ++ and STL.

I use the structure on the map as data. The key is some class C1. I would like to access the same data, but using a different C2 key (where C1 and C2 are two unrelated classes).

Is this possible without duplicating data? I tried searching on Google, but it was hard for me to find an answer that I could understand.

This is for an embedded purpose where accelerated libraries are not supported.

Can anyone help?

Answer 1

You can store pointers up to Data as std::map values, and you can have two maps with different keys pointing to the same data.

I think a smart pointer like std::shared_ptr is a good option in this case of data sharing:

 #include <map> // for std::map #include <memory> // for std::shared_ptr .... std::map<C1, std::shared_ptr<Data>> map1; std::map<C2, std::shared_ptr<Data>> map2; 

Data instances can be allocated using std::make_shared() .

Answer 2

Not in the standard library, but Boost offers boost::multi_index

Answer 3

Two keys of different types

I have to admit that I misunderstood a little, and didn’t really notice that you need two keys of different types, not values. The solution for this will be based on what is below. The other answers have pretty much what would be needed for this, I would add that you can make a universal search function: (C ++ 14-ish pseudocode).

 template<class Key> auto lookup (Key const& key) { } 

And specialize it for your keys (perhaps easier than SFINAE)

 template<> auto lookup<KeyA> (KeyA const& key) { return map_of_keys_a[key]; } 

And the same for KeyB .

If you want to encapsulate it in a class, the obvious choice would be to change the lookup to operator[] .

---

A key of the same type but a different value

Idea 1

The simplest solution that I can think of in 60 seconds: (the simplest sense is that it needs to be thought out). I would also switch to unordered_map by default.

 map<Key, Data> data; map<Key2, Key> keys; 

Access via data[keys["multikey"]] .

This will obviously waste some space (duplicating objects of type Key ), but I assume that they are much smaller than type Data .

Idea 2

Another solution would be to use pointers; then the only cost of the duplicate is the (smart) pointer:

 map<Key, shared_ptr<Data>> data; 

The Data object will be available as long as it has at least one key.

Answer 4

What I usually do in these cases is the use of non-pointers. I store my data in a vector:

 std::vector<Data> myData; 

And then I overlay pointers on each element. Since it is possible that pointers are invalid due to future growth of the vector, I will choose to use vector indexes in this case.

 std::map<Key1, int> myMap1; std::map<Key2, int> myMap2; 

Do not expose data containers to your customers. Encapsulate the insertion and deletion of elements into specific functions that are inserted everywhere and deleted everywhere.

Answer 5

Bartek's “Idea 1” is good (although there is no good reason to prefer from unordered_map to map ).

Alternatively, you can have std::map<C2, Data*> or std::map<C2, std::map<C1, Data>::iterator> to allow direct access to Data objects after a single C2 search, but then you need to be more careful not to get access to invalid (erased) Data (more precisely, before erase from both containers is atomic from the point of view of any other users).

It is also possible that one or both map move to shared_ptr<Data> - others could use weak_ptr<> if it is useful for ownership. (This is in the C ++ 11 standard, otherwise the obvious source - boost - seems to be for you, but maybe you implemented your own or chose a different library? Pretty fundamental classes for modern C ++).

EDIT - Hash Tables and Balanced Binary Trees

This is not particularly relevant to the issue, but received comments / interest below, and I need more space for it to be resolved correctly. Some moments:

1) Bartek does not recommend changing from map to unordered_map without recommending impact research. Reusing an iterator / pointer is dangerous and unreasonable if there is no reason to think that it is necessary (the question does not mention performance) and there are no recommendations for the profile.

3) A relatively small number of data structures in the program are important for critical behavioral characteristics, and there are many times when the relative performance of one against the other is of little interest. Supporting this claim - the masses of code were written using std::map to ensure portability to C ++ 11 and to perform just fine.

4) When performance is a serious issue, the advice should be “Care => profile”, but, saying that the rule of thumb is ok - according to “Don't pessimize prematurely” (see, for example, Sutter and Alexandrescu C ++ Coding Standards ) - and if asked, I would gladly recommend unordered_map by default, but this is not particularly reliable. It seems to me that the world does not recommend recommending every use of std::map .

5) This side track of container performance began to extract special pieces of useful information, but far from complete or balanced. This question is not a reasonable place for such a discussion. If there is another question regarding this, when it makes sense to continue this discussion, and someone asks me to come in, I will do this within the next month or two.

Answer 6

You might think that you have a regular std::list containing all your data, and then various std::map objects that display arbitrary key values ​​for iterators pointing to a list:

 std::list<Data> values; std::map<C1, std::list<Data>::iterator> byC1; std::map<C2, std::list<Data>::iterator> byC2; 

those. instead of messing with more or less raw pointers, you use simple iterators. Iterators in std::list have very good invalidation guarantees.

Answer 7

I had the same problem: at first two maps for common pointers sound very cool. But you still have to manage these two cards (insert, delete, etc.).

Than I came up with another way to do this. My mind was; access to data with xy or radius. Think that each point will contain data, but the point can be described as Cartesian x, y or radius-angle.

So, I wrote a structure like

 struct MyPoint { std::pair<int, int> cartesianPoint; std::pair<int, int> radianPoint; bool operator== (const MyPoint& rhs) { if (cartesianPoint == rhs.cartesianPoint || radianPoint == rhs.radianPoint) return true; return false; } } 

After that, I could use this as a key,

 std::unordered_map<MyPoint, DataType> myMultIndexMap; 

I'm not sure if your case is the same or is being configured for this scenerio, but it might be an option.