Как отсортировать вектор строк в определенном заданном порядке?

Question

Проблема: мне нужно отсортировать вектор строк в точном определенном порядке.Допустим, у нас есть постоянный вектор или массив с точным порядком:

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

Далее, у нас есть динамический входящий вектор, который будет иметь те же элементы, но они могут быть смешанными и меньше по числу.

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

Так что мне нужно отсортировать вектор incomming по порядку, как первый вектор, correctOrder, и результат должен быть:

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

Я думаю, что правильный порядок может бытьпредставлены по-другому, но не могу понять.Может кто-нибудь помочь мне, пожалуйста?

Answer 1

Вы можете создать свой собственный функтор для сортировки вектора в порядке шаблона вектора, как описано ниже кодом:

#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;
}

Answer 2

Вы можете воспользоваться std::unordered_map<std::string, int>, то есть хеш-таблицей для , отображающей строку в целое число в постоянное время.Вы можете использовать его для определения позиции, которую данная строка занимает в вашем векторе correctOrder в O(1), так что вы можете сравнить две строки, которые находятся в векторе incomming в постоянное время.

Рассмотрим следующую функцию 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];
            }
   ); 
}

Хеш-таблица order отображает строки в целые числа, и полученное в результате целое число используется лямбда-выражением (т. Е. Критерием сортировки) передается алгоритму сортировки std::sort для сравнения парных строк в векторе incomming, чтобы алгоритм сортировки мог соответствующим образом их переставить.

Если correctOder содержитN элементов, а incomming содержит M элементов, тогда хеш-таблицу можно инициализировать за O(N) время, а incomming можно отсортировать за O(M*log M) время.Таким образом, весь алгоритм будет выполняться за O(N + M*log M) времени.

Если N намного больше, чем M, это решение является оптимальным, поскольку доминирующим членом будет N, то есть O(N + M*log M) ~ O(N).

Answer 3

Если сравнение по умолчанию недостаточно (лексикографическое сравнение), то самое простое, что вы можете сделать, - это предоставить функции сортировки лямбда , которая сообщает, какая строка стоит первой.Вы можете иметь unordered_map<string,int> со строками в векторе correctorder в качестве ключей и их соответствующую позицию в отсортированном массиве в качестве значений.

Функция cmp просто сравнитзначения ключей, которые вы предоставляете в 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);

Answer 4

Вам необходимо создать функцию сравнения, которая возвращает правильный порядок и передает его в std::sort.Для этого вы можете написать многократно используемую функцию, которая возвращает лямбду, которая сравнивает результат попытки с std::find двумя сравниваемыми элементами.std::find возвращает итераторы, и вы можете сравнить их с оператором <.

#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, "
}

Обратите внимание, что этот ответ менее эффективен при большом количестве элементов, но более прост, чем решения, использующие std::unordered_map<std::string, int> для поиска, но линейный поиск, вероятно, быстрее для небольшого числа элементов.Проведите сравнительный анализ, если производительность имеет значение.

Answer 5

Редактировать: Если вы не хотите использовать сравнение по умолчанию, вам нужно передать в качестве третьего параметра свой пользовательский метод сравнения, как показано в примере, который существует в связанной ссылке.

Используйте std::sort и все готово:

#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;
}

Вывод:

commingVector содержит: Item1 Item3 Item5