Welcome to MLink Developer Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
240 views
in Technique[技术] by (71.8m points)

C++ unordered_map weird behaviour

I was solving leetcode problem (Pairs of Songs With Total Durations Divisible by 60) and my solution below uses a map, when I change it to an unordered_map and print the elements inside the loop; the number of elements are much more than the input

class Solution {
public:
    int numPairsDivisibleBy60(vector<int>& time) {
        map<int, int> mod_d;
        
        for(auto el : time) {
            if(mod_d.count(el % 60) == 0) {
                mod_d[el % 60] = 1;
            }else mod_d[el % 60]++;
        }
        
        int ans = 0, i = 1;
        //cout << "Size: " << mod_d.size() << "
";
        for(auto el : mod_d) {
            int f = el.first, s = el.second;
            cout << f << " " << 60 - f << "
";
            ans += mod_d[(60 - f) % 60] * (((60 - f) % 60) == f ? s - 1 : s);
        }
        
        return ans / 2;
    }
};

Sample Input Test: [15, 63, 451, 213, 37, 209, 343, 319]

And the output is as follows:

3 57
15 45
19 41
29 31
31 29
33 27
37 23
41 19
43 17
45 15
57 3

The number of elements printed should be only 8 inside the loop, but with an unordered_map, the elements are much more.

The code that is not working well is below:

class Solution {
public:
    int numPairsDivisibleBy60(vector<int>& time) {
        unordered_map<int, int> mod_d;
        
        for(auto el : time) {
            if(mod_d.count(el % 60) == 0) {
                mod_d[el % 60] = 1;
            }else mod_d[el % 60]++;
        }
        
        int ans = 0, i = 1;
        //cout << "Size: " << mod_d.size() << "
";
        for(auto el : mod_d) {
            int f = el.first, s = el.second;
            cout << f << " " << 60 - f << "
";
            ans += mod_d[(60 - f) % 60] * (((60 - f) % 60) == f ? s - 1 : s);
        }
        
        return ans / 2;
    }
};

The only difference is the usage of unordered_map instead of a map

And it prints the elements wrongly as:

19 41
43 17
37 23
33 27
31 29
29 31
3 57
41 19
15 45
41 19
3 57
29 31
31 29
57 3
33 27
37 23
43 17
17 43
19 41
23 37
27 33

Anyone knows why is this odd behavior happening?


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Answer

0 votes
by (71.8m points)

Alright I now understand, thank you so much all for the help. As per this link that shows the different ways to access a map, I see that using [] operator creates the elements if they are not there in the map and that is my mistake. When I should use std::map::at to retrieve map element

Fix

Checking if the element exist at first and using at() to access it

class Solution {
public:
    int numPairsDivisibleBy60(vector<int>& time) {
        unordered_map<int, int> mod_d;

        for(auto el : time) {
            if(mod_d.count(el % 60) == 0) {
                mod_d[el % 60] = 1;
            }else mod_d[el % 60]++;
        }

        int ans = 0, i = 1;
        cout << "Size: " << mod_d.size() << "
";
        for(auto el : mod_d) {
            int f = el.first, s = el.second;
            cout << f << " " << i++ << "
";
            if(mod_d.count((60 - f) % 60) > 0) ans += mod_d.at((60 - f) % 60) * (((60 - f) % 60) == f ? s - 1 : s);
        }

        return ans / 2;
    }
};

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome to MLink Developer Q&A Community for programmer and developer-Open, Learning and Share
...