set_union với nhiều vùng chứa?

Question

Sự trở lại của thuật toán std: set_union khi một hoặc cả hai vùng chứa đầu vào là multisets với các đối tượng trùng lặp là gì? Do dups bị lạc?

Giả sử ví dụ:

multiset<int> ms1; 
ms1.insert(1); 
ms1.insert(1); 
ms1.insert(1); 
ms1.insert(2); 
ms1.insert(3); 

multiset<int> ms2; 
ms2.insert(1); 
ms2.insert(1); 
ms2.insert(2); 
ms2.insert(2); 
ms2.insert(4); 

vector<int> v(10); 
set_union(ms1.begin(), ms1.end(), ms2.begin(), ms2.end(), v.begin()); 

sẽ đầu ra được gì?

Answer 1

Từ tiêu chuẩn, 25.3.5:

Ngữ nghĩa của hoạt động thiết lập được khái quát hóa để multisets trong một cách tiêu chuẩn bằng cách định nghĩa union() để chứa số lượng tối đa lần xuất hiện của mỗi phần tử, intersection() để chứa các tối thiểu, v.v.

Vì vậy, trong ví dụ của bạn, kết quả sẽ là (1,1,1,2,2,3,4,0,0,0), kể từ khi bạn khởi tạo vector có chiều dài 10

Answer 2

Từ số documentation of std::set_union (được thêm vào).

Trong trường hợp đơn giản nhất, set_union thực hiện thao tác "union" từ lý thuyết tập hợp: phạm vi đầu ra chứa bản sao của mọi phần tử được chứa trong [first1, last1), [first2, last2) hoặc cả hai. Trường hợp chung phức tạp hơn, vì phạm vi nhập liệu có thể chứa các phần tử trùng lặp. Khái quát hóa là nếu một giá trị xuất hiện m lần trong [first1, last1) và n lần trong [first2, last2) (trong đó m hoặc n có thể bằng 0), thì nó xuất hiện tối đa (m, n) lần trong phạm vi đầu ra. [1] Set_union ổn định, có nghĩa là cả thứ tự tương đối của các phần tử trong mỗi phạm vi đầu vào đều được giữ nguyên và nếu phần tử có mặt trong cả hai phạm vi đầu vào, nó được sao chép từ dãy đầu tiên chứ không phải thứ hai.

Nó sẽ xuất hiện max(m,n) lần nơi m là số lần nó xảy ra trong ms1 và n là số lần nó xảy ra trong ms2.

Answer 3

Từ tiêu chuẩn C++, §25.3.5/1:

Phần này xác định tất cả các hoạt động thiết lập cơ bản về cấu trúc được sắp xếp. Họ cũng làm việc với multisets (23.3.4) chứa nhiều bản sao của các phần tử tương đương. Ngữ nghĩa của các hoạt động thiết lập được khái quát hóa thành nhiều bộ theo một cách tiêu chuẩn bằng cách xác định union() để chứa số lần xuất hiện tối đa của mỗi phần tử, giao nhau() để chứa giá trị tối thiểu, v.v.