问如何将字符串向量按特定的预定顺序排序？
EN

Stack Overflow用户

提问于 2018-11-23 02:05:08

回答 5查看 1.9K关注 0票数 8

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

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

接下来，我们有一个动态输入向量，它将有相同的项目，但它们可能是混合的，而且数量较少。

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

因此，我需要按照顺序排序incomming向量，就像第一个向量，correctOrder，结果必须是：

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

我认为正确的顺序可以用另一种方式表示，但无法理解。有人能帮帮我吗？

c++

string

algorithm

sorting

vector

回答 5

Stack Overflow用户

回答已采纳

发布于 2018-11-23 02:45:01

您可以创建自己的函子，按照模板向量顺序对矢量进行排序，如下代码所解释：

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

票数 3

Stack Overflow用户

发布于 2018-11-23 02:12:12

如果默认的比较还不够(词汇表比较)，那么您可以做的最简单的事情就是为排序函数提供一个兰卜达，它告诉它哪个字符串放在第一位。您可以有一个unordered_map，其中字符串在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);

票数 10

Stack Overflow用户

发布于 2018-11-23 02:21:07

您可以利用std::unordered_map，即用于在恒定时间内将字符串映射为整数的哈希表。您可以使用它来找出给定字符串在向量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];
            }
   ); 
}