如何在C++中对两个vector进行逆序字典序比较？

C++中对两个std::vector进行字典序比较可以直接使用operator<，示例如下：

int main() {
    std::vector<int> a{0, 7, 8, 9};
    std::vector<int> b{1, 2, 3, 4};

    std::cout << std::boolalpha;
    std::cout << "a < b returns " << (a < b) << '\n';
}

但尝试对vector的逆视图（通过std::views::reverse生成）直接使用operator<会编译失败，示例代码：

int main() {
    std::vector<int> a{3, 2, 1};
    std::vector<int> b{9, 8, 7, 6};

    std::cout << std::boolalpha;
    std::cout << "reverse a < reverse b returns " << ((a | std::views::reverse) < (b | std::views::reverse)) << '\n';
}

编译错误信息：

<source>:23:81: error: no match for 'operator<' (operand types are 'std::ranges::reverse_view<std::ranges::ref_view<std::vector<int> > >' and 'std::ranges::reverse_view<std::ranges::ref_view<std::vector<int> > >')
   23 |     std::cout << "reverse a < reverse b returns " << ((a | std::views::reverse) < (b | std::views::reverse)) << '\n';
      |                                                       ~~~~~~~~~~~~~~~~~~~~~~~~~ ^ ~~~~~~~~~~~~~~~~~~~~~~~~~
      |                                                          |                           |
      |                                                          reverse_view<[...]>         reverse_view<[...]>

解决方案 #

方法1：使用std::ranges::lexicographical_compare #

C++20的Ranges库提供了std::ranges::lexicographical_compare函数，专门用于比较两个范围的字典序，支持所有符合范围概念的类型（包括reverse_view）。

修改后的代码如下：

#include <vector>
#include <iostream>
#include <ranges>
#include <algorithm>

int main() {
    std::vector<int> a{3, 2, 1};
    std::vector<int> b{9, 8, 7, 6};

    std::cout << std::boolalpha;
    auto rev_a = a | std::views::reverse;
    auto rev_b = b | std::views::reverse;
    bool result = std::ranges::lexicographical_compare(rev_a, rev_b);
    std::cout << "reverse a < reverse b returns " << result << '\n';
}

该函数会按字典序逐个比较两个范围中的元素，遇到第一个不相等的元素时返回结果；若一个范围是另一个的前缀，则较短的范围被判定为更小，完全匹配你开发大整数类的需求——小端存储的vector逆序后即为高位在前的数字，字典序比较等价于数值大小比较。

方法2：在自定义大整数类中封装比较逻辑 #

针对你开发自定义大整数类的场景，可以在类的operator<中直接调用std::ranges::lexicographical_compare来比较内部vector的逆视图：

#include <vector>
#include <ranges>
#include <algorithm>

class BigInt {
private:
    std::vector<int> digits; // 小端存储，digits[0]是最低位
public:
    BigInt(std::vector<int> d) : digits(std::move(d)) {}

    bool operator<(const BigInt& other) const {
        auto rev_this = digits | std::views::reverse;
        auto rev_other = other.digits | std::views::reverse;
        return std::ranges::lexicographical_compare(rev_this, rev_other);
    }
};

这样在比较两个BigInt对象时，会自动按逆序字典序（即数值大小）进行比较。

内容的提问来源于stack exchange，提问作者Sourav Kannantha B