How can I declare a custom sort function on std::map declaration?

c++ map sort by value
std::unordered_map sort by key
c++ sort map by key
std map sort order
std map comparator c
c map comparator lambda
sort unordered_map
sort map by frequency c++

The container std::map always sorts keys based on their value. Is it possible to make it sort, for example, on the number of bits set upon declaration?

I have a function for counting set bits:

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

But I do not know how to apply it when declaring the map:

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

I've tried to put it as a third parameter in the declaration <int,int,decltype(countSetBits)>, but with no luck.

You need to wrap your function in a binary operator, like this:

#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);
    }
};

Now you can use cntBitsCmp in a declaration:

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

Here is a demo on ideone. It correctly orders 128 ahead of 3, because 3 has two bits set, while 128 has only one.

How to Sort a Map by Value in C++ – thispointer.com, In the below example we will use a comparator as lambda function that compares the 2 pais using teir second field i.e.. [](std::pair<std::string  std::sort() in C++ STL We have discussed qsort() in C. C++ STL provides a similar function sort that sorts a vector or array (items with random access). Below is a simple program to show working of sort().

Basically this could work as you want:

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
}

C++ : Map Tutorial -Part 2: Map and External Sorting Criteria , Obviously we cannot change the definition of opeartor < for std::string. Then in such scenario we should use external sorting criteria i.e. a function  The container std::map always sorts keys based on their value. Is it possible to make it sort, for example, on the number of bits set upon declaration? I have a function for counting set bits: for

Since C++11, you can also use a lambda expression instead of defining a comparison function. If you combine this with std::bitset::count instead of using your own counting function, then the code becomes rather short:

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);

Note: Similar to the solution by dasblinkenlight, I'm assuming 32-bit integers for the sake of clarity. Please adapt the code to your needs.

Code on Ideone

map with custom comparison function? - C++ Forum, I would like to write a custom comparison function object that I can pass In my hands, a function object works fine when passed to an algorithm like sort, a non-constant type, ie I can't use a constructor in the map declaration (line 35). qualified the names with "std::" instead of using the 'using' keyword,  The accepted answer makes you believe that you must use a class or a std::function as comparator. This is not true! As cute_ptr's answer shows, you can pass a function pointer to the constructor. However, the syntax to do so is much simpler than shown there:

STL Sort Comparison Function, This article is a crash course on the STL's std::sort comparison functions. For your own custom classes, you need to define our own < operator. specify the return type of the lambda, it is automatically inferred from the only return statement. The sort() function in the algorithm header can be a very useful tool to both new and experienced programmers. It's use is to sort containers like arrays and vectors. The first example is what the function looks like.

Sort a map by values in C++, In this post, we will discuss how to sort a map by values in C++. The idea is to convert the std::map into a std::vector of key-value pairs and sort that vector according to Comparison function for sorting the set by increasing order of its pair's. We have discussed map in C++ STL and multimap in C++ STL.The default behavior of these data structures is to store elements in ascending order. How to ensure reverse order or descending order when inserting elements in map and multimap.

std::sort() in C++ STL, std::sort() in C++ STL. We have discussed qsort() in C. C++ STL provides a similar function sort that sorts a vector or array (items with random access). Below is a  std::map is a sorted associative container that contains key-value pairs with unique keys. Keys are sorted by using the comparison function Compare. Search, removal, and insertion operations have logarithmic complexity. Maps are usually implemented as red-black trees.

Comments
  • If it's a normal function you also have to pass it to the constructor as a function pointer.
  • Btw, gcc has a nice set of builtins, one of which int __builtin_popcount(unsigned int) returns the number of bits set in an integer.
  • You're assuming 32-bit ints. while (i) {++n; i&=i-1;}
  • @jthill Correct. I copy-pasted the OP's code, and modified it to remove constants. I posted the code as an example, with the understanding that nobody would use this code without modifications.