khoảng cách giữa std :: set begin() và std :: set iterator trong O (logn)

Question

Tôi cần tìm chỉ mục của phần tử trong std :: set. Chỉ số này có thể được hình dung như là khoảng cách của trình lặp từ đầu. Một cách có thể là:

for(int i = 0, set<int>::iterator it = s.begin(); it != iteratorToBeFound; ++it, ++i); 

Điều này rõ ràng mất thời gian O (n). Nhưng chúng ta biết rằng khoảng cách từ gốc trong cây tìm kiếm nhị phân như được thực hiện bởi tập hợp nội bộ có thể được tìm thấy trong thời gian O (log n).

Có cách nào để thực hiện tương tự để tìm chỉ mục trong thời gian O (log n) trong C++ không?

Answer 1

Bạn có thể sử dụng được sắp xếp std::vector<int> . Nếu nó được sắp xếp, bạn có thể tìm phần tử trong O(log n). Và bạn có thể tìm khoảng cách trong thời gian không đổi O(1).

By vector được sắp xếp Tôi có nghĩa là sau mỗi lần chèn (hoặc sau nhiều chèn) bạn làm std::sort(v.begin(), v.end());

Nếu loại của bạn bên trong std::set<T> không phải là ánh sáng như int - bạn có thể giữ cả hai - std::set<T> và sắp xếp vector vòng lặp std::vector<std::set<T>::iterator> . Nhưng nó không thể tầm thường để giữ cho các cấu trúc này được đồng bộ. Có thể bạn có thể thêm một số vị trí như vậy vào T? Hoặc giữ std::set<std::pair<T,int>, comp_first_of_pair<T>> trong đó comp_first_of_pair chỉ để có set chỉ được sắp xếp theo T và thứ hai int là để giữ vị trí trong nhóm?

Chỉ cần một vài ý tưởng - có thậm chí O(1) thời gian khoảng cách ...

Answer 2

Bạn có thể sử dụng chức năng std::set<>::find để tìm kiếm một yếu tố x và tính distance đến iterator đầu tiên của bộ này.

std::distance(s.begin(), s.find(x)) 

Tuy nhiên, khi nhận xét cho biết thời gian chạy phụ thuộc vào loại trình lặp được sử dụng. Trong trường hợp của một bộ này là một iterator hai chiều và khoảng cách là O (n).

Answer 3

Bạn không thể sử dụng matematics với trình vòng lặp hai chiều. Vì vậy, chỉ có cách chấp nhận được là tự tính (có bao nhiêu int nhỏ hơn X bạn đã lắp vào bộ).

Nhưng, nếu bạn đã sạch sẽ tách ra "thu thập dữ liệu" và "sử dụng thông tin" giai đoạn - có lẽ nó là giá trị để thay thế std :: set với sắp xếp std :: vector. Nó khó khăn hơn để duy trì, nhưng có những lợi ích riêng, bao gồm matematics iterator (do đó bạn có thể nhận được tìm kiếm với O (log n) với std :: binary_search và khoảng cách với O (1))

Answer 4

Nếu tính toán chỉ số này thực sự nút cổ chai của bạn, sau đó tôi nhìn thấy 2 lựa chọn:

• Store chỉ mục. Hoặc trong chính các nút hoặc trong một riêng biệt std::map. Tất nhiên điều này có nghĩa là bạn phải cập nhật bộ nhớ cache này.
• Sử dụng số std::vector. Đó không phải là xấu như nó có thể nhìn vào đầu tiên. Nếu bạn giữ cho véc-tơ luôn được sắp xếp, bạn có thể sử dụng nó như một set. Hiệu suất sẽ tương tự như set. Hạn chế lớn nhất là: nút có thể được sao chép rất nhiều. (Điều này có thể được bù bằng cách sử dụng con trỏ, boost:shared_ptr hoặc std::unique_ptr [chỉ C++ 11])
  Để tra cứu phần tử bạn sử dụng std::lower_bound.
  Thay vì chèn/đẩy_back bạn làm: insert(lower_bound(b,e,x), x)