Using std::complex as a std::map key

Question

How can I use a complex number as the key in a map? Here is a small example which will not compile:

#include <complex>
#include <map>
int main() {
  std::complex<double> zero = 0.0;
  std::map<std::complex<double>, int> theMap;
  return (theMap.count(zero));
}

I can create the map without errors, but any method (e.g., the count call above as well as find, the [] operator, insert, etc.) generates compile-time errors. It is definitely a problem with my understanding, as I get similar results using clang and g++.

It looks like the compiler cannot compare two complex numbers. I created all of the comparison operators (e.g., bool operator< (const std::complex & lhs, const std::complex & rhs) {return (std::norm(lhs) < std::norm(rhs));}), which works for comparing complex numbers (as long as you don't mind 3 < -5 being true, which should be fine for map), but the compiler doesn't pick it up.

I have similar problems with unordered_map (there is no hash for complex<double>)

Answer 1

The problem with your approach is that, for an ordered container, such as std::map, the key must be amenable to a strict weak ordering. From wikipedia:

A strict weak ordering has the following properties. For all x and y in S,

For all x, it is not the case that x < x (irreflexivity).

For all x, y, if x < y then it is not the case that y < x (asymmetry).

For all x, y, and z, if x < y and y < z then x < z (transitivity).

For all x, y, and z, if x is incomparable with y, and y is incomparable with z, then x is incomparable with z (transitivity of incomparability).

Unfortunately, there is no natural way to impose a strict weak ordering on the complex numbers. For example, is 1 < i or i < 1? If you say that -i ≮ 1 and 1 ≮ i, then by the rules strict weak ordering it must be the true that -i ≮ i. That does mean sense.

You need to use complex numbers as a key, it is unlikely that you need and ordered container. Try looking into std::unordered_map.

From section 23.2.4.2 [associative.reqmts] of C++11 standard:

Each associative container is parameterized on Key and an ordering relation Compare that induces a strict weak ordering (25.4) on elements of Key. In addition, map and multimap associate an arbitrary type T with the Key. The object of type Compare is called the comparison object of a container.

Answer 2

I have not looked at the implementation but per cppreference std::map uses std::less<T> as a comparison operator, that might not be specialized for std::complex, if you implement one pass it as the third parameter in your template std::map<std::complex, int, LessOperator> similarily with std:unordered_map, where you can supply a hash functor and an equality functor. If both of those are implemented you can use std::complex as the key.

Answer 3

The main answers have been pointed out in the comments above. The problem is that complex numbers are not ordered, and so there is no pre-defined smaller-operator for std::complex<T>. Nevertheless, you can define one for yourself, and this goes easily by using the already defined smaller operator for std::array<T,2>:

#include <iostream>
#include<complex>
#include<map>
#include<unordered_map>
#include<array>

template<typename T> struct less {};

    template<typename T>
    struct less<std::complex<T> >
    {
        bool operator()(std::complex<T> const& a, std::complex<T> const& b)
        {
            return std::array<T,2>{a.real(),a.imag()} < std::array<T,2>{b.real(),b.imag()};
        }
    };

int main()
{
    std::map<std::complex<double>, int, less<std::complex<double> > > m;

    m[std::complex<double>(1.0,0.0)]=1;
    m[std::complex<double>(0.0,1.0)]=2;
    m[{0.5,0.5}]=3;

    return 0;
}

See live example here.