CODEWITHSUNDEEP
c++listvectordictionarystl
Mustapha
Mustapha

Reputation: 167

STL map like data structure to allow searching based on two keys

I want to make a map like structure to allow searching by two keys both will be strings, here's an example:

Myclass s;

Person p = s.find("David"); // searching by name

// OR

p = s.find("XXXXX"); // searching by ID

i don't want a code solution, i just want some help to get started like the structures i can use to achieve what i want, help is appreciated guys, it's finals week.

Upvotes: 0

Views: 653

Answers (2)

LihO
LihO

Reputation: 42083

There are many different ways how this could be achieved. The question is: what are the complexities of insert, delete and lookup operations that you aim for?

std::map is implemented as red-black tree that provides increadibly quick self-balancing (rotations) and all of mentioned operations (lookup/find, insert, delete) with complexity of O(log(n)). Note that this suits the idea of single key.

With 2 keys you can not keep elements sorted because the order based on one key will be most likely different than order based on the other one. The most straightforward and natural approach would be storing records in one container and holding the keys used by this container in 2 different structures, one optimized for retrieving this key given id and the other one for retrieving it given name.

If there is a constraint of storing everything at one place while you'd like to optimize find operation that will support two different keys, then you could create a wrapper of std::map<std::string, Person> where each element would be contained twice (each time under a different key), i.e. something like:

std::map<std::string, Person> myContainer;
...
Person p;
std::string id = "1E57A";
std::string name = "David";
myContainer[id] = p;
myContainer[name] = p;
I can think of 2 advantages of doing this:
  • quite satisfying performance:
    • lookup with complexity O(log(2*n))
    • insertion & deletion with complexity O(2*log(2*n))
  • extremely simple implementation (using existing container)
    • you just need to remember than the "expected" size of the container is half of its actual size
    • both of the keys: id and name should be attributes of Person so that when you find a concrete element given one of these keys, you immediately have the other one too
Disadvantage is that it will consume 2x so much memory and there might even be a constraint that:
  • none of the names should be an id of some other person at the same time and vice versa (no id should be a name of some other person)

Upvotes: 0

ooga
ooga

Reputation: 15501

Put your records into a vector (or list). Add a pointer to the record objects to two maps, one with one key and one with the other.

Upvotes: 2

Related Questions