c++sorting

Sorting objects by key matching a specific sequence

I have a sequence of structs, say

struct Foo
{
    std::string key;
    int value;
};

The data points represented by these structs can arrive in any order, but need to go out in a specific order. I would represent that order by a sequence of keys, like so:

const std::vector<std::string> keySequence = {"thisMustBeFirst", "thenThisOne", "andThenThatOne"};

Now given a std::vector<Foo> and my hardcoded key sequence, I want to arrange my input data so that each object is at the position of its key in the required sequence. Precondition guarantees that all keys actually exist in the input, so the sorting is my only concern here.
My first plan was std::sort but it kinda feels like this might be the wrong approach, because I can't find an immediately obvious comparison function to give it. Am I maybe thinking about this the wrong way?

There are no hard requirements about the data structures, so maybe there's a different design that works better here?

I'd appreciate any and all suggestions.

Solution

  • You can implement the following less-than comparator for std::sort:

    1. Find the index of the first key in keySequence, let's call it index1.
    2. Find the index of the second key in keySequence, let's call it index2.
    3. Return index1 < index2.

    Note:
    If keySequence is long, searching through it to get the index of the key might hurt your performance.
    In this case you can first build a map from key to index, and use it in stages 1 and 2 above.
    Gegarding which map to use: 2 obvious options are std::map and std::unordered_map. Each has its advantages and disadvatages and choosing between them should be done based on profiling.