map of std::complex

[Mohamed Ali]

I need to create a map:
map<complex<int>,complex<double> >
But it generate an error due to operator != and < ?
Am I supposed to overload != and < operator for std::complex and How?

Thanks for help

 

[Joe Smith]

I need to create a map:
map<complex<int>,complex<double> >
But it generate an error due to operator != and < ?
Am I supposed to overload != and < operator for std::complex and How?

Thanks for help

You could use code like the following:

template<typename T>
struct complex_less
{
bool operator() (const std::complex<T>& lhs, const std::complex<T>& rhs)
{
if (lhs.real()<rhs.real()) return true;
else if (lhs.real()==rhs.real()&& lhs.imag()<rhs.imag()) return true;
return false;
}
};

std::map<std::complex<int>,std::complex<double>, complex_less<int> > t;

 

[peter koch]

I need to create a map:
map<complex<int>,complex<double> >

Why? I've never seen complex used as key, and I also find complex<int>
slightly unusual. This does not exclude the possibility that your
design is wrong, of course.

But it generate an error due to operator != and < ?

I can't imagine it complaining about a missing operator !=. But you
need to supply an operator <, as complex numbers aren't ordered.

Am I supposed to overload != and < operator for std::complex and How?

You are supposed to create an ordering function. As to how, I believe
you should do some of your work yourself and search for the answer in
your textbook, the net (e.g. the C++ FAQ) or in your compilers
documentation.

/Peter

 

[Juha Nieminen]

if (lhs.real()<rhs.real()) return true;
else if (lhs.real()==rhs.real()&& lhs.imag()<rhs.imag()) return true;
return false;

Wouldn't that be the same as:

return lhs.real() < rhs.real() ||
(lhs.real() == rhs.real() && lhs.imag() < rhs.imag());

 

[James Kanze]

Wouldn't that be the same as:

return lhs.real() < rhs.real() ||
(lhs.real() == rhs.real() && lhs.imag() < rhs.imag());

Or even the canonical:

return lhs.real() < rhs.real() ||
(!(rhs.real() < lhs.real()) && lhs.imag() < rhs.imag());

(Personally, I prefer your version, and find it more natural.
But the above is what the standard library usually uses.)

