Merging two sets in c++

→ Обратите внимание

До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
28:55:51
Зарегистрироваться »

*есть доп. регистрация

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя kissu_pari_na

Merging two sets in c++

Автор kissu_pari_na, история, 7 лет назад, По-английски

Is there any solution that will merge two sets in n=( size_of_se1 + size_of_set2 ) times in c++? If I iterate through both the sets and take the smaller value and insert it in another set, this way I can merge two sets but it will take close to n*logn time as set insert operation takes logn time. Also I can let the set1 unchanged and insert all the elements of set2 in set1 or vice versa but it will also take size_of_set2*log(size_of_set1) or size_of_set1*log(size_of_set2) time. I am searching for a solution if it is actually possible to merge two sets in linear time. I googled it and spend some time to find out any solution regarding to it but failed :( Can anyone help me with your valuable opinion? thanks in advance :)

kissu_pari_na
7 лет назад
11

Комментарии (10)

Показать архивные | Написать комментарий?

fofao_funk

7 лет назад, # |

+37

According to this and this, this should be linear:

#include <bits/stdc++.h>

using namespace std;

const int INF = 1e9;

int main() {
	set<int> a {1, 3, 7, 10, 13, 20};
	set<int> b {2, 3, 5, 7, 11, 13, 15, 19};
	
	vector<int> v;
	merge(a.begin(), a.end(), b.begin(), b.end(), back_inserter(v));
	
	set<int> m(v.begin(), v.end());
	
	for(const auto &element : m) {
		cout << element << " ";
	}
	cout << endl;
	
	return 0;
}

→ Ответить

AlexandruValeanu

7 лет назад, # ^ |

← Rev. 2 →

You can get rid of set<int> m(v.begin(), v.end()); by using:

set<int> m;
merge(a.begin(), a.end(), b.begin(), b.end(), inserter(m, m.end()));

→ Ответить

kissu_pari_na

7 лет назад, # ^ |

Got it. Thanks :)

→ Ответить

collares

7 лет назад, # ^ |

← Rev. 14 →

Is this guaranteed to be linear time, though? (Edit: I believe the answer is "probably not linear-time, but it's super tricky". See next paragraph.) fofao_funk's solution is clearly linear time, as inserting N elements into a vector and constructing a set from an ordered vector (see section 23.4.6.2 of the C++11 standard, or section 26.4.6.2 of the C++17 standard) are both linear-time operations.

I previously thought yours could be implementation-dependent, as suggested by the fact that using set::insert to insert a sorted range is not guaranteed to to take linear time. However, the standard says set::insert(p, t) takes "amortized constant time if t is inserted right before p" (technically this says nothing about duplicate elements, but let's ignore that), so that strongly suggests your solution is guaranteed to be linear time. However, the plot thickens! Here's what the inserter does:

iter = container->insert(iter, value);
++iter;

If it just did a bunch of container->insert(container.end(), value) operations, that would be amortized constant time per the standard. It does not do that, though: It inserts at m.end(), then takes the iterator to just-added element and advances it (thus making it point to m.end() again). This last iterator-advancing operation is probably not guaranteed to be amortized constant time.

→ Ответить

kissu_pari_na

7 лет назад, # ^ |

I just run the code and check the runtime. But is there any constant time factor, I am not sure? When I ran the code it shows slightly higher time complexity than linear. If I think logically surely it is linear.

→ Ответить