3

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

3 试用 2 美味 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;
}
4

4 回答 4

7

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

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 表达式，而不是手动编写仿函数：

  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和中有 C++03 替代实现std::tr1::tie。Lambda 表达式需要 C++11 语言支持。

于 2013-08-22T05:25:43.383 回答
4

一次性对两个字段进行排序：

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

另见现有条目

于 2013-08-22T05:41:52.767 回答
2

你必须考虑价值观本身。

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));
}
于 2013-08-22T05:29:39.590 回答
1

我想提出一个稍微不同的替代方案，并介绍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方法，虽然用迭代器表示，当然不是容器。

于 2013-08-22T06:21:55.100 回答