Efficiently moving contents of std::unordered_set to std::vector

Question

In my code I have a std::unordered_set and I need to move the data into a std::vector. I'm using the std::unordered_set while getting the data to ensure only unique values are stored prior to converting to a std::vector. My question is how do I move the contents to the std::vector the most efficiently? I don't need the std::unordered_set after the data is moved. I currently have the following:

std::copy(set.begin(), set.end(), std::back_inserter(vector));

Hewitt

Surely std::vector::reserve would help (if you're not doing that already). – Compeer

What, exactly, is your data? – Phenetole

It's numeric values. std::vector<double> – Hewitt

For double, copy is as efficient as move, but you should reserve as LogicStuff recommends. Separately, if in your case it takes time for the data to arrive (e.g. over the network, from a huge file doing async I/O etc) and you don't actually need the vector sorted, you could check whether it's the first time you've seen a value as you attempt insertion to the set, and if so also insert to the vector so it's ready to use as soon as the last input's received (though this works best if you know the number of elements to reserve beforehand). – Paracasein

Do you consider two double same if they are "nearly equal"? The default hashing maybe not enough in some cases. #14944317 – Liturgy

Answer 1

Before C++17, the best you can do is:

vector.insert(vector.end(), set.begin(), set.end());

The set's elements are const, so you can't move from them - moving is just copying.

---

After C++17, we get extract():

vector.reserve(set.size());
for (auto it = set.begin(); it != set.end(); ) {
    vector.push_back(std::move(set.extract(it++).value()));
}

Although given your comment that your data is doubles, this wouldn't matter.

Halcyon

Is set.extract(it++) really okay? What if the increment happens after the extract call invalidates the iterator? – Outofdoors

@Dan It can't. All of it++ has to happen before the function is evaluated. – Halcyon

I think before C++17 should also have a reserve – Nicknickel

@KrvPerera No, it's fine as-is. – Halcyon

@Halcyon Thanks barry I found the answer by reading some SO answers. So reserve happens upfront because they are not input iterators. I should have done more research. – Nicknickel

set.extract would rebalance the tree; is there a way to avoid that? – Cornea

Why not use a simple for(auto& element : set){ vector.push_back(std::move(element));} ? – Exhale

@Exhale as mentioned, a set only exposes const access to the elements. Moving = copying. – Kirk

It there any difference between your answer and for (auto it = set.begin(); it != set.end(); it++) { vector.push_back(std::move(set.extract(it).value())); } ? Since extract keeps the order, moving iterator should be fine. – Zodiac

@Michaël, I believe there is no rebalance for std::set per en.cppreference.com/w/cpp/container/set/extract "Extracting a node invalidates only the iterators to the extracted element, and preserves the relative order of the elements that are not erased. " – Zodiac

@LouisGo: It does rebalance. But rebalancing doesn't invalidate iterators nor change order. – Submarginal

Answer 2

I'm using C++ 17 and this approach worked fine for me:

vector<string> vec(set.begin(), set.end());

Please reference to Convert Set To Vector in C++ to more examples.

Ambsace