在哪些情况下std::sort
失败了?
我有一个 std::vector<KeyValPair<T>> queue
我用它做以下事情
std::sort(queue.begin(), queue.end());
std::pair<iterator, iterator> match =
std::equal_range(queue.begin(), queue.end(), cost);
正是这样。然后有时(并非总是如此)我会收到“序列未排序”错误。
文档描述了 sort
和 equal_range
因为使用相同的比较函数,所以我很困惑 vector 如何变得无序。
vector
type 是具有自定义比较运算符的以下类。
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;};
比较功能会不会以某种方式失败了?还有什么可能导致此错误?
最佳答案
@ecatmur 首次从心理上检测到,您的问题是您正在使用 <
在 double
s,以及您的一个或多个 double
s 是 NaN
.
保险箱 double
顺序如下:
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;
}
};
接下来,我们可以编写一个键排序器:
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;
}
};
它传递了一个键类型和一个可选的排序仿函数,让您可以搜索/排序 std::pair<Key,?>
与 Key
直接输入。
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>{} );
上面有一些C++11isms,但是如果你用的是C++03,大体的设计应该很清楚。
关于c++ - 我的 vector 已排序,但出现 "sequence not ordered"错误,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/25083716/