Make object searchable with two different keys

Question

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

"but that doubles the amount of memory used" - indices aren't free, unfortunately. You want to introduce orderings that are completely unrelated to each other, so I am afraid you'll need to use some additional memory to hold that data in. Of course you can store references to those large objects, or make the objects themselves store references to "large array", thus only doubling the index space. — Bartek Banachewicz, Sep 27 '22 at 13:49
What is your exact use case for this? What are you trying to solve? — kiner_shah, Sep 27 '22 at 13:49
depends on more details. Could be an option to store the instances in a `std::vector` sort it with respect to `key1`, then use a `std::set ` sorted with respect to `key2` with pointers pointing to elements of the vector. Doesn't work (easily) when you need to add / remove elements — 463035818_is_not_an_ai, Sep 27 '22 at 13:52
Store the objects themselves in one of the sets and pointers to the objects in the second set. Then it’s not exactly “doubling the memory used”. Of course there will always be a memory overhead for each additional index you need. — Andrej Podzimek, Sep 27 '22 at 13:54
your clarification is about what you do not want. I think this was clear before. What is a little unclear is what you do want. Why do you need two different orderings? Do you need to add / remove elements frequently? Is `O(log(N))` look-up absolutely necessary for both ways? How much additional memory would be acceptable? — 463035818_is_not_an_ai, Sep 27 '22 at 14:01

463035818_is_not_an_ai · Answer 1 · 2022-09-27T14:50:56.393

3

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; });

edited Sep 27 '22 at 14:50

answered Sep 27 '22 at 14:07

463035818_is_not_an_ai

109,796
11
89
185

Using pointers seems like the way to go for me. But could I store pointers in both sets/verctors (see edit 3 of my question)? – PieterV Sep 27 '22 at 14:28
"the type of container you actually choose isnt that important." yea right, then you add elements to `sorted1` and boom. – Slava Sep 27 '22 at 14:33
@Slava wasnt happy with that wording either. Tried to fix it – 463035818_is_not_an_ai Sep 27 '22 at 14:51
@PieterV why not ? – 463035818_is_not_an_ai Sep 27 '22 at 14:51

Slava · Accepted Answer · 2022-09-27T15:17:08.033

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.

Make object searchable with two different keys

2 Answers2