C++向量双侧排序

Question

我有一个由字符串和整数（计数）组成的向量，我按照计数排序了所有内容，但是如果列表中有2个或更多的重复项，则还必须对字符串进行排序。例如;

3 trial 2 yummy 2 abc

因此，在列表中有2个2时，abc必须排在yummy之前。我的代码如下：

vector<pair<string, int> > values(hash_table.begin(), hash_table.end());

sort(values.begin(), values.end(), sort_reverse);


bool sort_reverse(const pair<string, int> &a, const pair<string, int> &b) {
  return a.second > b.second;
}

- Jason

Answer 1

您可以通过使用大于比较符号而不是默认的小于符号来反转任何范围的排序：

std::sort(values.begin(), values.end(), std::greater<std::pair<string, int>>());

或者，您可以反转迭代的顺序：

std::sort(values.rbegin(), values.rend());

编辑 如果您想更改比较标准，以通过对成对的second先进行词典排序，然后按其first进行排序，您可以提供自己的比较函数。它仍必须满足上面示例中的严格弱序列。使用std::tie实现词典比较非常简单：

#include <tuple>

template<typename T1, typename T2>
struct pair_backwards_greater
{
  bool operator()(const std::pair<T1, T2>& lhs, const std::pair<T1, T2>& rhs) const
  {
    return std::tie(lhs.second, lhs.first) > std::tie(rhs.second, rhs.first);
  }
};

那么

std::sort(values.begin(), values.end(), pair_backwards_greater<string, int>());

您也可以选择使用简单的lambda表达式而不是手写函数对象：

你也可以使用一个简单的lambda表达式，而不是手写函数对象：

  std::sort(values.begin(), values.end(),
            [](const std::pair<std::string, int> &lhs, const std::pair<std::string, int> &rhs) 
            {
              return std::tie(lhs.second, lhs.first) > std::tie(rhs.second, rhs.first); 
            }  
           );

std::tie需要C++11库的支持，但在boost::tie和std::tr1::tie中有C++03的替代实现。Lambda表达式需要C++11语言支持。

- juanchopanza

---

只是为了检查班级评分员是否在关注，使用+1或rbegin()和rend()。 - WhozCraig

抱歉，我不明白你的意思。实际上，我正在根据它们的计数对元素进行排序。如果有两个或更多元素具有相同的计数，我只想对字符串进行排序。因此，在这种情况下，您的解决方案并不能真正解决我的问题。 - Jason

@Jason，“their count”是什么意思？据我所知，这可以解决问题。 - juanchopanza

所以有两对。第一对->“test”出现了2次，第二对->“asd”也出现了2次。起初我是根据它们的出现次数进行比较的，但现在我必须根据它们的出现次数和字母顺序进行比较。 - Jason

@Jason 啊，好的，所以你想先按照int进行比较，然后再按照string比较？我会编辑我的回答。 - juanchopanza

Answer 2

要同时按两个字段排序：

bool sort_pair(const std::pair<std::string, int> &a, const std::pair<std::string, int> &b) 
{
    return (a.second > b.second) ||  
        ( 
            (a.second == b.second)  &&
            (a.first > b.first)
    );
}

void sortVector(std::vector<std::pair<std::string, int> >& values)
{
    std::sort(values.begin(), values.end(), sort_pair);
}

另请参见 现有 条目。

- Keith

---

是的，我正是在寻找这个的 :D - P0W

@P0W 没错；确实，对于 pair<> 来说，排序是规范的，只是通常主要排序会基于 first 而不是 second。 - Keith

Answer 3

你需要考虑数值本身。

bool sort_reverse(const pair<string, int> &a, const pair<string, int> &b) {
    return (a.second > b.second) || ((a.second == b.second) && (a.first > b.first));
}

- Alex

---

为什么这样是错的？他正在寻找像这样的排序： 1：“3 trail” 2：“2 abc”（由于前导“a”，有2个条目） 3：“2 yummy”（由于前导“y”，有3个条目） - Alex

感谢再次点赞；) 我真的不知道为什么会被踩...没有评论 ：P @Jason：没问题，不客气。 - Alex

因为它不满足排序算法所需的严格弱序关系，这是技术上未定义的行为。 - juanchopanza

这是不行的；正如@juanchopanza所说，这在某些数据上将完全失败。 - Keith

谢谢，我已经修改了我的答案。 - Alex

Answer 4

我想提出一个稍有不同的替代方案，并介绍stable_sort的好处。

typedef std::pair<int, std::string> CNP;

bool byName(CNP const& left, CNP const& right) { return left.second < right.second; }
bool byCount(CNP const& left, CNP const& right) { return left.first < right.first; }

std::sort(values.begin(), values.end(), byName);

std::stable_sort(values.begin(), values.end(), byCount);

这是因为在相等元素的情况下（比较相等的元素），stable_sort 会保留它们的相对顺序（而 sort 可能会，但不保证）。

因此，假设你有 [ (3, "apple"), (2, "zorro"), (2, "banana") ]：

按名称排序结果为：[ (3, "apple"), (2, "banana"), (2, "zorro") ] 稳定地按数量排序结果为：[ (2, "banana"), (2, "zorro"), (3, "apple") ] 当然，如果你不需要中间步骤，使用一个更复杂的谓词进行单一排序更有效率；然而，如果你收到一个已按名称排序的列表，那么只需应用按数量的 stable_sort 可能更快。

最后，检查列表是否按照准则排序（或未排序）的简单技巧：

template <typename C, typename P>
bool is_sorted(C const& list, P comp) {
    typedef typename C::const_reference CR;

    auto const reversed = [](CR left, CR right) { return comp(right, left);  };

    return std::adjacent_find(list.begin(), list.end(), reversed) == list.end();
}

注意：C++11有一个is_sorted方法，但它是基于迭代器而不是容器的。

- Matthieu M.

---

这是一个非常有用的建议。顺便提一下，C++11中有一个std::is_sorted函数。 - juanchopanza

@juanchopanza：哦！我不知道！ - Matthieu M.