Как объявить пользовательскую функцию сортировки в объявлении std :: map?

Question

std :: map всегда сортирует ключи по значению. Можно ли его сортировать, например, по количеству бит, установленным после объявления?

У меня есть функция для подсчета установленных бит:

for(size_t i = 0; i < CHAR_BIT * sizeof value; ++i, value >>= 1) { 
    if ((value & 1) == byteState) ++num_bits; 
    } 

, но я не знаю, как применить его при объявлении карты.

std::map<int, int> myMap = { 
    {1,2}, 
    {3,4}, 
    //... 
} 

Я пытался поставить его в качестве третьего параметра в объявлении <int,int,decltype(countSetBits)> не повезло.

Answer 1

Вам необходимо обернуть функцию бинарного оператора, например:

#include <iostream> 
#include <map> 
#include <algorithm> 

int cntBits(int value) { 
    int num_bits=0; 
    for(size_t i = 0; i < 32 ; ++i, value >>= 1) { 
     if ((value & 1) == 1) ++num_bits; 
    } 
    return num_bits; 
} 

struct cntBitsCmp { 
    bool operator()(int a, int b) { 
     return cntBits(a) < cntBits(b); 
    } 
}; 

Теперь вы можете использовать cntBitsCmp в объявлении:

std::map<int,int,cntBitsCmp> myMap= { 
    {128,2}, 
    {3,4}, 
    ... 
}; 

Вот demo on ideone. Он правильно заказывает 128 перед 3, потому что 3 имеет два бита, а 128 - только один.

Answer 2

В основном это может работать, как вы хотите:

bool comp(int x , int y){ 
    return __builtin_popcount(x) < __builtin_popcount(y); 
} 
int main(){ 
    bool(*fn_pt)(int,int) = comp; 
    std::map<int, int, bool(*)(int,int) > myMap (fn_pt); 
    myMap[7]=11; 
    myMap[8]=12; 
    cout<<myMap.begin()->first<<endl; // you get 8 instead of 7 
}