Find common values in map

Question

Is there a way to find out if a map contains common values?

above keys 1, 3 and 5 have common values.

I am trying not to use a loop if possible.

I looked at the map key compare and value compare functions but not sure if that’s achieves what I am trying to do.

Edit: Im interested in seeing if there are any member functions of map or any other functions I can use.

Do you only want to know IF it contains duplicate values (vs knowing WHAT those duplicates are)? If so, and memory isn't a constraint, you can store all the values in a `set`. Then if the size of the `map` differs from the `set`, you have duplicates. — JohnFilleau, Mar 03 '20 at 18:18
Yes I am aware of this but wondering if there is an alternative. And yes I just want to know if it contains duplicates — henhen, Mar 03 '20 at 18:20
Please edit the question to include all methods you are aware of that you don't want to use. — JohnFilleau, Mar 03 '20 at 18:21
`std::map>` put the value as key and key as list of value. There is no method which compare value of maps — Build Succeeded, Mar 03 '20 at 18:21
Do you need a generic solution or just one that works for specific integer values? Also how big is the data? — Sopel, Mar 03 '20 at 18:26
@Mannoj It sounds like a very bad alternative to `std::multimap`. — François Andrieux, Mar 03 '20 at 18:27
@Mannoj if I do this, won’t i have to iterate through the list? — henhen, Mar 03 '20 at 18:27
@henhen How is that map populated? Maybe during the population of that map, you track whether a duplicate occurs? — PaulMcKenzie, Mar 03 '20 at 18:28
@henhen There is no solution that won't require you to iterate through the map. Whether it's to sort it or to check a predicate, whether is hidden in an algorithm function or through recursion, somewhere somehow you will loop. — François Andrieux, Mar 03 '20 at 18:28
Can you clarify what you mean when you say you don't want to use a loop? Do you mean you don't want the solution to use a loop at all (even under the hood, because of performance reasons), or that you don't want to have a visible loop in your code? — JohnFilleau, Mar 03 '20 at 18:29
@Sopel an optimized solution would be great. Data can be any given input. — henhen, Mar 03 '20 at 18:29
@PaulMcKenzie map is populated by iterating through a vector. — henhen, Mar 03 '20 at 18:31
@FrançoisAndrieux it's not the same, he can return the duplicate value list in single lookup, which is not possible as u mentioned for multi_map — Build Succeeded, Mar 03 '20 at 18:35
Your requirement is strange to me. You could probably attract higher quality answers if you can explain why you're okay with an under-the-hood loop, so long as your part of the code doesn't have a loop in it. — JohnFilleau, Mar 03 '20 at 18:36
@henhen what is actual problem? Vector you had, then why map comes here? Explain the problem you are trying to solve — Build Succeeded, Mar 03 '20 at 18:37
@Mannoj Technically true, but you still have to iterate over the list you obtain so there is no actual gain. Edit : I now see that you don't actually need to iterate over the list in this scenario, you probably only care about the size. — François Andrieux, Mar 03 '20 at 18:46

score 2 · Answer 1 · answered Mar 03 '20 at 19:23

2

suppose initial map is m:

//to create new map

map<int , vector<int>> m2;
for(auto it: m)
{
   m2[it.second].push_back(it.first);
}

// this will create a map as required, i.e.,

2 : [1,3,5]
5 : [2]
6 : [4]

//to print or use the new map

for(auto it: m2)
{
   cout<<it.first<<": "<<endl;
   for(auto it1 : it.second)
   {
       cout<<it1<<" ";
   }
       cout<<endl;
 }

// this will generate an output like:

 2 : 1 3 5
 5 : 2
 6 : 4

answered Mar 03 '20 at 19:23

Nawed Diwan

51
4

This is called inverse index. You basically implemented elastic search. – Maxim Egorushkin Mar 03 '20 at 19:40
i thought it may help! – Nawed Diwan Mar 03 '20 at 20:07
I think that is a good alternative but the first @John comment is optimal in space allocation. – Mandy007 Mar 03 '20 at 21:14
Using vector is bad idea, that's why I have mentioned my answer to use list – Build Succeeded Mar 04 '20 at 03:04
what is the benefit of a list over vector? – Nawed Diwan Mar 04 '20 at 05:35
1

@NawedDiwan Memory allocation overhead is there in vector due to resizing. Refer: https://stackoverflow.com/questions/2209224/vector-vs-list-in-stl – Build Succeeded Mar 04 '20 at 06:11

score 1 · Answer 2 · answered Mar 03 '20 at 18:29

The values in the map are just an unordered sequence. To find duplicates you need to organise the values in another container in such a way that allows you to find duplicate easily, for example, copy the values (or pointers to values if the values aren't cheap to copy) into an array and sort the array.

score 1 · Answer 3 · answered Mar 03 '20 at 18:59

There is no member function of std::map, which can return duplicate based on values.

More details: https://en.cppreference.com/w/cpp/container/map

Other way you have to iterate the map atleast once as I mentioned in comments. Fill the std::map<int,std::list<int>>.

Find common values in map

3 Answers3