我如何才能要求可以比较泛型类型的引用与泛型类型的相等性? [英] How can I require that a reference to a generic type can be compared for equality against the generic type?
问题描述
我正在尝试实现一种依赖于模幂的算法.我找不到像 u64
这样的本机类型(仅适用于 bigint)的任何模块化求幂构造,所以我想我会编写一个标准的 通过重复平方方法取模.
I'm trying to implement an algorithm which relies on modular exponentiation. I couldn't find any modular exponentiation construct for native types like u64
(only for bigints), so I figured I'd code a standard modular exponentiation by repeated squaring method.
这是我想出的:
fn powm(base: &u64, exponent: &u64, modulus: &u64) -> u64 {
if *modulus == 1u64 {
0
} else {
let mut result = 1;
let mut base = self % modulus;
let mut exp = *exponent;
while exp > 0 {
if exp % 2 == 1 {
result = (result * base) % modulus;
}
exp >>= 1;
base = (base * base) % modulus;
}
result
}
}
这很好用.现在,我想让这个函数通用,以便它也适用于 u64
以外的数字类型.这是我开始有点迷失的地方.
This works fine. Now, I'd like to make this function generic so that it also works for numeric types other than u64
. This is where I start to get a bit lost.
我找到了 num 箱子,它有一个 Num
特征,指定基本的数字运算.在分离出一个新的 PowM
trait 并创建了一堆 trait bound 之后,我得到了:
I found the num crate, which has a Num
trait that specifies basic numeric operations. After separating out a new PowM
trait and creating a bunch of trait bounds, I end up with:
extern crate num;
use num::Num;
use std::ops::{ShrAssign,Rem};
pub trait PowM {
fn powm(&self, exponent: &Self, modulus: &Self) -> Self;
}
pub trait Two {
fn two() -> Self;
}
impl Two for u64 {
fn two() -> u64 { return 2u64 }
}
impl Two for usize {
fn two() -> usize { return 2usize }
}
impl<T> PowM for T
where T: Num + Two + ShrAssign<T> + Rem<T> + PartialOrd<T> {
fn powm(&self, exponent: &T, modulus: &T) -> T {
if modulus == T::one() {
T::zero()
} else {
let mut result = T::one();
let mut base = *self % *modulus;
let mut exp = *exponent;
while exp > T::zero() {
if exp % T::two() == T::one() {
result = (result * base) % *modulus;
}
exp >>= T::one();
base = (base * base) % *modulus;
}
result
}
}
}
编译器给出的唯一抱怨如下
The only complaint the compiler gives is the following
error[E0277]: the trait bound `&T: std::cmp::PartialEq<T>` is not satisfied
|
30 | if modulus == T::one() {
| ^^ can't compare `&T` with `T`
|
= help: the trait `std::cmp::PartialEq<T>` is not implemented for `&T`
= help: consider adding a `where &T: std::cmp::PartialEq<T>` bound
我正在尝试添加特征边界,但最终遇到了很多关于我不完全理解的生命周期的编译器错误,并最终陷入了以下问题:
I'm trying to add the trait bounds, but end up chasing a lot of compiler errors about lifetimes I do not fully understand, and end up stuck with the following:
impl<'a, T> PowM for T
where T: 'a + Num + Two + ShrAssign<T> + Rem<T> + PartialOrd<T>,
&'a T: PartialEq<T> {
fn powm(&self, exponent: &T, modulus: &T) -> T {
if modulus == T::one() {
[...]
仍然会出错.我该如何解决这个问题?
which still gives errors. How do I fix this?
推荐答案
您可以忽略该问题并将引用与引用或非引用与非引用进行比较:
You can either ignore the problem and compare a reference to a reference or non-reference to a non-reference:
if modulus == &T::one() {
// Or
if *modulus == T::one() {
或者你可以使用排名更高的特征边界:
impl<T> PowM for T
where
T: Num + Two + ShrAssign<T> + Rem<T> + PartialOrd<T>,
for <'a> &'a T: PartialEq<T>,
{
// ...
}
无论哪种情况,您都需要要求 T
实现 Copy
或者它实现 Clone
,然后向 添加适当的调用.clone()
.
In either case, you need to require that T
implements Copy
or that it implements Clone
and then add appropriate calls to .clone()
.
另见:
这篇关于我如何才能要求可以比较泛型类型的引用与泛型类型的相等性?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!