CODEWITHSUNDEEP
c++copystdvectorstdset
CrocodileDundee
CrocodileDundee

Reputation: 1903

C++, copy set to vector

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?

Upvotes: 171

Views: 202556

Answers (9)

Shah Fahad
Shah Fahad

Reputation: 207

Use a range constructor. According to the docs, It Constructs a container with as many elements as the range [first,last), with each element emplace-constructed from its corresponding element in that range, in the same order.

std::set <double> input;
input.insert(5);
input.insert(6);
 
// copy element from input into output using range constructor
std::vector<double> output = std::vector(input.begin(), input.end());

Upvotes: 0

James McNellis
James McNellis

Reputation: 355069

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

Upvotes: 245

Mostafa Wael
Mostafa Wael

Reputation: 3838

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

Upvotes: 3

ashish_nandan
ashish_nandan

Reputation: 1

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

Upvotes: 0

dshvets1
dshvets1

Reputation: 127

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.

Upvotes: 4

TeddyC
TeddyC

Reputation: 603

here's another alternative using vector::assign:

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

Upvotes: 53

Jacob
Jacob

Reputation: 3686

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.

Upvotes: 152

Bradley Swain
Bradley Swain

Reputation: 814

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

Upvotes: 1

Marlon
Marlon

Reputation: 20312

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

Upvotes: 27

Related Questions