Get this book -> Problems on Array: For Interviews and Competitive Programming

In this article, we have explored different ways to convert vector to set in C++.

**Introduction**

Vectors and Sets are both containers in C++. Containers are objects which are capable of storing multiple objects of the same type. Containers are usually called STL containers since their classes are defined in the Standard Template Library. In C++ there are three kinds of STL containers: sequential, associative and unordered associative STL containers.

- Sequential containers store elements which are accessed in sequential order.
- Associative containers store elements in a sorted order.
- Unordered associative containers provide unsorted versions of associated containers.

## Vectors vs Sets

Vectors are sequential STL containers. Access to elements of a vector is sequential just like linkedlists.Some common methods associated with vectors are `size()`

, `capacity()`

, `begin()`

and `end()`

. Vectors in C++ are internally implemented using linkedlists.

```
#include <iostream>
#include <vector>
using namespace std;
//print a vector of integers
void printVector( vector<int> v){
cout << "vector: "
for (auto i: v){
cout << i << ",";
}
cout << endl;
}
int main(){
//create a vectors of integers
vector<int> my_vector = {3, 10, 1, 0, 4};
printVector(my_vector);
return 0;
```

*output*

vector: 3,10,1,0,4,

A set is a type of associative STL container with no duplicate elements. Inserting an element already present in a set is not possible. Being associative containers, elements of sets are always sorted no matter the order in which they are inserted or initialized. Some common method associated to sets are `begin()`

, `end()`

, `empty()`

, and `size()`

. Sets in C++ are internally implemented using binaries trees.

```
#include <iostream>
#include <set>
using namespace std;
//print any set of integers
void printSet(set<int> s){
cout << "Set: ";
for(auto i: s){
cout << i << ",";
}
cout << endl;
}
int main(){
//create an initialized set of integers
set<int> my_set = {3, 1, 0, 1, 4, 8};
printSet(my_set);
return 0;
}
```

output:

Set: 0,1,3,4,8,

## Converting vectors to sets

### Solution 1: Trivial solution.

This consists of simply creating a set and inserting the elements of the vectors in it.

### Pseudocode

-create an empty set of same type like vector elements

-move through the vector and insert each elements of the vector in the set.

### Complexity

*Time complexity*

worst case: O(nlogn)

Average case:O(nlogn)

Best case: O(nlogn)

n being the size of the vector, iterate n times with each iteration consisting of and insertion of O(logn)

*Space complexity:* O(1)

### Implementation

```
#include <iostream>
#include <vector>
#include <set>
//method 1
set<int> vectorToSet(vector<int> my_vector){
set<int> my_set;
for(auto i: my_vector){
my_set.insert(i);
}
return my_set;
}
//print a vector of integers
void printVector( vector<int> v){
cout << "vector: "
for (auto i: v){
cout << i << ",";
}
cout << endl;
}
//print a set of integers
void printSet(set<int> s){
cout << "Set: ";
for(auto i: s){
cout << i << ",";
}
cout << endl;
}
int main(){
vector<int> v = {3, 0, 3, 1, -1, 4, 8, 2};
set<int> s = vectorToSet(v);
printVector(v);
printSet(s);
return 0;
}
```

*output*

vector: 3,0,3,1,-1,4,8,2,

Set: -1,0,1,2,3,4,8,

### Solution 2: Using range converter

Define a set which is initialized with elements by copying elements of a vector using `begin()`

and `end()`

methods of the vector, returning two iterators which point to the first and last elements of the vectors. Iterators are objects which points to elements of STL containers and can iterate over the containers.

### Complexity

*Time complexity*

Worst case: O(n)

Average case: O(n)

Best case: O(n)

n being the length of the vector.

*Space complexity:* O(1)

### Implementation

```
#include <iostream>
#include <set>
#include <vector>
using namespace std;
//method 2
set<int> vectorToSet(vector<int> my_vector){
set<int> s(my_vector.begin(), my_vector.end());
return s;
}
//print a vector of integers
void printVector( vector<int> v){
cout << "vector: "
for (auto i: v){
cout << i << ",";
}
cout << endl;
}
//print a set of integers
void printSet(set<int> s){
cout << "Set: ";
for(auto i: s){
cout << i << ",";
}
cout << endl;
}
int main(){
vector<int> v = {4, 1, -1, 3, 1, 4, 8};
set<int> s = vectorToSet(v);
printVector(v);
printSet(s);
}
```

*output*

vector: 4,1,-1,3,1,4,8,

Set: -1,1,3,4,8,

### Solution 3: Using the copy method

`copy()`

is a function defined in `<algorithm>`

which copies a range of elements into a new location.

Declaration:

```
OutputIterator copy(InputIterator begin, InputIterator end, OutputIterator result);
```

`begin`

iterator at beginning of source

`end`

iterator at end of source

`result`

iterator at initial position of new sequence

The return is of type `OutputIterator`

which corresponds to result iterator pointing to the last position in the new sequence.

### Pseudocode

```
OutputIterator copy(InputIterator begin, InputIterator end, OutputIterator reuslt){
while (begin!=end) {
^result = ^begin;
++result; ++begin;
}
return result;
}
```

### Complexity

*Time complexity*

Worst case: O(n)

Average case: O(n)

Best case: O(n)

*Space complexity:* O(1);

### Implementation

```
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
//method 3
set<int> vectorToSet(vector<int> v){
set<int> s;
copy( v.begin(), v.end(), inserter(s,s.end()));
return s;
}
//print a vector of integers
void printVector( vector<int> v){
cout << "vector: "
for (auto i: v){
cout << i << ",";
}
cout << endl;
}
//print a set of integers
void printSet(set<int> s){
cout << "Set: ";
for(auto i: s){
cout << i << ",";
}
cout << endl;
}
int main(){
vector<int> v = {1, 3, -1, 4};
set<int> s = vectorToSet(v);
printVector(v);
printSet(s);
return 0;
}
```

### Applications

Converting vectors to sets can be useful in the following situations

-Eliminating multiple occurrence of values in a list.

-Sorting a list without taking into account multilple occurrences of any value.

### Question

What if we passed the iterator parameter `s.end()`

in `copy()`

of solution 3 rather than `inserter(s, s.end())`

?

options:

a.nothing happens and the program runs fine.

b.compiler error arises.

c.program compiles but runtime error arises.

Answer:

b.compiler error arises.

We should note that all the iterator parameters in `copy()`

are of type `std::insert_iterator`

for insertion of elements in containers.`s.end()`

is of type `range::iterator`

indicating position, this generates a compiler error.