Make object searchable with two different keys-CodePudding

Given a class with two keys:

class A {
    int key1;
    int key2;
    byte x[]; // large array
}

If multiple objects of class A are instantiated and I want to sort them by key1, I can insert them into an std::set.

But if I want to sort these objects both by key1 and by key2, how would I do that?

I could create two sets where one set sorts by key1 and the other set sorts by key2, but that doubles the amount of memory used. How can I avoid this?

Edit 1:

As far as I know, when an object is inserted into a set, the object is copied. So if I create two sets (one sorted by key1 and one sorted by key2), that means two versions of the object will exist: one in set1 and one in set2. This means that member x also exists twice, which unnecessarily doubles the amount of memory used.

Edit 2:

To give a more specific example: given the class Person.

class Person {
    std::string name;
    std::string address;
    // other fields
}

I want to be able to find people either by their name and by their address. Both keys won't be used at the same time: I want to be able to call find(name) and find(address).

Also, objects of the Person class won't be added or removed from the datastructure that often, but lookups will happen often. So lookups should ideally be fast.

Edit 3:

Storing pointers to the objects in the set instead of the objects themselves seems like a good solution. But would it be possible to store pointers in both sets? I.e.

std::set<A*> set_sorted_by_key1;
std::set<A*> set_sorted_by_key2;

A *obj_p = new A();

set_sorted_by_key1.insert(obj_p);
set_sorted_by_key2.insert(obj_p);

CodePudding user response：

Finding an element in a sorted vector via binary_search is O(log(N)) just as std::set::find is O(log(N)), hence if you want to stay with standard containers, concerning time complexity of finding elements, the type of container you actually choose isnt that important.

Concerning the additional memory, you wont get it any cheaper than storing an additional pointer to the elements somewhere.

So what you can do is

 std::vector<A> sorted1;
 std::sort(sorted1.begin(),sorted1.end(), 
           [](const A& a,const A& b) { return a.key1 < b.key2; });

 std::vector<A*> sorted2;
 // ... fill with pointers to elements in sorted2
 std::sort(sorted2.begin(),sorted2.end(), 
           [](A* a, A* b) { return a->key2 < b->key2; });

CodePudding user response：

Storing pointers to the objects in the set instead of the objects themselves seems like a good solution. But would it be possible to store pointers in both sets?

Sure, your sets seem to share ownership of that objects, so:

class Person {
    std::string name;
    std::string address;
    // other fields
};

using PersonPtr = std::shared_ptr<Person>;

Now you want to sort them by name:

struct CmpName {
    using is_transparent = void;
    
    bool operator()( const PersonPtr &p1, const PersonPtr &p2 ) const { return p1->name < p2->name; }
    bool operator()( const std::string &s, const PersonPtr &p2 ) const { return s < p2->name; }
    bool operator()( const PersonPtr &p1, const std::string &s ) const { return p1->name < s; }
};

std::set<PersonPtr,CmpName> byName;

Note type alias using is_transparent = void; and two additional methods are to enable equivalent search in std::set otherwise you would have to create instance of std::shared pointer<Person> just to to lookup. Details can be found here What are transparent comparators?

And search it:

auto f = byName.find( "John" );

Here how it works: Live example

Searching by address can be done very similar way, just add another comparator struct and initialize std::set with it.

Though you can store object and have multiple indexes using boost.multiindex but it has learning curve.