CODEWITHSUNDEEP
c++setmultiset
Jun
Jun

Reputation: 301

Efficient way to convert multiset to set

Is there an efficient way to convert multiset to set, instead of loop all elements in multimap, test if set has the element, if yes insert if not continue? For multiset and set, I prefer using stock C++ containers, but other language implementation are also OK.

Upvotes: 0

Views: 2381

Answers (3)

Yong
Yong

Reputation: 444

I am not sure that above answers are most efficient.

Items in multiset is ordered, but the constructor of set probably doesn't know that, and will perform a lookup on every insert.

Try this:

std::set<T> result;
for (auto item: the_multiset) {
    result.insert(result.end(), item);
}

But it is still not perfect because it will walk through all duplicate values one by one, and if there are a large number of duplicate values, it wastes time. Because it is a multiset, so the internal data can just be something like a map<key, count>, and it should allow developer to go directly to next different value. I hope this can happen in future C++.

Upvotes: 0

user3504726
user3504726

Reputation:

You can create a set from an existing multiset

template<typename T>
set<T> SetFromMultiset(multiset<T> const &ms)
{
    set<T> ret(ms.cbegin(), ms.cend())
    return ret;
}

I'm supposing you are using c++11, so there is no overhead in returning a container by value, only a move operation (even though this is a case where RVO would apply)

Upvotes: 3

Mark B
Mark B

Reputation: 96241

std::set<T> new_set(multiset_obj.begin(), multiset_obj.end(); should do the trick. Let the language and container requirements be your friend.

Upvotes: 3

Related Questions