tr1 :: unordered_set union và intersection

Question

Cách thực hiện giao lộ và liên kết cho các tập hợp kiểu tr1 :: unordered_set trong C++? Tôi không thể tìm thấy nhiều tài liệu tham khảo về nó.

Mọi tham chiếu và mã sẽ được đánh giá cao. Cảm ơn nhiều.

Cập nhật: Tôi chỉ đoán tr1 :: unordered_set nên cung cấp chức năng cho giao lộ, công đoàn, sự khác biệt .. Vì đó là thao tác cơ bản của tập hợp. Tất nhiên tôi có thể tự viết một hàm, nhưng tôi tự hỏi liệu có được xây dựng trong hàm từ tr1 hay không. Cảm ơn bạn rất nhiều.

Answer 1

Tôi thấy rằng set_intersection() et al. từ tiêu đề algorithm sẽ không hoạt động khi chúng yêu cầu rõ ràng đầu vào của chúng được sắp xếp - hãy đoán bạn đã loại trừ chúng. Nó xảy ra với tôi rằng cách tiếp cận "ngây thơ" của iterating thông qua băm A và tìm kiếm mọi phần tử trong hash B thực sự cung cấp cho bạn hiệu suất gần tối ưu, vì tra cứu liên tiếp trong băm B sẽ đi đến cùng một thùng băm (giả sử rằng cả hai băm đều sử dụng cùng hàm băm). Điều đó sẽ cung cấp cho bạn địa phương bộ nhớ phong nha, mặc dù các thùng này gần như chắc chắn được thực hiện dưới dạng danh sách được liên kết.

Dưới đây là một số mã cho unordered_set_difference(), bạn có thể tinh chỉnh nó để làm cho các phiên bản cho bộ công đoàn và thiết lập sự khác biệt:

template <typename InIt1, typename InIt2, typename OutIt> 
OutIt unordered_set_intersection(InIt1 b1, InIt1 e1, InIt2 b2, InIt2 e2, OutIt out) { 
    while (!(b1 == e1)) { 
     if (!(std::find(b2, e2, *b1) == e2)) { 
      *out = *b1; 
      ++out; 
     } 

     ++b1; 
    } 

    return out; 
} 

Giả sử bạn có hai unordered_set s, x và y, bạn có thể đặt giao của họ trong z sử dụng:

unordered_set_intersection(
    x.begin(), x.end(), 
    y.begin(), y.end(), 
    inserter(z, z.begin()) 
); 

Không giống như bdonlan's answer, này sẽ thực sự làm việc cho bất kỳ loại chìa khóa, và bất kỳ sự kết hợp của c ontainer loại (mặc dù sử dụng set_intersection() dĩ nhiên sẽ nhanh hơn nếu các vùng chứa nguồn được sắp xếp). LƯU Ý: Nếu việc chiếm đóng thùng cao, có thể nhanh hơn để sao chép từng băm vào một số vector, sắp xếp chúng và set_intersection() chúng ở đó, vì việc tìm kiếm trong một nhóm chứa n phần tử là O (n).

Answer 2

Không có gì nhiều cho nó - đối với giao nhau, chỉ cần đi qua mọi phần tử của một và đảm bảo nó ở phần còn lại. Đối với công đoàn, hãy thêm tất cả các mục từ cả hai bộ nhập liệu.

Ví dụ:

void us_isect(std::tr1::unordered_set<int> &out, 
     const std::tr1::unordered_set<int> &in1, 
     const std::tr1::unordered_set<int> &in2) 
{ 
    out.clear(); 
    if (in2.size() < in1.size()) { 
     us_isect(out, in2, in1); 
     return; 
    } 
    for (std::tr1::unordered_set<int>::const_iterator it = in1.begin(); it != in1.end(); it++) 
    { 
     if (in2.find(*it) != in2.end()) 
      out.insert(*it); 
    } 
} 

void us_union(std::tr1::unordered_set<int> &out, 
     const std::tr1::unordered_set<int> &in1, 
     const std::tr1::unordered_set<int> &in2) 
{ 
    out.clear(); 
    out.insert(in1.begin(), in1.end()); 
    out.insert(in2.begin(), in2.end()); 
} 

Answer 3

dựa trên câu trả lời trước: C++ 11 phiên bản, nếu các thiết lập hỗ trợ một chức năng nhanh chóng nhìn lên find() (giá trị trả lại được di chuyển một cách hiệu quả)

/** Intersection and union function for unordered containers which support a fast lookup function find() 
* Return values are moved by move-semantics, for c++11/c++14 this is efficient, otherwise it results in a copy 
*/ 

namespace unorderedHelpers { 

    template<typename UnorderedIn1, typename UnorderedIn2, 
      typename UnorderedOut = UnorderedIn1> 
    UnorderedOut makeIntersection(const UnorderedIn1 &in1, const UnorderedIn2 &in2) 
    { 
     if (in2.size() < in1.size()) { 
      return makeIntersection<UnorderedIn2,UnorderedIn1,UnorderedOut>(in2, in1); 
     } 

     UnorderedOut out; 
     auto e = in2.end(); 
     for(auto & v : in1) 
     { 
      if (in2.find(v) != e){ 
       out.insert(v); 
      } 
     } 
     return out; 
    } 

    template<typename UnorderedIn1, typename UnorderedIn2, 
      typename UnorderedOut = UnorderedIn1> 
    UnorderedOut makeUnion(const UnorderedIn1 &in1, const UnorderedIn2 &in2) 
    { 
     UnorderedOut out; 
     out.insert(in1.begin(), in1.end()); 
     out.insert(in2.begin(), in2.end()); 
     return out; 
    } 
}