std::sort() not working on vector of pairs

Question

I have the following code snippet:

struct compare {
    bool operator()(const pair<size_t, double>& left, const pair<size_t, double>& right) {
               return left.second > right.second;
    }
};

int main() {
   size_t vertices = 31112738;
   vector<pair<size_t, double> > opt, one;
   opt.reserve(vertices);
   one.reserve(vertices);

   for(size_t i=0;i<vertices;i++) {
      opt[i] = make_pair(i,rand());
      one[i] = make_pair(i,rand()); 
   }

   sort(opt.begin(), opt.end(), compare());
   sort(one.begin(), one.end(), compare());

  return 0;


}

Even after calling the sort function, opt[] and one[] aren't sorted. If however I use push_back() to insert the elements and then call the sort() function, they get sorted.

Why is the outcome different in the two scenarios?

Answer 1

Because in the scenario you outlined, the vectors always have size 0.

You reserve more space in the vectors, but you never resize them. (So your for-loop just triggers undefined behavior by writing past the end of the vectors)

push_back grows the vector's size by 1, but if you don't call that, then you must call resize and set the size explicitly. (or specify the size as a constructor argument)