5.1.4 Ordering expressions

Sometimes it is necessary to establish a mathematically well-defined ordering on a set of arbitrary expressions, for example to use expressions as keys in a std::map<> container, or to bring a vector of expressions into a canonical order (which is done internally by GiNaC for sums and products).

The operators <, > etc. described in the last section cannot be used for this, as they don't implement an ordering relation in the mathematical sense. In particular, they are not guaranteed to be antisymmetric: if ‘a’ and ‘b’ are different expressions, and a < b yields false, then b < a doesn't necessarily yield true.

By default, STL classes and algorithms use the < and == operators to compare objects, which are unsuitable for expressions, but GiNaC provides two functors that can be supplied as proper binary comparison predicates to the STL:

class ex_is_less : public std::binary_function<ex, ex, bool> {
public:
    bool operator()(const ex &lh, const ex &rh) const;
};

class ex_is_equal : public std::binary_function<ex, ex, bool> {
public:
    bool operator()(const ex &lh, const ex &rh) const;
};

For example, to define a map that maps expressions to strings you have to use

std::map<ex, std::string, ex_is_less> myMap;

Omitting the ex_is_less template parameter will introduce spurious bugs because the map operates improperly.

Other examples for the use of the functors:

std::vector<ex> v;
// fill vector
...

// sort vector
std::sort(v.begin(), v.end(), ex_is_less());

// count the number of expressions equal to '1'
unsigned num_ones = std::count_if(v.begin(), v.end(),
                                  std::bind2nd(ex_is_equal(), 1));

The implementation of ex_is_less uses the member function

int ex::compare(const ex & other) const;

which returns 0 if *this and other are equal, -1 if *this sorts before other, and 1 if *this sorts after other.