c++dictionarysortingcomparator

Sorting keys in a dictionary with multiple keys while keeping certain keys together


I have a Dictionary with keys of type Setting, where setting is a struct with members mCategory (String), mIndex (int), and mDescription (String). Some of the keys are unique - there will be at most one with the same mCategory. These have mIndex set to -INF and their descriptions are arbitrary.

The other keys will follow a sequence, e.g., items in mCategory Books can have mIndex 1, 2, 3 etc. Descriptions are not arbitrary for the latter. They are prefixed with mCategory + mIndex. I want the keys to be sorted by description, until we are at a non-unique mCategory. I want to sort the keys with the same mCategory by mIndex because sorting the whole thing lexicographically would place Book 10 after Book 1. This is what I want - but I cannot figure out how to make it sort the way I want

Description Index Type
ABC -INF X
BCD -INF Y
CDE -INF Z
D 1 1 D
D 2 2 D
D 3 3 D
D 4 4 D
.. .. ..
D 10 10 D
EGH -INF E
GHI .. F
K 1 .. K
K 2 .. K

This is the comparator I wrote but this is clearly not working:

bool operator()(const myStruct& rLeft, const myStruct& rRight) const
{
        if (rLeft.mCategory == rRight.mCategory)
             return rLeft.mIndex < rRight.mIndex;
        else return rLeft.mDescription.CompareNoCase(rRight.m_sDescription) < 0;  
}

Clarification: I don't want to sort by uniqueness, I want to sort by description until sorting by description finds a non-unique category, then sort that subsequence by index, then continue sorting by description until another non-unique subsequence occurs, and so on. I fixed the example to reflect that.


Solution

  • The easiest way to ensure that you have a valid comparison over multiple criteria is to always use std::tuple::operator<, synthesizing values that represent your priority of order.

    bool operator()(const myStruct& rLeft, const myStruct& rRight) const
    {
        return std::tuple{ lhs.index == -1 ? lhs.description : lhs.type, lhs.index }
             < std::tuple{ rhs.index == -1 ? rhs.description : rhs.type, rhs.index };
    }
    

    This orders elements of a non-unique category together, by ignoring their description, and uses the index to order within the category.