2017-12-20 31 views
5

Tôi đang triển khai sắp xếp hợp nhất sẽ sắp xếp một mảng loại T. Trong phương thức merge của tôi, thuật toán gọi cho phần tử cuối cùng của danh sách bên trái và bên phải là vô cực dương. Làm cách nào tôi có thể nhận được giá trị tối đa mà một loại dữ liệu nhất định có thể giữ?Tìm giá trị tối đa cho phép đối với loại chung T

fn merge<T: PartialOrd + Copy + std::fmt::Debug>(p: usize, q: usize, r: usize, array: &mut Vec<T>) { 
    let left_size: usize = q - p; 
    let right_size: usize = r - q; 

    let mut left: Vec<T> = Vec::new(); 
    let mut right: Vec<T> = Vec::new(); 

    for i in 0..left_size { 
     left.push(array[p + i]); 
    } 

    for i in 0..right_size { 
     right.push(array[q + i]); 
    } 

    left.push(T::max_value()); //where I would put the max value 
    right.push(T::max_value()); //where I would put the max value 

    let mut i: usize = 0; 
    let mut j: usize = 0; 

    for k in p..r { 
     if left[i] <= right[j] { 
      array[k] = left[i]; 
      i += 1; 
     } else { 
      array[k] = right[j]; 
      j += 1; 
     } 
    } 
} 
+1

'mảng: & tắt Vec ' - đó là ** không ** một "mảng". Một mảng có kích thước được biết đến tại thời gian biên dịch. Xem thêm [Tại sao nó không khuyến khích chấp nhận một tham chiếu đến một String (& String), Vec (& Vec) hoặc Box (& Box) như một đối số hàm?] (Https://stackoverflow.com/q/40006219/155423). – Shepmaster

+2

FWIW, có rất nhiều điểm không thành ngữ với mã này. Bạn có thể xem xét [đăng mã làm việc của bạn lên Mã đánh giá] (https://codereview.meta.stackexchange.com/questions/5777/a-guide-to-code-review-for-stack-overflow-users). – Shepmaster

Trả lời

4

Theo tôi biết, không có cách nào để làm điều đó với thư viện chuẩn tại thời điểm này. Một cách để giải quyết nó sẽ làm cho đặc điểm của riêng bạn, thêm một đặc điểm khác được ràng buộc vào merge và thực hiện đặc điểm của bạn cho các loại bạn đang mong đợi.

Triển khai đặc điểm cụ thể cho u32 sau đó sẽ trả về std::u32::MAX và cứ tiếp tục cho các loại khác.

Đây là discussion from earlier this year.

oli_obk - ker pointed out bên dưới, thùng num đã có đặc điểm như vậy: Bounded.

+1

bạn hoàn toàn đúng. Có 'num' thùng mà đã có một đặc điểm như vậy: [' Bounded'] (http://rust-num.github.io/num/num/trait.Bounded.html) –

+0

Oh đó là tốt đẹp và tốt để biết. Không bật lên trên rustdoc tất nhiên. Tôi phải mở rộng tìm kiếm của mình lên thùng nhiều hơn. – StarSheriff

+0

hoàn hảo. Cảm ơn, tôi đã thực hiện các đặc điểm bị ràng buộc và nó hoạt động như một sự quyến rũ. – Erlich

1

Đối với một generic trên ràng buộc bạn cũng có thể quấn các loại trong một enum:

#[derive(Clone, Copy, PartialEq, PartialOrd, Debug)] 
enum UpperBounded<T> { 
    Value(T), 
    Max, 
} 

Các derived order is documented để sắp xếp Value(_) trước Max.

UpperBounded<T> sau đó có thể được sử dụng cho các vectơ leftright.

Các vấn đề liên quan