C++ Comparator function to specifiy specific key ordering for map?

Question

Question: How would you write a function to do a custom comparator for a map constructor to create a specific order for keys?

I have the following string keys:

"a", "d", "i", "n", "ns", "ne", "vl", "rr"

I am using a map to write values for those keys. But I need them to be ordered in that exact order as stated above. Map usually creates the order:

a d i n ne ns rr vl

How do I write a comparator function that I can send to the map constructor so I can keep this order?

Here's what I've resorted to for now

vector<pair<string, string>>({ { "a","" },{ "d","" },{ "i","" },{ "n","" },{ "ns","" },{ "ne","" },{ "vl","" },{ "rr","" }, { "","" } });

...and then I do a bunch of find_if calls. If it is found, I add the value to the pair. If not, I create a new pair (at the beginning). I do it at the beginning so I can just return "" if the key does not exist. Well, it all works except that I need to sort the keys that I don't list above, as any key can be added. Also, my program crashes when I try to add a non-existent key. Gotta debug that... but this way of doing it is confusing. Using a map with a bit of specific sorting would be perfect for my needs (any keys added during runtime should be sorted by a default comparison as well to maintain an order. These "unknown" (future-added) keys can be sorted however).

Reason that I "want this" (asked in comments): I need to, at the final step of my program, output a string like this:

",a=legato,d=dn,i=12,n=A3" 

etc. They need to be in a specific order because I need to later use regex (in a separate program) to manipulate this string. The order is important for specified keys. The order must be also fixed for unspecified keys... because of regex.

Answer 1

This function sorts a set based on an input vector for ordering

A good friend and great programmer wrote this answer for me. This is the most efficient solution according to ideone.com. This is not the answer to the original question, but it is the answer to the actual problem.

//first param is the container you want to sort
//second param is the container that holds the order of things
vector<pair<string,string>> KeySort(map<string,string> s, const vector<string>& order){
    vector<pair<string,string>> res;
    for (const auto& it : order) {
        auto needle = s.find(it);
        if (needle != s.end()) {
            res.emplace_back(move(*needle));
            s.erase(needle);
        }
    }
    for (auto&& it : s) res.emplace_back(move(it));
    return res;
}

ideone benchmark test: https://ideone.com/GYsiM8

ideone example use: https://ideone.com/eAU5US

// create vector holding desired ordering
vector<string> ord({ "a", "d", "i", "n", "ns", "ne", "vl", "rr" });

// create the map
map<string,string> MyMap = { {"a","legato"}, {"vl","4"}, 
{"i","2"}, {"rr","3"}, {"z","unspecified1"}, {"b","unspecified2"}};

// sort the vector
vector<pair<string,string>> out = KeySort(MyMap, ord);

output: a=legato i=2 vl=4 rr=3 b=unspecified2 z=unspecified1

Answer 2

Sorts a vector of pairs based on a vector holding key order

This is not the answer to the original question, but a solution to the problem described. See my other answer for a faster version of this concept.

RUN: https://ideone.com/8ICRwZ

#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <algorithm>
using namespace std;

// create vector holding desired ordering
vector<string> order({ "a", "d", "i", "n", "ns", "ne", "vl", "rr" });

// create sort function for vector of pairs
bool comparator(const pair<string, string> &s1, const pair<string, string> &s2) {
    // find() - it.begin() gives you the index number. 
    int a = find(order.begin(), order.end(), s1.first) - order.begin();
    int b = find(order.begin(), order.end(), s2.first) - order.begin();
    return a < b; // lower index < higher index
};

int main() {
    // create the map
    map<string,string> MyMap = { { "a","legato" }, { "vl","3" }, {"i", "3"}, { "rr","2" } };

    // convert map into vector of pairs
    vector<pair<string,string>> vp;
    for (auto& it : MyMap) vp.push_back({ it.first, it.second });

    // sort the vector
    sort(vp.begin(), vp.end(), comparator);

    // put the vector pairs into a string format
    for (auto& it : vp) cout << it.first << "=" << it.second << " ";

    return 0;
}

output: a=legato i=3 vl=3 rr=2

Answer 3

