type 'set<int>' does not provide a subscript operator

Question

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        //use set. As in set, element appears only once.

        set<int> s;

        for(int i=0; i<nums.size(); i++) {
            s.insert(nums[i]);
        }

        nums.clear();

        for(int i=0; i<s.size(); i++) {

            nums.push_back(s[i]);
        }

        return s.size();
    }
};

https://leetcode.com/problems/remove-duplicates-from-sorted-array/solutions/

As you can see above is my solution code for a leetcode problem (I've also given it's link below). I don't seem to see a problem in my code but its giving me error. Please help.

Answer 1

The compiler is correct. A std::set does not have a subscript operator. In general, containers with an operator[] uses this to provide constant time lookups of elements. In an array, int arr[10], you can use arr[9] and get access to the 10:th element just as fast as to the first element, arr[0]. This is similar for std::unordered_map and std::map. You have a Key that you can use to lookup a Value in approximately the same time independently of which element you look for.

std::set is however not such a container. Accessing element 10 in a std::set would require that you iterate all the way to the 10:th element. Fortunately, you don't need the subscript operator. Just create the set using the iterators from the vector and then assign the result back to the vector:

class Solution {
public:
    std::size_t removeDuplicates(std::vector<int>& nums) {

        // create the set from the values in the vector:
        std::set<int> s(nums.begin(), nums.end());

        // assign the values in the set to the vector:
        nums.assign(s.begin(), s.end());

        return s.size();
    }
};

However, reading the actual task reveals something interesting:

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same.

The fact that it's already sorted makes it tempting to use std::unique and vector::erase to do this in-place instead of using a std::set:

#include <algorithm>

class Solution {
public:
    std::size_t removeDuplicates(std::vector<int>& nums) {
        auto new_end_it = std::unique(nums.begin(), nums.end());
        nums.erase(new_end_it, nums.end());
        return nums.size();
    }
};

Answer 2

std::set doesn't provide random access via operator[].

As alternatives to using std::vector::assign per Ted's answer, you can use a range-based for loop:

for(const auto i : s) {
   nums.push_back(i);
}    

or std::copy with std::back_inserter:

std::copy(s.cbegin(), s.cend(), std::back_inserter(nums));