Re: Contraints on equal_range comparison function object
Meador Inge ha scritto:
For:
template<class ForwardIterator, class T, class Compare>
pair<ForwardIterator, ForwardIterator>
equal_range(ForwardIterator first, ForwardIterator last, const T&
value, Compare comp);
what are the constraints on T?
The Standard only specifies that "Type T is LessThanComparable
(20.1.2)." Is that it?
Yes. That's the only requirement on T. However there is a requirement on
the range and, implicitly, on the comparison function in 25.3.3/1: "All
of the algorithms in this section [...] assume that the sequence being
searched is in order according to the implied or explicit comparison
function."
The reason I am asking is because I have a case something like:
struct Compare
{
bool operator()(const std::string& lhs, int rhs);
bool operator()(int lhs, const std::string& rhs);
};
...
std::vector<int> v;
std::string k("abc");
std::equal_range(v.begin(), v.end(), k, Compare());
Now this only works if there is *not* a constraint stating that the
value type of ForwardIterator == T.
Is the above well-defined in terms of the Standard?
Not with the current standard. But notice that it's Compare that is
failing the requirements, not T.
However, it seems that the committee realized that the requirements is
unnecessarily restrictive and that most implementations already work
with relaxed assumptions. In fact, in the most recent draft of the
standard, the statement above reads completely different: "All of the
algorithms in this section [...] 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."
It works on most compiler, but on VC++ 8.0 in debug mode I hit problem.
The reason being that their debug implementation of std::equal_range
uses Compare to ensure that the sequence is actually ordered. Since I
don't have a 'bool operator()(int lhs, int rhs' I get compilation
problems.
Strictly speaking, the VC++ 8.0 library is correct. However, I find it a
bit overzealous... checking if the range is sorted each time I do a
binary search, even if only in debug builds, sounds really too much to
me. Of course, that's just my opinion. Anyway, when the new wording will
become standard the check will have to be corrected.
HTH,
Ganesh
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]