Trong chỗ C++ thiết lập giao

Question

Cách chuẩn giao nhau hai bộ trong C++ là phải làm như sau:

std::set<int> set_1; // With some elements 
std::set<int> set_2; // With some other elements 
std::set<int> the_intersection; // Destination of intersect 
std::set_intersection(set_1.begin(), set_1.end(), set_2.begin(), set_2.end(), std::inserter(the_intersection, the_intersection.end())); 

Làm thế nào tôi sẽ đi về làm một bộ giao nhau tại chỗ? Đó là, tôi muốn set_1 có kết quả của cuộc gọi đến set_intersection. Rõ ràng, tôi chỉ có thể làm một set_1.swap(the_intersection), nhưng điều này là rất ít hiệu quả hơn so với giao nhau tại chỗ.

Answer 1

Tôi nghĩ rằng tôi đã có nó:

std::set<int>::iterator it1 = set_1.begin(); 
std::set<int>::iterator it2 = set_2.begin(); 
while ((it1 != set_1.end()) && (it2 != set_2.end())) { 
    if (*it1 < *it2) { 
     set_1.erase(it1++); 
    } else if (*it2 < *it1) { 
     ++it2; 
    } else { // *it1 == *it2 
      ++it1; 
      ++it2; 
    } 
} 
// Anything left in set_1 from here on did not appear in set_2, 
// so we remove it. 
set_1.erase(it1, set_1.end()); 

Bất cứ ai nhìn thấy bất kỳ vấn đề? Có vẻ là O (n) trên kích thước của hai bộ. Theo cplusplus.com, std :: đặt xóa (vị trí) là hằng số khấu hao trong khi xóa (đầu tiên, cuối cùng) là O (log n).

Answer 2

Bạn có thể dễ dàng đi qua set_1, kiểm tra từng yếu tố để xem liệu nó có tồn tại trong set_2 và xóa nó nếu không. Vì tập hợp được sắp xếp, bạn có thể so sánh chúng theo thời gian tuyến tính và xóa một phần tử bằng cách sử dụng trình lặp là amortized constant time. Tôi sẽ không dựa vào đó là hiệu quả hơn những gì bạn bắt đầu với mặc dù, điểm chuẩn sẽ là khôn ngoan nếu nó quan trọng với bạn.