How to lexicographically compare two vectors in reverse order?

Question

If I want to compare two vectors in lexicographical order, I can do as follows:

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

But doing the same in reverse order fails to compile:

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

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

The latter code fails with:

<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<[...]>

So, how to do achieve this properly?

I needed this because, I was creating a custom big integer class. In that, I was storing nodes in little endian order. Now, to compare if two integers are equal, first I compare their sizes. Then I would need to compare equal sized vectors in lexicographical order of their reverse view.

Does this answer your question? Is there a standard way to compare two ranges in C++? — kiner_shah
– kiner_shah, Commented Feb 17, 2023 at 8:02
@kiner_shah OP wants to compare the reversed vectors via <, the question you propose as dupe is about equality, where reversed or not does not matter — 463035818_is_not_an_ai
– 463035818_is_not_an_ai, Commented Feb 17, 2023 at 8:06
@kiner_shah the fact that there is an answer that is slightly related does not make the questions a duplicate. Consider that the answer you link could be deleted or modified to still match the question asked there but to not match the question asked here. That question is about comparing for eqaulity, this question is about comparing < reversed. — 463035818_is_not_an_ai
– 463035818_is_not_an_ai, Commented Feb 17, 2023 at 8:09
@kiner_shah i mean that == / equality and lexicographical comparison / < are totally different. The question you link is about the former, the question here is about the latter. The answers on the question you link focus on equality because thats what is being asked for there, but not here. — 463035818_is_not_an_ai
– 463035818_is_not_an_ai, Commented Feb 17, 2023 at 8:14

user17732522 · Accepted Answer · 2023-02-17 08:01:29Z

7

operator< is not defined for std::views::reverse and others. There is however a normal algorithm as normal function template for it in the standard library: std::lexicographical_compare with iterator interface and std::ranges::lexicographical_compare with range interface.

std::cout << "revrese a < reverse b returns "
          << std::ranges::lexicographical_compare(a | std::views::reverse, b | std::views::reverse) 
          << '\n';

answered Feb 17, 2023 at 8:01

user17732522

78.1k3 gold badges82 silver badges147 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Sourav Kannantha B Over a year ago

For future reference, I'm using this solution, with slight modification as in shown in this.

Sourav Kannantha B · Accepted Answer · 2023-02-20 21:22:32Z

1

As @user17732522 said you can use std::ranges::lexicographical_compare && std::views::reverse but if you want use c++11 you can simply use reverse iterators with std::lexicographical_compare.

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

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 "
            << std::lexicographical_compare(a.cbegin(), a.cend(), b.rbegin(),
                                            b.rend())
            << '\n';
}

edited Feb 20, 2023 at 21:22

Sourav Kannantha B

3,4241 gold badge22 silver badges55 bronze badges

answered Feb 17, 2023 at 8:39

Another HM

14810 bronze badges

1 Comment

Damir Tenishev Over a year ago

Why do you use cbegin/cend for vector a? Is it a misprint and rbegin/rend were expected?

Collectives™ on Stack Overflow

How to lexicographically compare two vectors in reverse order?

2 Answers 2

1 Comment

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related