Ytukyg

The problem: I need to sort a vector of strings in exact specific order. Let say we have a constant vector or a array with the exact order:

vector<string> correctOrder = {"Item3", "Item1", "Item5", "Item4", "Item2"};

Next, we have a dynamic incoming vector which will have same Items, but they maybe mixed and less in number.

vector<string> incommingVector = {"Item1", "Item5", "Item3"};

So I need to sort the incomming vector with the order like the first vector, correctOrder, and the result must be:

vector<string> sortedVector = {"Item3", "Item1", "Item5"};

I think the correct order may be represented in a different way, but can't figure out.
Can someone help me please?

You can create your own functor to sort your vector in template vector order as explained by below code :

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

using namespace std;

struct MyComparator

{

    //static const int x = 9;

  const std::vector<std::string> correctOrder{"Item1", "Item2", "Item3", "Item4", "Item5"};

  bool operator() (const std::string& first,const std::string& second )

  {

      auto firstitr = std::find(correctOrder.begin(),correctOrder.end(),first);

      auto seconditr = std::find(correctOrder.begin(),correctOrder.end(),second);

      return firstitr < seconditr;

  }

};

void printVector(const std::vector<std::string>& input)

{

    for(const auto&elem:input)

    {

        std::cout<<elem<<" , ";

    }

    std::cout<<std::endl;

}

int main()

{

  std::vector<string> incomingVector = {"Item3", "Item5", "Item1"};

  std::cout<<"vector before sort... "<<std::endl;

  printVector(incomingVector);

  std::sort(incomingVector.begin(),incomingVector.end(),MyComparator());

  std::cout<<"vector after sort...."<<std::endl;

  printVector(incomingVector);

  return 0;

}

If the default comparison is not enough (lexicographic comparison) then the simplest thing you can do is to provide the sort function with a lambda that tells it which string come first.
You can have a unordered_map<string,int> with the strings in your correctorder vector as keys and their corresponding position in the sorted array as values.

The cmp function will simply compare the values of the keys you provide in your incommingVector.

unordered_map<string, int> my_map;

for(int i = 0 ; i < correctorder.size() ; i++)

   my_map[correctorder[i]]=i;



auto cmp =[&my_map](const string& s, const string& s1){

   return my_map[s] < my_map[s1];

}   



sort(incommingVector.begin(), incommingVector.end() , cmp);

You can take advantage of std::unordered_map<std::string, int>, i.e., a hash table for mapping a string into an integer in constant time. You can use it for finding out the position that a given string occupies in your vector correctOrder in O(1), so that you can compare two strings that are in the vector incomming in constant time.

Consider the following function sort_incomming_vector():

#include <unordered_map>



using Vector = std::vector<std::string>;



void sort_incomming_vector(const Vector& correctOrder /*N*/, Vector& incomming /*M*/)

{

   std::unordered_map<std::string, int> order;



   // populate the order hash table in O(N) time

   for (size_t i = 0; i < correctOrder.size(); ++i)

      order[correctOrder[i]] = i;



   // sort "incomming" in O(M*log M) time

   std::sort(incomming.begin(), incomming.end(),

            [&order](const auto& a, const auto& b) { // sorting criterion

               return order[a] < order[b];

            }

   ); 

}

The hash table order maps the strings into integers, and this resulting integer is used by the lambda (i.e., the sorting criterion) passed to the sorting algorithm, std::sort, to compare a pair strings in the vector incomming, so that the sorting algorithm can permute them accordingly.

If correctOder contains N elements, and incomming contains M elements, then the hash table can be initialised in O(N) time, and incomming can be sorted in O(M*log M) time. Therefore, the whole algorithm will run in O(N + M*log M) time.

If N is much larger than M, this solution is optimal, since the dominant term will be N, i.e., O(N + M*log M) ~ O(N).

You need to create a comparison function that returns the correct ordering and pass that to std::sort. To do that, you can write a reusable function that returns a lambda that compares the result of trying to std::find the two elements being compared. std::find returns iterators, and you can compare those with the < operator.

#include <algorithm>



std::vector<std::string> correctOrder = {"Item1", "Item2", "Item3", "Item4", "Item5"};

// Could be just std::string correctOrder, or std::array<...> etc.



// Returns a sorter that orders elements based on the order given by the iterator pair

// (so it supports not just std::vector<string> but other containers too.

template <typename ReferenceIter>

auto ordered_sorter(ReferenceIter ref_begin, ReferenceIter ref_end) {

    // Note: you can build an std::unordered_map<ReferenceIter::value_type, std::size_t> to

    // be more efficient and compare map.find(left)->second with 

    // map.find(right)->second (after you make sure the find does not return a

    // one-past-the-end iterator.

    return [&](const auto& left, const auto& right) {

        return std::find(ref_begin, ref_end, left) < std::find(ref_begin, ref_end, right);

    };

}



int main() {

    using namespace std;

    vector<string> v{"Item3", "Item5", "Item1"};



    // Pass the ordered_sorter to std::sort

    std::sort(v.begin(), v.end(), ordered_sorter(std::begin(correctOrder), std::end(correctOrder)));

    for (const auto& s : v)

        std::cout << s << ", "; // "Item1, Item3, Item5, "

}

Note that this answer less efficient with a large number of elements, but more simpler than the solutions using an std::unordered_map<std::string, int> for lookup, but a linear search is probably faster for small number of elements. Do your benchmarking if performance matters.

Edit: If you don't want the default comparison to be used, then you need to pass as a third parameter your custom compare method, as shown in the example that exists in the linked reference.

Use std::sort and you are done:

#include <iostream>     // std::cout

#include <algorithm>    // std::sort

#include <vector>       // std::vector

#include <string>       // std::string

using namespace std;



int main () {

  vector<string> incommingVector = {"Item3", "Item5", "Item1"};



  // using default comparison (operator <):

  std::sort (incommingVector.begin(), incommingVector.end());



  // print out content:

  std::cout << "incommingVector contains:";

  for (std::vector<string>::iterator it=incommingVector.begin(); it!=incommingVector.end(); ++it)

    std::cout << ' ' << *it;

  std::cout << 'n';



  return 0;

}

Output:

incommingVector contains: Item1 Item3 Item5