C++, copy set to vector

Question

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?

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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.

Answer 5

set<T> s;
// some code
vector<T> v;
v.assign(s.begin(), s.end());

Answer 6

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

Answer 7

here's another alternative using vector::assign:

theVector.assign(theSet.begin(), theSet.end());

Answer 8

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.