168

I need to copy std::set to std::vector:

std::set <double> input;
input.insert(5);
input.insert(6);

std::vector <double> output;
std::copy(input.begin(), input.end(), output.begin()); //Error: Vector iterator not dereferencable

Where is the problem?

3
  • 7
    there is also assign() function: output.assign(input.begin(), input.end()); Feb 17, 2011 at 20:40
  • 2
    your vector is empty. There are a multitude of ways to remedy that though as people are pointing out below.
    – AJG85
    Feb 17, 2011 at 20:53
  • 1
    @Gene: assign() wants to reserve() the necessary amount of storage ahead of time. It will use the input iterators to determine how much is needed, unless the iterators are strictly InputIterator, in which case it will skip reserving and result in reallocations on every push_back(). On the opposite end of the spectrum, BiderectionalIterators would allow it to just subtract end - begin. std::set's iterators, however, are neither (they are ForwardIterator), and that's unfortunate: in this case, assign() will just walk the entire set to determine its size -- bad performance on large sets. Jul 10, 2015 at 22:33

8 Answers 8

241

You need to use a back_inserter:

std::copy(input.begin(), input.end(), std::back_inserter(output));

std::copy doesn't add elements to the container into which you are inserting: it can't; it only has an iterator into the container. Because of this, if you pass an output iterator directly to std::copy, you must make sure it points to a range that is at least large enough to hold the input range.

std::back_inserter creates an output iterator that calls push_back on a container for each element, so each element is inserted into the container.

Alternatively, you could have created a sufficient number of elements in the std::vector to hold the range being copied:

std::vector<double> output(input.size());
std::copy(input.begin(), input.end(), output.begin());

Or, you could use the std::vector range constructor:

std::vector<double> output(input.begin(), input.end()); 
5
  • 3
    Hi James, instead of your std::copy line (the first code block in your answer), couldn't I just do output.insert(output.end(), input.begin(), input.end()); instead? Feb 10, 2013 at 10:55
  • or just use the cbegin and cend version: output.insert(output.cend(), input.cbegin(), input.cend()); What do you think? Thanks. Feb 10, 2013 at 12:12
  • 2
    Should I output.reserve(input.size()); by myself or can I hope that some compiler does it for me?
    – jimifiki
    Mar 27, 2014 at 13:19
  • @jimifiki, no hope I'm afraid. Sep 29, 2019 at 10:50
  • Your first vector initialization is incorrect. You create an array of input,size() empty entries and then append the appends after that. I think you mean to use std::vector<double> output; output.reserve(input.size()); std::copy(...);. Sep 29, 2019 at 10:51
149

Just use the constructor for the vector that takes iterators:

std::set<T> s;

//...

std::vector v( s.begin(), s.end() );

Assumes you just want the content of s in v, and there's nothing in v prior to copying the data to it.

0
53

here's another alternative using vector::assign:

theVector.assign(theSet.begin(), theSet.end());
1
  • That works, but as @SergeyShevchenko commented at the q., this might want to repeatedly reallocate the vector, as it grows, while iterating through the set.
    – Sz.
    Feb 4, 2022 at 0:02
27

You haven't reserved enough space in your vector object to hold the contents of your set.

std::vector<double> output(input.size());
std::copy(input.begin(), input.end(), output.begin());
4
  • 1
    This doesn't deserve -1. In particular, this allows vector to only do one allocation (since it can't determine the distance of set iterators in O(1)), and, if it wasn't defined for vector to zero out each element when constructed, this could be worthwhile to allow the copy to boil down to a memcpy. The latter could still be worthwhile if the implementation figures out the loop in vector's ctor can be removed. Of course, the former can also be achieved with reserve.
    – Fred Nurk
    Feb 17, 2011 at 20:42
  • 1
    I gave you a -1, but it was a thinko on my part. Make a small edit so I can undo my vote, and I'll give you a +1: this is actually a very clean solution because of the fail-first property.
    – Fred Foo
    Feb 17, 2011 at 23:04
  • 1
    I only just figured out that if I edit the answer myself, I can do an upvote. Did that, gave you a +1 for the fail-first memory allocation. Sorry!
    – Fred Foo
    Feb 27, 2011 at 13:51
  • Also, very important that it's not just "reserving" enough space that's needed, but also initializing (default-constructing) those instance slots. So, just calling output.reserve(input.size()) wouldn't be enough.
    – Sz.
    Feb 17, 2022 at 23:17
4

I think the most efficient way is to preallocate and then emplace elements:

template <typename T>
std::vector<T> VectorFromSet(const std::set<T>& from)
{
    std::vector<T> to;
    to.reserve(from.size());

    for (auto const& value : from)
        to.emplace_back(value);

    return to;
}

That way we will only invoke copy constructor for every element as opposed to calling default constructor first and then copy assignment operator for other solutions listed above. More clarifications below.

  1. back_inserter may be used but it will invoke push_back() on the vector (https://en.cppreference.com/w/cpp/iterator/back_insert_iterator). emplace_back() is more efficient because it avoids creating a temporary when using push_back(). It is not a problem with trivially constructed types but will be a performance implication for non-trivially constructed types (e.g. std::string).

  2. We need to avoid constructing a vector with the size argument which causes all elements default constructed (for nothing). Like with solution using std::copy(), for instance.

  3. And, finally, vector::assign() method or the constructor taking the iterator range are not good options because they will invoke std::distance() (to know number of elements) on set iterators. This will cause unwanted additional iteration through the all set elements because the set is Binary Search Tree data structure and it does not implement random access iterators.

Hope that helps.

2
  • please add a reference to an authority why this is fast and something like why a back_inserter doesn't need to be used Jun 12, 2019 at 19:37
  • Added more clarifications in the answer.
    – dshvets1
    Jun 13, 2019 at 14:37
2
set<T> s;
// some code
vector<T> v;
v.assign(s.begin(), s.end());
1

std::copy cannot be used to insert into an empty container. To do that, you need to use an insert_iterator like so:

std::set<double> input;
input.insert(5);
input.insert(6);

std::vector<double> output;
std::copy(input.begin(), input.end(), inserter(output, output.begin())); 
1
  • 4
    This fails the first time the vector reallocates: the iterator from output.begin() gets invalidated.
    – Fred Nurk
    Feb 17, 2011 at 21:02
0

The COPY function returns an iterator to the end of the destination range (which points to the element following the last element copied).

A back-insert iterator is a special type of output iterator designed to allow algorithms that usually overwrite elements (such as copy) to instead insert new elements automatically at the end of the container.

set os; vector vec;

copy(os.begin(), os.end(), back_inserter(vec));

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.