Sorting Vector of string from another vector of strings

Hello,

I am having a bit of brain freeze today and cannot figure out the best way to implement this using the STL algorithms. I have these two vectors

Code:

---

       
vector<string> valuesToSort = {"aa", "cc", "bb"};
vector<string> orderToFollow = {"cc", "bb", "gg", "ii", "aa"};

---

I want to sort valuesToSort by orderToFollow. So, using orderToFollow, valuesToSort will be modified to:

Code:

---

valuesToSort = {"cc", "bb", "aa"};

---

Or if the values were the other way round:

Code:

---

       
vector<string> valuesToSort =  {"cc", "bb", "gg", "ii", "aa"};
vector<string> orderToFollow = {"aa", "cc", "bb"};

---

valuesToSort would be:

Code:

---

valuesToSort = {"aa", "cc", "bb", "gg", "ii"};

---

So if a value that do not exist in the valuesToSort their position is maintained relative. I am thinking of stable_sort with a comparitor but not quite sure how to implement it. Heres what I have so far:

Code:

---

        //values are distinct
        vector<string> valuesToSort = {"aa", "cc", "bb"};
        vector<string> orderToFollow = {"cc", "bb", "gg", "ii", "aa"};


        //vector<string> orderToFollow = {"aa", "cc", "bb"};
        //vector<string> valuesToSort = {"cc", "bb", "gg", "ii", "aa"};


        vector<string> newOrder;

        for (int i = 0; i < orderToFollow.size(); ++i)
        {
                auto val = find(valuesToSort.begin(), valuesToSort.end(), orderToFollow[i]);
                if (val != valuesToSort.end())
                {       
                        iter_swap(valuesToSort.begin() + i, val);
                }
        }

        cout << "Order to follow:" << endl;
        for (auto i : orderToFollow) cout << i << "\t";
        cout << endl << endl;

        cout << "Values to sort:" << endl;
        for (auto i : valuesToSort) cout << i << "\t";
        cout << endl<< endl;

        cout << "New order:" << endl;
        for (auto i : newOrder) cout << i << "\t";
        cout << endl<< endl;

---

This current implementation goes out of bounds on the iter_swap.

All the strings when being searched should be compared case insensitive and there will never be any duplicates of a string in any vector, they will always be unique. So this could be a set container.

By any chance, would you be able to combine them as a pair or say, as members of an object?

I am currently looking into using a multi_index conatiner:

Code:

---

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index/composite_key.hpp>

using boost::multi_index_container;
using namespace boost::multi_index;

struct NameOrder
{
        explicit NameOrder(std::wstring name, unsigned int pos) : m_Name(name), m_Pos(pos){}
       
        std::wstring m_Name;
        unsigned int m_Pos;
};

typedef multi_index_container<
        NameOrder,
        indexed_by<               
                                ordered_unique<member<NameOrder, unsigned int, &NameOrder::m_Pos> >
        >
> NAME_ORDER;

int _tmain(int argc, _TCHAR* argv[])
{
        using namespace std;

        //values are distinct
        vector<string> valuesToSort = {"aa", "cc", "bb"};
        vector<string> orderToFollow = {"cc", "bb", "gg", "ii", "aa"};

        NAME_ORDER order;


        for (int i = 0; i < valuesToSort.size(); ++i)
        {
                auto val = find(orderToFollow.begin(), orderToFollow.end(), valuesToSort[i]);
                if (val != orderToFollow.end())
                {
                        order.insert(NameOrder(*val, std::distance(orderToFollow.begin(), val)));
                }
        }
}

---

Conceptually, these two vectors represent two independent collections on different business objects. They can't really be refactored easily as you say.

Do you have to sort the vector in-place? You anyway need to convert the original vector to an unordered set, for performance reasons. So, you might as well empty the original vector and use it.

Hmm... Would it be possible to just `std::sort` and the appropriate functor?

I don't really see any sort of pattern that would make std::sort a good choice. I did however have a think on it, and one way to do it would be to copy from order to follow.

Code:

---

