Order an std::map by the absolute value of key

user_6703592 0
Viewed 210

I want to order an std::map by the absolute value of key with following code as the usual customized order

vector<int> A = {-4,4,-2,2};
auto cmp = [](int a, int b) { return abs(a) < abs(b); };
map<int, int, decltype(cmp)> m(cmp);
for (int x : A)  m[x]++;

But the result is m = {{-4,2},{-2,2}}. I don't know, why the key 4 and 2 are missing. I want to keep all values and actually I don't care about the = i.e. 4,-4 and -4,4 are both ok for me. I only what to order them when the values are different.

dictionary c++
4 Answers

Your comparison function causes your map to treat keys 4 and -4 as equivalent. Ditto for keys 2 and -2, so that explains the results you get, since keys in a map must be unique.

user_57432880

As other answers mention, your comparison operator renders the keys like 4 and -4 equal, as far as the map is concerned.

Solution

You can create your own ordering (with a custom comparison operator) to achieve what you want:

auto cmp = [](int a, int b) { 
        auto aa = abs(a);
        auto bb = abs(b);
        
        return (2 * aa + (aa == a)) < (2 * bb + (bb == b)); 
    };

outputs:

{-2, 1} {2, 1} {-4, 1} {4, 1}

Demo

Explanation

The numbers -4, -2, 2, 4 and so on are integers. Inside the comparison function, you can map them to to natural numbers and create a tie breaker for positive ones by:

  • taking the absolute of double the negative numbers
  • taking the absolute of double the positive + 1

So your keys K = {k1, k2, ... kn} behave as

K' = {k1', k2', ..., kn'} where 

     / 2 * ki, ki < 0
ki' = 
     \ 2 * ki + 1, ki > 0
user_25676830

To order the int keys as 0, 1, -1, 2, -2, 3, -3, ... change the comparator to this (live):

auto cmp = [](int a, int b) { return abs(a) != abs(b) ? abs(a) < abs(b) : a > b; };

This comparator uses lexicographical comparison with two sort keys:

  1. The absolute value of the number.
  2. The sign of the number.
user_112798790

If you check the std::map documentation from cppreference.com:

Everywhere the standard library uses the Compare requirements, uniqueness is determined by using the equivalence relation. In imprecise terms, two objects a and b are considered equivalent (not unique) if neither compares less than the other: !comp(a, b) && !comp(b, a).

Because of that, after you've already inserted -4, it will work out that neither of 4 and -4 are less than the other, so deem them equal and increment that map value. If you'd inserted 4 first, you would have had a single entry for 4 instead of -4.

Personally, I consider this confusing and would recommend using a std::map<int, int> and for (auto a : A) m[abs(a)]++;.

user_4107670
Related