2

我有一个包含三个字段的结构数组：

struct data{
   int s;
   int f;
   int w;   
};

struct data a[n];

为了根据字段 f 对结构数组进行排序，我使用了自己的比较运算符：

bool myf( struct data d1,const struct data d2){
   return d1.f < d2.f ; 
}

上述运算符在内置sort()函数中工作正常：

 sort(a,a+n,myf);

但它不适用于upper_bound()功能：

 upper_bound(a,a+n,someValue,myf);

谁能告诉我我在哪里做错了？我的比较运算符错了吗？如果它是错误的，它为什么工作sort() function and not upper_bound()？

我正在关注编译：

    /usr/lib/gcc/i686-pc-linux-gnu/4.3.4/include/g++-v4/bits/stl_algo.h: In function     ‘_FIter std::upper_bound(_FIter, _FIter, const _Tp&, _Compare) [with _FIter = data*, _Tp =     int, _Compare = bool (*)(data, data)]’:
   prog.cpp:37:   instantiated from here

    /usr/lib/gcc/i686-pc-linux-gnu/4.3.4/include/g++-v4/bits/stl_algo.h:2243: error: conversion from ‘const int’ to non-scalar type ‘data’ requested
4

2 回答 2

4

您真正需要的只是operator<为您的类型创建：

inline bool operator<( const data& lhs, const data& rhs ) {
    return lhs.f < rhs.f;
}

标准算法将为您神奇地工作。

在 C++ 中，您不需要struct像在 C 中那样引用类型，并且您希望通过 const 引用传递以避免复制。

编辑0：

上面为您的类型重载了标准比较运算符<。您可以将其隐式用作：

data values[N];
// ... populate
std::sort( values, values + N );

或显式使用标准函子：

std::sort( values, values + N, std::less<data>());

编辑1：

看到编译器_Tp = int在警告中告诉你了吗？您需要将 的实例data作为第三个参数传递给upper_bound，而不是int：

data xxx = { 0, 1, 7 };
auto iter = std::upper_bound( values, values + N, xxx );

您还可以创建用于与整数进行比较的重载，例如：

inline bool operator<( const data& lhs, int rhs ) {
    return lhs.f < rhs;
}

inline bool operator<( int lhs, const data& rhs ) {
    return lhs < rhs.f;
}

使您的原始调用生效。

于 2012-10-01T14:52:02.113 回答
1

首先，它不起作用，因为upper_bound接受自定义排序的重载需要四个参数：

// http://en.cppreference.com/w/cpp/algorithm/upper_bound
template< class ForwardIt, class T, class Compare >
ForwardIt upper_bound( ForwardIt first, ForwardIt last, const T& value, 
                       Compare comp );

operator<在您为您的类型介绍的另一个答案中提出了建议。但是，不要仅仅为了一个特定的排序而这样做。仅当它们对您的类型有意义时才引入比较运算符。

如果你不遵守这条规则，未来的程序员可能会使用你的类型并想知道为什么某些东西不应该有效，反之亦然。你未来的邪恶双胞胎可能还想为他的目的使用另一种分类。

例如，它对complex-datatype 类、SIMD 类（如）有意义，但对于一个类std::valarray没有任何特定Employee意义：

Employee foo, bar;

if (bar > foo) {
    // is bar taller than foo?
    // is bar older than foo?
    // is bar working better than foo?
    // is bar bigger newbie than foo?
}

相反，您可以这样做：

namespace employee_ordering {
    struct by_name_ascending {
        bool operator() (Employee const &lhs, Employee const &rhs) const {
            return lhs.name() < rhs.name();
        }
    };

    struct by_name_descending {
        bool operator() (Employee const &lhs, Employee const &rhs) const {
            return lhs.name() > rhs.name();
        }
    }
};

....


upper_bound(first, last, ..., employee_ordering::by_name_ascending());
于 2012-10-01T15:48:56.123 回答