The reference operator [] on STL set

Question

I am just getting familiar with the STL and I can't quite understand why the operator [] gives an error.

        int main(){
          set< int > s;
          for(int i=0; i<=1000; i++) s.insert((i*1777)%123);
          for(int i=0; i<s.size(); i++) cout<<s[i]<<endl;
        }

Then I tried this and got another error message

        int main(){
          set< int > s;
          for(int i=0; i<=1000; i++) s.insert((i*1777)%123);
          for(int i=0; i<s.size(); i++) cout<<*(s.begin() + i)<<endl;
        }

I understand why it doesn't have members like push_back, pop_back and all but I don't understand why these two methods of referencing don't work (but they do for vector and string). I understand that these operators weren't overloaded in the library, but why?

After some web searches I did figure out how to reference it

        int main(){
          set< int > s;
          for(int i=0; i<=1000; i++) s.insert((i*1777)%123);
          for(set< int >::iterator i=s.begin(); i!=s.end(); i++) cout<<*i<<endl;
        }

Answer 1

The standard does not specify those operators for a set or its iterators, because those are not efficient ways to access a set. A set has bidirectional iterators. This means that in order to move to the nth element in the iteration sequence, you need to iterate over every element in between. So, for example, if operator+ were to be implemented for a set's iterators, internally, it would be something like this:

iterator operator+(iterator it, size_t n)
{
    for (int i=0; i<n; ++i)
        ++it;
    return it;
}

So, in other words, it would be an O(n) operation. If you were to iterate over the set like you are doing in your for loop, it becomes an O(n^2) for loop. The same thing applies if operator[] was implemented. Because of this, no one with efficiency in mind would want to use these operators, and so they are not implemented.