CODEWITHSUNDEEP
c++dictionarydata-structureshash
Tariq Iqbal
Tariq Iqbal

Reputation: 27

How to create a unique key, given arbitrary number of integers ? And use that key to store and later lookup from the map

So I'm trying to generate a unique key from the arbitrary number of integers so that i can later lookup the value using that unique key from the map. Ordering of numbers should not matter while generating the unique key

I have looked into various options which includes using Tuple, Hashing and Concatenation the int to generate key but unable to find the optimal solution.

The expected function or logic should take an array of int and in return it should give a unique key (int).

For example

Sample Input can be [1,5,6], [134,1] [6,5,1] [1,5,6] key should be same as [6,5,1]

Upvotes: 0

Views: 438

Answers (1)

463035818_is_not_an_ai
463035818_is_not_an_ai

Reputation: 122228

As I understand your question (mainly infered from comments) you want to put some data structure in a map and use an array of integers as key where different orders of the integers should actually be considered as the same key.

For the sake of the example, lets say "some data structure" is a std::string, then the most straightforward is to use a std::set as keys, because no matter what order you use to construct the set, 1 5 6, 1 6 5 or 6 5 1, you get the same set:

#include <string>
#include <map>
#include <iostream>

int main() {
    std::map< std::set<int>, std::string> x;
    x[ { 1,5,6} ] = "Hallo";    
    std::cout << x[ { 6 , 5, 1} ] << "\n";    
}

Live example

It is a bit wasteful to use a set just to have the elements sorted, so you can use a sorted vector instead. To prevent the user of the map needing to sort the vector you can use a helper type, as in:

#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <initializer_list>

struct sorted_vector {
    std::vector<int> x;
    sorted_vector(std::initializer_list<int> l) : x(l) {
        std::sort(x.begin(),x.end());       
    }
    bool operator<(const sorted_vector& other) const {
        return x < other.x;
    }
};

int main() {
    std::map< sorted_vector, std::string> x;
    x[ { 1,5,6} ] = "Hallo";    
    std::cout << x[ { 6 , 5, 1} ] << "\n";   
}

Live example

I do understand that you are worried about efficiency especially when the vector contain lots of elements. However, unless you really hit a limit or profile your code and realize that you need to improve something, I would not bother to reinvent the wheel.

Upvotes: 2

Related Questions