Re: Contraints on equal_range comparison function object
Meador Inge wrote:
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?
I don't even find that requirement in the current draft. Only
that comp(e, value) and comp(value, e) are both valid
expressions evaluating to bool and that comp(e, value) ==
!comp(value, e). Similarly, it doesn't require that the
sequence be sorted (since we have no ordering criteria defined
for the elements), only that the elements are partitionned such
that there exists two elements, e1 and e2, such that e1 precedes
e2 in the sequence, and the sequence is partitionned such that
for all elements before e1, comp(e, value) is true, and for all
elements after and including e2 (unless e2 is the end iterator),
comp(value, e) is true.
I suspect that this is a clarification with regards to the
original version, which "sort of" assumed that T and
ForwardIterator::value_type were the same. (Obviously, T is
LessThanComparable means that you can compare two T's, but not
necessarily that you can compare a T with
ForwardIterator::value_type, if they are not the same.
Note too that LessThanComparable says that the operator< must be
defined, even though it obviously won't be (or shouldn't be)
used if you provide the 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?
It should be according to the most recent draft. The original
version of the standard is very ambiguous on the question; in
fact, it doesn't begin to make sense unless you assume that T is
ForwardIterator::value_type---it also seems reasonable to assume
that if you are providing the comparison function yourself, you
don't need to define an operator< for T, but that your
comparison function must define a strict ordering much in the
same way < does for arithmetic types.
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.
They probably tried to exterpolate what the official version of
the standard meant, before the clarification was made. As a
work-around, add the additional operator (and maybe one for two
string parameters as well---who knows). More generally, if you
really want to be sure of being portable, don't use *_bound or
equal_range without ForwardIterator::value_type being the same
(modulo cv qualifiers) as T. Since the actual standard doesn't
make sense otherwise, it seems reasonable to assume that this is
what was meant.
One additional point: I hope they have several different flags
for turning off verifications. I generally leave the
verifications in delivered code, but a verification like this,
as useful as it is, is very likely to have serious performance
implications, at least if the vector is fairly large (and if it
isn't, I'll probably be using std::find anyway, and not one of
the binary search functions). So I would definitly prefer being
to turn it off without turning all of the others (e.g. bounds
checking on vector<>::operator[]) off.
--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orient?e objet/
Beratung in objektorientierter Datenverarbeitung
9 place S?mard, 78210 St.-Cyr-l'?cole, France, +33 (0)1 30 23 00 34
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]