CODEWITHSUNDEEP
c++comparisoncontainersstdc++98
Fabio A.
Fabio A.

Reputation: 2734

heterogeneous containers lookup in C++98

In a project I'm working on, I'm forced to use c++98. Having the need to perform fast lookups in certain vectors of structures, using only a few elements of those structures as keys, I have so far happily been passing to std::lower_bound and std::upper_bound a value parameter with a type different than those structure's and a comparison functor that would handle this heterogeneous case properly.

It all works as expected, but today I suddenly realized this might not be allowed by the standard, and I found confirmation of this hunch in a few papers, like this one which also proposes an amendment to the standard which, I'm learning now, has been implemented in C++0x, as this other paper confirms.

My question is: is the fact my code works as expected, despite NOT abiding by the letter of the standard, a mere coincidence, a side-effect of the specific implementation, a non-guaranteed result should I change compiler and whatnot?

In other words, should I really really really change my code to be standard-compliant (which would greatly complicate it), or can I just not bother and let it be, considering this codebase is not going to be compiled with anything else but g++ for the time being?

Upvotes: 1

Views: 141

Answers (1)

Galik
Galik

Reputation: 48665

Only you can decide if keeping the status quo is worth the risk. However, if you move to C++11, the wording has changed to allow for what you are doing.

I would think it is rather unlikely compiler vendors will change how their Standard Library works for an old version of the Standard. So I can't see that it is very likely that your C++98 code will break unless you move it to an untested compiler. And even if that happened, you could always implement your own (drop-in-replacement) version of std::lower_bound to accomodate.

According to my reading of the C++11 Standard you are fine.

25.4.3.1 lower_bound [ lower.bound ]

template<class ForwardIterator, class T>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value);

template<class ForwardIterator, class T, class Compare>
ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last, const T& value, Compare comp);

1 Requires: The elements e of [first,last) shall be partitioned with respect to the expression e < value or comp(e, value).

2 Returns: The furthermost iterator i in the range [first,last] such that for any iterator j in the range [first,i) the following corresponding conditions hold: *j < value or comp(*j, value) != false.

3 Complexity: At most log 2 (last − f irst) + O(1) comparisons.

Requirement 2 does not dictate that value be of the same type as *e.

Also the document you reference says:

But is it legal? The standard's position on this question is not encouraging. For one thing, 25.3 says that for the algorithms to work correctly, the comparison object has to induce a strict weak ordering on the values.

This comes from the C++03 Standard and is not the wording I find in the C++11 Standard which states this:

25.4 Sorting and related operations [ alg.sorting ]

3 For all algorithms that take Compare, there is a version that uses operator< instead. That is, comp(*i, *j) != false defaults to *i < *j != false. For algorithms other than those described in 25.4.3 to work correctly, comp has to induce a strict weak ordering on the values.

It gives a clear exemption to the algorithm used by std::lower_bound:

25.4.3 Binary search [ alg.binary.search ]

1 All of the algorithms in this section are versions of binary search and assume that the sequence being searched is partitioned with respect to an expression formed by binding the search key to an argument of the implied or explicit comparison function.

This wording allows "an argument" to the comparison function to be of different type to the container elements. It simply needs to match the "search key".

Upvotes: 1

Related Questions