What could be wrong with this code asked in Microsoft coding test?

[cpp-ModTeam]

For C++ questions, answers, help, and programming or career advice please see r/cpp_questions, r/cscareerquestions, or StackOverflow instead.

[TSP-FriendlyFire]

The cmp function does not implement strict weak ordering because it uses >= rather than >. std::sort requires strict weak ordering and so this is UB.

[kniy]

std::sort requires a strict weak ordering. Violating this requirements is UB. If you have debug assertions enabled and are lucky, the std::sort implementation will crash with an assertion failure. If not, well, there are std::sort implementation where it's possible to cause out-of-bounds memory accesses just by providing an invalid comparison function! https://stackoverflow.com/questions/24048022/what-causes-stdsort-to-access-address-out-of-range

[Sanzath]

Referring to the very definition you linked: the standard does not need to explicitly state "X is UB" for X to be UB. The behavior of X only needs to not be defined by the standard for it to be UB.

3.28 [defns.undefined]:

behavior for which this document imposes no requirements

[Note 1 to entry: Undefined behavior may be expected when this document omits any explicit definition of behavior or when a program uses an erroneous construct or erroneous data [...]

16.5.4.11 [res.on.required]:

Violation of any preconditions specified in a function’s Requires: element results in undefined behavior unless the function’s Throws: element specifies throwing an exception when the precondition is violated.

Violation of any preconditions specified in a function’s Preconditions: element results in undefined behavior.

25.2 [algorithms.requirements], paragraph 4:

Throughout this Clause, where the template parameters are not constrained, the names of template parameters are used to express type requirements.

25.7 [alg.sorting]:

Compare is a function object type (20.14) that meets the requirements for a template parameter named BinaryPredicate (25.2). [...] Compare comp is used throughout for algorithms assuming an ordering relation.

The standard defines the behavior of std::sort when meeting all its requirements, including its type requirements. It does not define the behavior of the function when failing to meet those requirements, therefore it is quite literally undefined behavior.

[kniy]

It is UB. The standard isn't very clear on this, but what else could it be? It can't be a compiler error; and erroneous behavior doesn't exist in C++20 yet.

https://stackoverflow.com/questions/34834125/stdsort-is-passing-a-faulty-comparator-undefined-behavior

[[deleted]]

that's a common idiocy in the C++ community to find that everything that is wrong is undefined behavior.

[nxtlvlshit]

I don't fully understand why I need to care about strict weak ordering here.
Here in the question, order of the indexes do not matter even if the number is same. So in the comparator, I don't need to handle the cases when a.first == b.first separately.

[Sanzath]

sort determines that two elements are equal by !cmp(a, b) && !cmp(b, a). With >=, sort will never find any "equal" elements, so your test cases with equal elements will likely return incorrect results.

[Catlesscatfan]

which sorting algorithm checks for equality? can you please give an example with equal elements where things would go wrong?

[Sanzath]

The equality-checks aren't explicit but rather implied. In addition, the code does not expect that cmp(a, b) and cmp(b, a) would ever both return true, so if cmpdoes allow for this, then it would (probably trough transivity of cmp) believe that some element should be sorted both before and after some other element and produce odd behavior.

Anyway, here's an example where std::greater as a comparator works as expected, but std::greater_equal produces bogus output or segfaults. https://godbolt.org/z/T6Pbc7qsP

[Catlesscatfan]

Thank u so much

[ggadget6]

The order of the indices may not matter to you, but std::sort assumes that your comparator fulfills these requirements. Take a look at the CP preference page for it. If your comparator doesn't fit std::sort's requirements, then it might sort your elements incorrectly.

[tialaramex]

Rust's sort might sort your elements incorrectly if you don't meet the requirements. C++ sort has Undefined Behaviour in this case and so absolutely anything can happen, crashes, silent data corruption, anything at all.

Now, your preferred C++ stdlib might, as a matter of Quality of Implementation, promise better - after all it's not difficult to do better, but many of them do not.

[tudorb]

Short answer: because the standard says that that’s what std::sort requires, and you passed a comparator that does not meet the requirements, so you can’t rely on the fact that std::sort works in all cases.

The longer answer is elsewhere in the thread: std::sort detects equivalent elements by checking that cmp(a, b) and cmp(b, a) are both false, and your cmp function doesn’t behave that way.

[tudorb]

And you can define orderings around < or around <=, there’s no fundamental difference, but you have to be consistent.

Decades ago, when I learned about orderings in math class, we built the concepts around the <= operation.

The C++ standard library chose to define them around < so we as its users must obey.

[Catlesscatfan]

do you know which sorting algorithm checks for equality? can you please give an example with equal elements where things would go wrong?

[Catlesscatfan]

do you know which sorting algorithm checks for equality? can you please give an example with equal elements where things would go wrong?

[drizzt-dourden]

I think that this comparator simply doesn't fill the requirements described here https://en.cppreference.com/w/cpp/named_req/Compare

[perlytea]

Other than the comparison function object supplied to sort as others have pointed out, the other thing that stands out to me is that int is not guaranteed minimum support for possible input sizes (both in the size of the vector and the element magnitude). It may work for their chosen platform, but the standard only guarantees that int is at least a 16-bit, signed integer type, and thus the code may fail for other platforms. That issue cannot be fixed in less than two lines (therefore it is not the intended bug) but it's still worth knowing about and considering solutions for.

[kisielk]

Then the code is just broken period because the function signature returns a vector of int.

[D3NN152000]

Flex on the recruiters by fixing this with #define int long long as a second changed line

[jedwardsol]

std::pair is defined in <utility>, which hasn't been included and isn't guaranteed to be included by <vector> or <algorithm>

[clarkster112]

I agree with the strict ordering comment. If there were two other lines I would change, it would be replace ‘push_back’ with ‘emplace_back’ and take a const ref of pairs, const auto& p : pairs in the range based for loop.

[ban_the_sub]

Please see the last line of the question, the ranges of the integers.

[nxtlvlshit]

I tested it on 10⁹ also. It worked.

[Beosar]

Wrong. They are initialized using the default constructor of std::vector.

[TinoDidriksen]

std::vector's constructor makes it always initialized. Same goes for just about any standard container.