如何按照特定的预定顺序对字符串向量进行排序？

Question

问题：我需要按照精确的顺序对一个字符串向量进行排序。假设我们有一个具有精确顺序的常量向量或数组：

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

接下来，我们有一个动态的输入向量，其中的项可能被混合并且数量较少。

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

所以我需要按照第一个向量"correctOrder"的顺序对"incomming"向量进行排序，结果必须为：

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

我认为正确的顺序可能以不同的方式表示，但无法弄清楚。 有人能帮我吗？

- Rosen Karadinev

---

使用std::sort进行实际排序是一个不错的开始。我还建议阅读有关lambda表达式，以提供自定义比较函数，然后将其传递给std::sort使用。 - Some programmer dude

@gsamaras 可能吧。或者OP想要使用向量correctOrder中的元素来获取元素的相对位置？我不知道，从问题中并不是很清楚。 - Some programmer dude

这是正确的，gsamaras。我需要相对于第一个向量进行排序。 - Rosen Karadinev

我看到所有的答案都是离线的。有没有更有效的在线算法？ - Andrew Scott

虽然所有的答案都告诉你如何在O(N * M log M)的时间内解决问题，但是你可以通过使用堆来实现O(log N * M log M)的时间复杂度，因为它们只需要log N的时间来插入。请注意，无法查找中间的值，因为这样你将不得不花费M的时间。 - Andrew Scott

Answer 1

如果默认比较（词典排序）不够用，那么最简单的方法就是提供一个lambda函数告诉sort函数哪个字符串应该排在前面。你可以使用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);

- Davide Spataro

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 会使用 lambda 函数（即排序标准）来比较向量 incomming 中的一对字符串，并根据比较结果对它们进行排序。

如果 correctOrder 包含 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

您可以创建自己的函数对象来按照模板向量顺序对向量进行排序，如下面的代码所示：

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

- PapaDiHatti

---

在我的情况下，确切地有8个元素，这个解决方案非常完美。非常感谢！ - Rosen Karadinev

Answer 4

你需要创建一个比较函数，返回正确的排序顺序，并将其传递给std::sort。为此，您可以编写一个可重用函数，返回一个lambda，比较试图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> 进行查找的解决方案更简单。但是，在元素数量较小的情况下，线性搜索可能更快。如果性能很重要，请进行基准测试。

- palotasb

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

输出：

incommingVector 包含：Item1 Item3 Item5

- gsamaras

---

好的，但是假设正确的顺序是{"Item4", "Item1", "Item3", "Item2", "Item5"}，它会像这样工作吗？ - Rosen Karadinev

@RosenKaradinev，为此您需要使用自定义比较函数，并将其作为std::sort()的第三个参数传递。请参阅我在答案中提供的参考资料以获取更多信息。 - gsamaras

我认为你误读了问题，而且 OP 没有使用最佳示例（对于问题中的示例，简单的排序可以解决，但在一般情况下不行）。 - 463035818_is_not_a_number

不是问题的答案 - NiVeR

感谢 @RosenKaradinev，我现在明白问题了！ - Neil Gatenby