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));

Surely `std::vector::reserve` would help (if you're not doing that already). — LogicStuff, Feb 28 '17 at 22:29
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). — Tony Delroy, Feb 28 '17 at 22:41
Do you consider two double same if they are "nearly equal"? The default hashing maybe not enough in some cases. http://stackoverflow.com/questions/14943817/does-stdhash-guarantee-equal-hashes-for-equal-floating-point-numbers — Petar Petrovic, Mar 01 '17 at 04:26

score 34 · Accepted Answer · answered Feb 28 '17 at 22:33

34

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.

answered Feb 28 '17 at 22:33

Barry

286,269
29
621
977

Is `set.extract(it++)` really okay? What if the increment happens after the `extract` call invalidates the iterator? – Dan Stahlke Apr 15 '18 at 20:41
1

@Dan It can't. All of `it++` has to happen *before* the function is evaluated. – Barry Apr 16 '18 at 03:14
I think before C++17 should also have a reserve – Krv Perera May 20 '19 at 15:16
1

@KrvPerera No, it's fine as-is. – Barry May 20 '19 at 15:21
@Barry 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. – Krv Perera May 20 '19 at 17:56
`set.extract` would rebalance the tree; is there a way to avoid that? – Michaël Feb 26 '21 at 17:59
Why not use a simple `for(auto& element : set){ vector.push_back(std::move(element));}` ? – BRabbit27 May 03 '21 at 09:44
2

@BRabbit27 as mentioned, a set only exposes const access to the elements. Moving = copying. – tehhowch Jul 17 '21 at 14:30

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

1 Answers1

Linked