CODEWITHSUNDEEP
c++
Cecilia
Cecilia

Reputation: 4741

My vector is sorted and yet I'm getting a "sequence not ordered" error

Are there situations in which std::sort fails?

I've got a std::vector<KeyValPair<T>> queue with which I do the following

std::sort(queue.begin(), queue.end());
std::pair<iterator, iterator> match =
    std::equal_range(queue.begin(), queue.end(), cost);

Exactly that. And then sometimes, not always, I get a "sequence not ordered" error.

The documentation describes sort and equal_range as using the same comparison functions, so I am confused how the vector could become unordered.

The vector type is the following class with custom comparison operators.

template<typename T>
class KeyValPair: public std::pair<double, T>
{
public:
    KeyValPair(double d, T t): std::pair<double, T>(d, t){};

    bool operator<(const KeyValPair<T>& rhs) const 
    { 
        return first < rhs.first;
    }

    bool operator==(const KeyValPair<T>& rhs) const 
    { 
        return second == rhs.second;
    }
};

template<typename T>
bool operator< (const KeyValPair<T>& lhs, const double& rhs) {return lhs.first < rhs;};
template<typename T>
bool operator< (const double& lhs, const KeyValPair<T>& rhs) {return lhs < rhs.first;};

Could the comparison function be failing somehow? What else can cause this error?

Upvotes: 3

Views: 658

Answers (1)

Yakk - Adam Nevraumont
Yakk - Adam Nevraumont

Reputation: 275730

As first psychically detected by @ecatmur, your problem is you are using < on doubles, and one or more of your doubles is a NaN.

A safe double ordering follows:

struct safe_double_order {
  bool operator()(double lhs, double rhs) const {
    if ((lhs != lhs) || (rhs != rhs)) // NaN detector
      return (lhs!=lhs)>(rhs!=rhs); // order NaN less than everything, including -infinity
    return lhs < rhs;
  }
};

Next, we can write a key-sorter:

template<class K, class O=std::less<K>>
struct key_sorter {
  struct helper {
    K const& k;
    helper( K const& o ):k(o) {}
    template<typename V>
    helper( std::pair<K, V> const& o ):k(o.first) {}
    bool operator<( helper const& o ) const {
      return O{}( k, k.o );
    }
  };
  bool operator()( helper lhs, helper rhs ) const {
    return lhs < rhs;
  }
};

which passed a key-type and an optional ordering functor lets you search/sort std::pair<Key,?> with Key types directly.

std::vector< std::pair<double, X> > vec;
std::sort( vec.begin(), vec.end(), key_sorter<double, safe_double_order>{} );
auto match = std::equal_range( vec.begin(), vec.end(), value, key_sorter<double, safe_double_order>{} );

There are some C++11isms above, but the general design should be clear if you are using C++03.

Upvotes: 2

Related Questions