CODEWITHSUNDEEP
c++stl
NeonGlow
NeonGlow

Reputation: 1692

Searching data using different keys

I am no expert in C++ and STL.

I use a structure in a Map as data. Key is some class C1. I would like to access the same data but using a different key C2 too (where C1 and C2 are two unrelated classes).

Is this possible without duplicating the data? I tried searching in google, but had a tough time finding an answer that I could understand.

This is for an embedded target where boost libraries are not supported.

Can somebody offer help?

Upvotes: 4

Views: 430

Answers (7)

Kadir Erdem Demir
Kadir Erdem Demir

Reputation: 3595

I had the same problem, at first holding two map for shared pointers sound very cool. But you will still need to manage this two maps(inserting, removing etc...).

Than I came up with other way of doing this. My reason was; accessing a data with x-y or radius-angle. Think like each point will hold data but point could be described as cartesian x,y or radius-angle .

So I wrote a struct 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 used that as key, 

std::unordered_map<MyPoint, DataType> myMultIndexMap;

I am not sure if your case is the same or adjustable to this scenerio but it can be a option.

Upvotes: 0

Tony Delroy
Tony Delroy

Reputation: 106096

Bartek's "Idea 1" is good (though there's no compelling reason to prefer unordered_map to map).

Alternatively, you could have a std::map<C2, Data*>, or std::map<C2, std::map<C1, Data>::iterator> to allow direct access to Data objects after one C2-keyed search, but then you'd need to be more careful not to access invalid (erased) Data (or more precisely, to erase from both containers atomically from the perspective of any other users).

It's also possible for one or both maps to move to shared_ptr<Data> - the other could use weak_ptr<> if that's helpful ownership-wise. (These are in the C++11 Standard, otherwise the obvious source - boost - is apparently out for you, but maybe you've implemented your own or selected another library? Pretty fundamental classes for modern C++).

EDIT - hash tables versus balanced binary trees

This isn't particularly relevant to the question, but has received comments/interest below and I need more space to address it properly. Some points:

1) Bartek's casually advising to change from map to unordered_map without recommending an impact study re iterator/pointer invalidation is dangerous, and unwarranted given there's no reason to think it's needed (the question doesn't mention performance) and no recommendation to profile.

3) Relatively few data structures in a program are important to performance-critical behaviours, and there are plenty of times when the relative performance of one versus another is of insignificant interest. Supporting this claim - masses of code were written with std::map to ensure portability before C++11, and perform just fine.

4) When performance is a serious concern, the advice should be "Care => profile", but saying that a rule of thumb is ok - in line with "Don't pessimise prematurely" (see e.g. Sutter and Alexandrescu's C++ Coding Standards) - and if asked for one here I'd happily recommend unordered_map by default - but that's not particularly reliable. That's a world away from recommending every std::map usage I see be changed.

5) This container performance side-track has started to pull in ad-hoc snippets of useful insight, but is far from being comprehensive or balanced. This question is not a sane venue for such a discussion. If there's another question addressing this where it makes sense to continue this discussion and someone asks me to chip in, I'll do it sometime over the next month or two.

Upvotes: 2

Daniel Daranas
Daniel Daranas

Reputation: 22624

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

std::vector<Data> myData;

And then I map pointers to each element. Since it is possible that pointers are invalidated because of the future growth of the vector, though, I will choose to use the vector indexes in this case.

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

Don't expose the data containers to your clients. Encapsulate element insertion and removal in specific functions, which insert everywhere and remove everywhere.

Upvotes: 2

Bartek Banachewicz
Bartek Banachewicz

Reputation: 39370

Two keys of different types

I must admit I've misread a bit, and didn't really notice you want 2 keys of different types, not values. The solution for that will base on what's below, though. Other answers have pretty much what will be needed for that, I'd just add that you could make an universal lookup function: (C++14-ish pseudocode).

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

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

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

And the same for KeyB.

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

Key of the same type, but different value

Idea 1

The simplest solution I can think of in 60 seconds: (simplest meaning exactly that it should be really thought through). I'd also switch to unordered_map as default.

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

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

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

Idea 2

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

map<Key, shared_ptr<Data>> data;

Object of Data will be alive as long as there is at least one key pointing to it.

Upvotes: 3

Frerich Raabe
Frerich Raabe

Reputation: 94319

You could consider having a plain std::list holding all your data, and then various std::map objects mapping arbitrary key values to iterators pointing into the list:

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

I.e. instead of fiddling with more-or-less-raw pointers, you use plain iterators. And iterators into a std::list have very good invalidation guarantees.

Upvotes: 1

Mr.C64
Mr.C64

Reputation: 42924

You may store pointers 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 shared ownership of data:

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

Instances of Data can be allocated using std::make_shared().

Upvotes: 4

MSalters
MSalters

Reputation: 179799

Not in the Standard Library, but Boost offers boost::multi_index

Upvotes: 3

Related Questions