if (vectorToSort.size() > orderToFollow.size())
{
    // Push elements not in orderToFollow to the end.
    auto mark = remove_if(vectorToSort.begin(), vectorToSort.end(), [&](string n) {
        return find(orderToFollow.begin(), orderToFollow.end(), n) == orderToFollow.end();
    });
    // Compute how much of the order to follow to copy.
    auto copyEnd = std::distance(vectorToSort.begin(), mark);
    // Copy.
    vectorToSort.assign(orderToFollow.begin(), orderToFollow.begin()+copyEnd);
}
else
{
    // Remove elements that will not be sorted. Note: this is possibly destructive to the orderToFollow vector.
    // Copy it first to preserve the original order.
    auto mark = remove_if(orderToFollow.begin(), orderToFollow.end(), [&](string n) {
        return find(vectorToSort.begin(), vectorToSort.end(), n) == vectorToSort.end();
    });
    // ...
    // Assign the sorted vector.
    vectorToSort.assign(orderToFollow.begin(), mark);
}

---

I probably skipped a few steps because I'm too lazy to do it.

I still think this is bad. I would like to use an unordered set instead. I really don't see how this is "sorted order".

Well, I did specify "appropriate functor". I think std::sort expects a binary functor that returns a boolean. So all you have to do for your array is write a function that takes two valid entries of the array and returns a boolean indicating "less than".

The core of the logic would come from this:

Code:

---

std::vector<std::string> orderToFollow{ "cc", "bb", "gg", "ii", "aa" };

---

For the sake of performance the logic can of course be refactored but the idea is, you could greatly simplify your problem by just creating a simple function that takes two strings and returns the appropriate boolean value.

Perhaps create a map for ordertofollow consisting of pairs of string, index. Then use a lambda function or comparator to find indexes for both strings of a compare. If the string (key) is not in the map, use size as the index value (so all missing keys will have the same index). To preserve the order of keys not in the map, use std::stable_sort().

That idea worked for me when I tested it, rcgldr... though I did simplify it. My lambda returned false if either value to sort wasn't a key.

Quote:

---

Originally Posted by rcgldr

Perhaps create a map for ordertofollow consisting of pairs of string, index. Then use a lambda function or comparator to find indexes for both strings of a compare. If the string (key) is not in the map, use size as the index value (so all missing keys will have the same index). To preserve the order of keys not in the map, use std::stable_sort().

---

Ha, I actually thought of this as well. You could easily use `std::map` or `std::unordered_map` to accomplish this goal easily.

I must admit, this was a very interesting problem to try and solve!

Quote:

---

Originally Posted by whiteflags

That idea worked for me when I tested it, rcgldr... though I did simplify it. My lambda returned false if either value to sort wasn't a key.

---

std::stable_sort() does a compare(right object, left object), expecting it to return the result of right object < less object. Returning false means the left object is less than or equal to the right object (meaning objects are in order, left before right). If right object string is found, but left object string is not found, then the lambda should return true.

Quote:

---

Originally Posted by rcgldr

std::stable_sort() does a compare(right object, left object), expecting it to return the result of right object < less object. Returning false means the left object is less than or equal to the right object (meaning objects are in order, left before right). If right object string is found, but left object string is not found, then the lambda should return true.

---

Then I guess the only question is, have you written tests? XD

Quote:

---

Originally Posted by rcgldr

std::stable_sort() does a compare(right object, left object), expecting it to return the result of right object < less object.

---

Quote:

---

Originally Posted by MutantJohn

Then I guess the only question is, have you written tests?

---

I'm not sure what you mean. I've looked at the actual code in <algorithm>, and I've also stepped through the code. In general STL expects a compare function to be a less than compare. In order for stable_sort to be stable, it only reorders data if a left object is greater than a right object, otherwise it leaves the objects in place. Since the compare is a less than compare, it swaps the parameters from what you would usually expect, to compare for right object less than left object, which is the equivalent of not(left object less than or equal to right object), if the result is true, the objects are out of order.

Well, it was largely a joke. Yes, you are probably right but in my mind, you never know until you actually run the code and see what you get.

OP, I don't know if we confused you or not but in C++ and any other non-functional programming context, a "functor" is synonymous with "callable object". So these would be your function pointers, your lambdas, your std::function's, your objects that overload operator(). In this case, std::sort expects a "binary" one which is a fancy way of saying "two arguments", in this case two adjacent array entries. By focusing your attention on writing the callable object, you've massively simplified your problem while also still relying on the STL.

I don't know if that was redundant information but I haven't seen the OP post since so I was thinking maybe we scared them off with our high highfalutin programmin' talk.