C++ nhận chỉ mục của phần tử mảng theo giá trị

Question

Cho đến nay, tôi đã lưu trữ mảng trong một vectơ và sau đó lặp qua vectơ để tìm phần tử phù hợp và sau đó trả về chỉ mục.

Có cách nào nhanh hơn để thực hiện việc này trong C++ không? Cấu trúc STL mà tôi sử dụng để lưu trữ mảng không thực sự quan trọng đối với tôi (nó không phải là một vectơ). Mảng của tôi cũng là duy nhất (không có phần tử lặp lại) và được sắp xếp (ví dụ: danh sách các ngày chuyển tiếp theo thời gian).

Answer 1

Vì các phần tử được sắp xếp, bạn có thể sử dụng tìm kiếm nhị phân để tìm phần tử phù hợp. Thư viện chuẩn C++ có một thuật toán std::lower_bound có thể được sử dụng cho mục đích này. Tôi muốn giới thiệu gói nó trong thuật toán tìm kiếm nhị phân của riêng bạn, cho rõ ràng và đơn giản:

/// Performs a binary search for an element 
/// 
/// The range `[first, last)` must be ordered via `comparer`. If `value` is 
/// found in the range, an iterator to the first element comparing equal to 
/// `value` will be returned; if `value` is not found in the range, `last` is 
/// returned. 
template <typename RandomAccessIterator, typename Value, typename Comparer> 
auto binary_search(RandomAccessIterator const first, 
        RandomAccessIterator const last, 
        Value    const& value, 
        Comparer     comparer) -> RandomAccessIterator 
{ 
    RandomAccessIterator it(std::lower_bound(first, last, value, comparer)); 
    if (it == last || comparer(*it, value) || comparer(value, *it)) 
     return last; 

    return it; 
} 

(C++ thư viện chuẩn có std::binary_search, nhưng nó trả về một bool: true nếu phạm vi chứa các phần tử, false khác. Nó không hữu ích nếu bạn muốn một iterator cho phần tử.)

Khi bạn có một trình lặp cho phần tử, bạn có thể sử dụng thuật toán std::distance để tính chỉ mục của phần tử trong phạm vi.

Cả hai thuật toán này hoạt động tốt như nhau bất kỳ chuỗi truy cập ngẫu nhiên nào, bao gồm cả std::vector và mảng thông thường.

Answer 2

Nếu bạn muốn kết hợp giá trị với chỉ mục và tìm chỉ mục nhanh chóng, bạn có thể sử dụng std::map hoặc std::unordered_map. Bạn cũng có thể kết hợp chúng với các cấu trúc dữ liệu khác (ví dụ: std::list hoặc std::vector) tùy thuộc vào các hoạt động khác mà bạn muốn thực hiện trên dữ liệu.

Ví dụ, khi tạo vector chúng tôi cũng tạo ra một bảng tra cứu:

vector<int> test(test_size); 
unordered_map<int, size_t> lookup; 
int value = 0; 
for(size_t index = 0; index < test_size; ++index) 
{ 
    test[index] = value; 
    lookup[value] = index; 
    value += rand()%100+1; 
} 

Bây giờ để tìm kiếm các chỉ số bạn chỉ đơn giản là:

size_t index = lookup[find_value]; 

Sử dụng một bảng băm cấu trúc dữ liệu dựa (ví dụ unordered_map) là một sự cân bằng không gian/thời gian khá cổ điển và có thể hoạt động tốt hơn khi thực hiện tìm kiếm nhị phân cho loại hoạt động tra cứu "đảo ngược" này khi bạn cần thực hiện nhiều tra cứu. Ưu điểm khác là nó cũng hoạt động khi véc tơ được phân loại.

Đối với niềm vui :-) tôi đã thực hiện một chuẩn mực nhanh chóng trong VS2012RC so sánh mã tìm kiếm nhị phân James' với một tìm kiếm tuyến tính và với việc sử dụng unordered_map cho tra cứu, tất cả trên một vector:

Để ~ 50000 yếu tố unordered_set đáng kể (x3-4) vượt trội so với tìm kiếm nhị phân biểu hiện hành vi O (log N), kết quả hơi ngạc nhiên là unordered_map mất hành vi O (1) của nó vượt quá 10000 phần tử, có lẽ do va chạm băm, có lẽ là thực hiện vấn đề.

CHỈNH SỬA: max_load_factor() cho bản đồ không có thứ tự là 1 vì vậy sẽ không có xung đột. Sự khác biệt về hiệu suất giữa tìm kiếm nhị phân và bảng băm cho các vectơ rất lớn dường như là bộ nhớ đệm có liên quan và thay đổi tùy thuộc vào mẫu tra cứu trong điểm chuẩn.

Choosing between std::map and std::unordered_map nói về sự khác biệt giữa bản đồ đặt hàng và không có thứ tự.