Also, I wouldn't name it complex_less, or anything that might
suggest that it has anything to do with less than in a
mathematical sense. Something like complex_ordering, or
something which suggests an arbitrary ordering would probably be
better. (But admittedly, it's not a big point, as long as he
doesn't use it to overload <.)

Another alternative which is sometimes suggested is the name it
std::less< std::complex< double> > or whatever the desired
instantiation is. Do this, and you don't have to specify the
comparison object when instantiating std::map. Of course, you
do have to ensure that you're the only coder in the project
which does it, or you'll probably run afowl of the one
definition rule, so you probably wouldn't want to do it in
anything but toy code.

 

[Juha Nieminen]

Or even the canonical:

return lhs.real() < rhs.real() ||
(!(rhs.real() < lhs.real()) && lhs.imag() < rhs.imag());

(Personally, I prefer your version, and find it more natural.
But the above is what the standard library usually uses.)

I suppose the idea in the standard library is to avoid unnecessarily
requiring the type to support operator==, when operator< will suffice
equally well?

 

[James Kanze]

I suppose the idea in the standard library is to avoid
unnecessarily requiring the type to support operator==, when
operator< will suffice equally well?

That's the theory. I'll let you guess as to what I think with
regards to types that define operator<, but not operator==.

 

[James Kanze]

Even then, the behavior is undefined. It's a specialization of
a standard library template but it doesn't depend on any
user-defined types.

Good point. So you'd have to specialize it on std::complex<
MyDouble >, or something like that.

 

[Joe Smith]

Or even the canonical:

return lhs.real() < rhs.real() ||
(!(rhs.real() < lhs.real()) && lhs.imag() < rhs.imag());

(Personally, I prefer your version, and find it more natural.
But the above is what the standard library usually uses.)

His suggestion is the most natural, but the latter has the advantage
of not needing a working ==.

They are also not equivlent: lhs as 6+6i and rhs as 5+7i gives different
results for the two.

Also, I wouldn't name it complex_less, or anything that might
suggest that it has anything to do with less than in a
mathematical sense. Something like complex_ordering, or
something which suggests an arbitrary ordering would probably be
better. (But admittedly, it's not a big point, as long as he
doesn't use it to overload <.)

Indeed. My example was just a quick and dirty example, which is why it was
not a one-line function, and used a questionable name.

 

[Joe Smith]

Good point. So you'd have to specialize it on std::complex<
MyDouble >, or something like that.

The only issue is that the behavior of std::complex<T> for a T that is not
float, double, or long double is unspecified.

That seems odd. The correct behavior for std::complex<int> for example is
obvious, (at least for the arithmatic functions) and there seems to be no
reason why that should be unspecified.

The case of std::complex<UserDefinedFloatingPointType> should be
specifiable, too, right? Perhaps I should read back over the std::complex
related proposals for C++0x that were rejected or deferred.



As a slightly related aside, I just noticed that [complex.numbers]/4 in
N2800 has some slight typographical issues, namely that in several places cv
was typeset in bold, when it should have been typeset in italic. I mention
this here, because I'm not sure how best to report this, but am confident
that somebody who does will see it.

 

[James Kanze]

His suggestion is the most natural, but the latter has the
advantage of not needing a working ==.

Do you have some types where < is defined, but there is no
working ==? Such types wouldn't get through code review at the
places I've worked.

They are also not equivlent: lhs as 6+6i and rhs as 5+7i gives
different results for the two.

They both evaluate to false, which is what I'd expect. If they
do give different results, the definitions of < and == aren't
compatible.

 

[Juha Nieminen]

His suggestion is the most natural, but the latter has the advantage
of not needing a working ==.

It might also be possible that the version using operator< only can be
better optimized by the compiler.

If you call lhs.real() < rhs.real() and then lhs.real == rhs.real(),
it's probable that the compiler will produce two comparisons and two
conditional jumps from those.

However, if you call lhs.real() < rhs.real() and then
!(lhs.real() < rhs.real()), it's theoretically possible that the
compiler will notice the pattern and create only one comparison and one
conditional jump.

 

[Kai-Uwe Bux]

It might also be possible that the version using operator< only can be
better optimized by the compiler.

If you call lhs.real() < rhs.real() and then lhs.real == rhs.real(),
it's probable that the compiler will produce two comparisons and two
conditional jumps from those.

However, if you call lhs.real() < rhs.real() and then
!(lhs.real() < rhs.real()), it's theoretically possible that the
compiler will notice the pattern and create only one comparison and one
conditional jump.

Huh? You have the first comparison

lhs.real() < rhs.real()

and the second comparison with reversed order of operands

rhs.real() < lhs.real()

whose result is negated. I don't see how the compiler could optimize one
comparison away (unless there is a machine instruction doing a three-way
comparison).

On the other hand, I suspect that a good optimizing compiler might generate
identical code regardless of the form the programmer chooses.


Best

Kai-Uwe Bux

 

[James Kanze]

It might also be possible that the version using operator<
only can be better optimized by the compiler.

Or the reverse might also be possible.

If you call lhs.real() < rhs.real() and then lhs.real ==
rhs.real(), it's probable that the compiler will produce two
comparisons and two conditional jumps from those.

On most machines, a comparison will set status bits; the
compiler will likely see that the comparison has already been
done, and only test the status bits. Of course, the compiler
could also recognize that !x<y is the same as x>y, and recognize
that the status bits were already set for that as well. With a
good optimizing compiler, I'd expect no difference.

However, if you call lhs.real() < rhs.real() and then
!(lhs.real() < rhs.real()), it's theoretically possible that
the compiler will notice the pattern and create only one
comparison and one conditional jump.

Or not. Back in the old days, Fortran had a three way if
(arithmetic if), which didn't test for true/false, but for
positive/zero/negative. I would expect that handling such cases
would involve well known optimization techniques. (Curiously,
both g++ and VC++ seem to use three comparison instructions in
both cases. On the AMD machine where I'm writing this, I'd have
expected something along the lines of:
xor %eax, %eax
ucomisd %xmm0, %xmm2
jnz $end
ucomisd %xmm1, %xmm3
$end:
addc 0, $eal
rep
for either of them, supposing I understand the instruction set
correctly---I've never really studied it. G++ is far from that.
(The issue on the 32 bit Intel architecture on which I have VC++
is more complex, because floating point comparison doesn't
directly affect the CPU status codes. Still, VC++ compares and
reads the status codes twice for the first double, where once
would definitely suffice.)

 

[Joe Smith]

Do you have some types where < is defined, but there is no
working ==? Such types wouldn't get through code review at the
places I've worked.


They both evaluate to false, which is what I'd expect. If they
do give different results, the definitions of < and == aren't
compatible.

Right. I origninally misread the second example,
as

return lhs.real() < rhs.real() ||
(!(LHS.real() < RHS.real()) && lhs.imag() < rhs.imag());

(Caps for emphasis).