Different ways to convert vector to set in C++

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.