4

容器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)>，但没有运气。

4

4 回答 4

8

您需要将函数包装在二元运算符中，如下所示：

#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},
    ...
};

这是关于 ideone 的演示。它正确地将 128 排在 3 之前，因为 3 设置了两位，而 128 只有一位。

于 2013-03-23T15:26:39.910 回答
2

从C++11开始，您还可以使用lambda 表达式而不是定义比较函数。如果将其与std::bitset::count结合使用，而不是使用您自己的计数函数，则代码会变得相当短：

auto comp = [](int a, int b) { return std::bitset<32>(a).count() < std::bitset<32>(b).count(); };
std::map<int, int, decltype(comp)> m(comp);

注意：类似于Sergey 的解决方案，为了清楚起见，我假设为 32 位整数。请根据您的需要调整代码。

Ideone 上的代码

于 2018-12-13T10:36:32.050 回答
1

基本上这可以按你的意愿工作：

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
}
于 2013-03-23T15:32:04.667 回答
0

当我将我的函数包装在一个二元运算符中并使用它通过字符串（键）的长度对我的地图进行排序时，一切都很好并且它工作正常。但是，我没有意识到它影响了 maps find() 函数。而不是找到等于字符串的键，而是找到与键具有相同字符串长度的键！

于 2022-01-14T12:59:38.173 回答