This is how you would create comparator function for map to create a specific sort order for a number of keys.

The inspiration from other answers allowed me to write my own answer that addresses my question exactly and in the best way possible (IMO).

RUN: https://ideone.com/7H5CZg

#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <algorithm>
using namespace std;

// create vector holding desired ordering
vector<string> order({ "a", "d", "i", "n", "ns", "ne", "vl", "rr" });

// create sort function for map   
struct my_comparator {
    bool operator()(const string &s1, const string &s2) {
        // find() - it.begin() gives you the index number. 
        int a = find(order.begin(), order.end(), s1) - order.begin();
        int b = find(order.begin(), order.end(), s2) - order.begin();
        return a < b; // lower index < higher index
    }
};

int main() {
    // create the map
    map<string,string, my_comparator> MyMap = { { "a","legato" }, { "i","3" }, { "vl","3" }, { "rr","2" } };

    // output map
    for (auto& it : MyMap) cout << it.first << "=" << it.second << "  ";

    return 0;
}

output: a=legato i=3 vl=3 rr=2

---

UPDATE: This will usually be faster, it uses a map instead of vector to look up key order.

You can apply this way of doing things to the other answers as well.

#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <algorithm>
using namespace std;

// using a map is faster in most cases (with more keys and such)
map<string, int> maporder({ {"a", 1}, {"d", 2}, {"i", 3}, {"n", 4}, {"ns", 5}, {"ne", 6}, {"vl", 7}, {"rr", 8} });

// create sort function for map   
struct mapcomp {
    bool operator()(const string &s1, const string &s2) {
         // compares ints by looking them up with the input string
        return maporder[s1] < maporder[s2];
    }
};

int main() {
    // create the map
    map<string,string, mapcomp> MyMap = { { "a","legato" }, { "i","3" }, { "vl","3" }, { "rr","2" } };

    // output map
    for (auto& it : MyMap) cout << it.first << "=" << it.second << "  ";

    return 0;
}

Answer 4

Looking at the edit to the question explaining why this is wanted, I'd recommend instead using a map with default ordering, then at the time you want to output the values consult a different list:

std::vector<std::string> ordering = { "a", "d", "i", "n", "ns", "ne", "vl", "rr" };
for (const auto& key : ordering)
    ...output the_map[key]...

Anyway, if you insist on a map with different ordering, you can special-case as necessary:

struct WeirdLess
{
    bool operator<(const std:string& lhs, const std::string& rhs) const
    {
        if (lhs == "ne" && rhs == "ns" ||
            lhs == "ns" && rhs == "ne" ||
            lhs == "rr" && rhs == "vl ||
            lhs == "vl" && rhs == "rr")
            return rhs < lhs;
        return lhs < rhs;
    }
};

std::map<std::string, std::string, WeirdLess> my_map;

It's not very scalable though, if you end up with hundreds of entries in the map and half of those need special casing. Trying to come up with some logic capturing why particular strings are earlier - or at least an heuristic for recognising them - that may be a better idea. For example:

    bool operator<(const std:string& lhs, const std::string& rhs) const
    {
        if (lhs.size() == 2 && rhs.size() == 2 && lhs[0] == rhs[0])
            return rhs < lhs;
        return lhs < rhs;
    }

Answer 5

You specify the comparator that map uses for ordering keys as a template parameter. So your map declaration looks like:

std::map<string, value_type, my_comparator> my_map;

The comparator is something you can define that takes two key_type parameters a and b, and then returns true if a comes before b (and false otherwise). An example of this would be:

struct my_comparator {
    bool operator()(const string &a, const string &b) {
        // Return true if a comes before b.
    }
}

To achieve the ordering that you have specified in your question, you could do something along the lines of the below. I have used std::tuple to ensure the strict ordering criteria is met.

bool operator()(const string &a, const string &b) {
    auto a_tuple = std::make_tuple(a == "a", a == "d", a == "i", ..., a);
    auto b_tuple = std::make_tuple(b == "a", b == "d", a == "i", ..., a);

    return a_tuple < b_tuple;
}

As this has a and b in the last elements of the tuple, it will sort by these if it does not match one of your pre-defined strings.