0

鉴于我有一个数据结构，

struct data{
int val;
};
struct data A[LEN]; // LEN: some length.

// the below operator would be used in sorting.
bool operator < (struct data &a1, struct data &a2){
return a1.val < a2.val;
}

int main(){
// fill up A.
sort(A, A+LEN); // sort up A

/*Now I want something like this to happen ..
x = find(A, A+LEN, value); -> return the index such that A[index].val = value,
find is the stl find function .. 
*/
}

你是怎样做的 ？对于任何 stl 函数，您如何知道要覆盖哪些运算符以使其在给定条件下工作？

4

2 回答 2

3

在这种情况下查找元素所需的修改非常少。首先，你想让你operator<的论点作为const参考（技术上对于当前的练习来说不是必需的，但是你通常想要做的事情）：

bool operator < (data const &a1, data const &a2){
    return a1.val < a2.val;
}

然后（真正重要的部分std::find）你还需要定义一个operator==：

bool operator==(data const &a, data const &b) { 
    return a.val == b.val;
}

但是请注意，如果您使用二进制搜索，则不必定义它：

auto pos = std::lower_bound(data, data+LEN, some_value);

这将只使用operator<您已经定义的。如果项目已经排序，这通常会更可取（通常会快一点，除非 LEN 非常小）。

于 2013-07-21T05:06:39.523 回答
2

如果您只想使std::find为您的结构数组工作，则需要operator==为结构数据定义：

struct data
{
   data(int value=0) : val(value) {}
   int val;
};

bool operator==(const data& l, const data& r) { return l.val == r.val;}

auto x = find(A, A+LEN, value);

或者

auto x = find(A, A+LEN, data(value));

要获取 A 中的值索引，请使用std::distance

std::distance(A, x);

注意：要使用排序容器进行更充分的搜索，请改用std::lower_bound、std::uppper_bound、std::binary_search。

auto lower = std::lower_bound(A, A+LEN, data(3));
auto upper = std::upper_bound(A, A+LEN, data(3));

你的operator<函数签名最好像：

bool operator < (const data &a1, const data &a2)
//               ^^^^^           ^^^^^
于 2013-07-21T05:05:46.833 回答