std::sort Doesn't work for User-Defined Object with oveloaded < operator

Question

I am writing a class to test the efficient of different sorting algorithms (for a college course), and of the algorithms I'm supposed to test is the STL sort. To measure efficiency, we've defined a class Integer that holds and integer value, and also allows us to increment a global variable each time it is compared or assigned. I then have a driver class which tests the std::sort call on multiple vectors of integers. I have overloaded the '<' operator in my Integer class, and it conforms to strict weak ordering (at least I'm pretty sure it does). Every time I call sort, however, I get a segmentation fault. I really can't figure out why this is happening, any help would be greatly appreciated. Thanks!

Integer.cpp

#include "Integer.h"

int Integer_count;

//Default Constructor
Integer::Integer() {
    val = 0;
}

//Specified Constructor
Integer::Integer(int x) {
    val = x;
}

//Copy-Constructor
Integer::Integer(const Integer &cp) {
    Integer_count++;
    val = cp.val;
}

//Return the Integer's value
int Integer::value() {
    return val;
}

//Less-than (<) operator overload
bool Integer::operator < (const Integer& obj) const {
    Integer_count++;
    return (val < obj.val);
}

//Assignment (=) operator overload
void Integer::operator = (const Integer& obj) {
    Integer_count++;
    val=obj.val;
}

driver.cpp

#include <iostream>
#include <cstdlib>
#include <vector>
#include "Integer.h"
#include "Sorter.cpp"    
srand (time(NULL)); //Seed the random number generator

    std::vector<Integer> one;
    std::vector<Integer> two;
    std::vector<Integer> three;
    std::vector<Integer> four;
    std::vector<Integer> five;


    for(int i=0; i<10000; i++){
        one[i] = Integer(i);
        two[i] = Integer(10000-i);
        three[i] = Integer(rand() % (10000+1));
        four[i] = Integer(rand() % (10000+1));
        five[i] = Integer(rand() % (10000+1));
    }


    //Sort function called from the STL
    //Sorted Array
    std::sort(one.begin(), one.end());
    std::cout << "STL for Sorted Array: " << Integer_count << std::endl;

Basically, I think the std::sort function is not using the overloaded operator from my Integer class, which is messing up the stack. I don't know for certain is this is the error however, and can't seem to resolve it.

Answer 1

std::vector::operator[] never inserts a new element into the container and no bounds checking is performed (vector/operator_at). If you access an element that is out of bounds leads to undefined behaviour which is your case.

You must use std::vector::emplace_back or std::vector::push_back, other option is to use the constructor explicit vector<T>(size_type count); that constructs the container with count default-inserted instances of T:

First option:

std::vector<Integer> one;
one.reserve(10000);
std::vector<Integer> two;
two.reserve(10000);
std::vector<Integer> three;
three.reserve(10000);
std::vector<Integer> four;
four.reserve(10000);
std::vector<Integer> five;
five.reserve(10000);

for (int i = 0; i < 10000; ++i) {
    one.emplace_back(i);
    two.emplace_back(10000 - i);
    three.emplace_back(rand() % (10000+1));
    four.emplace_back(rand() % (10000+1));
    five.emplace_back(rand() % (10000+1));
}

Second option:

std::vector<Integer> one(10000);
std::vector<Integer> two(10000);
std::vector<Integer> three(10000);
std::vector<Integer> four(10000);
std::vector<Integer> five(10000);

for (int i = 0; i < 10000; ++i) {
    one[i] = Integer(i);
    two[i] = Integer(10000-i);
    three[i] = Integer(rand() % (10000+1));
    four[i] = Integer(rand() % (10000+1));
    five[i] = Integer(rand() % (10000+1));
}

And std::sort(one.begin(), one.end()) must work.

Answer 2

Your values for your vector[i] are not allocated. Hence, accessing vector values (e.g one[999999]) that are out of bounds leads to undefined behaviour.

Use push_back() for your std:::vector to allocate and assign the values to your vectors:

for(int i=0; i<10000; i++){
    one.push_back(Integer(i));
    two.push_back(Integer(10000-i));
    three.push_back(Integer(rand() % (10000+1)));
    four.push_back(Integer(rand() % (10000+1)));
    five.push_back(Integer(rand() % (10000+1)));
}

That will solve the segmentatio fault. As for sorting, once you have values.

std::sort(one.begin(), one.end()) sorts by default using operator< so leave it as it is.

Answer 3

You didn't push/append elements in vector. Without allocating space or pushing back, you can't add element in vector this way (My clang compiler would yield runtime error due to bad allocation/array out of bound). Use push_back instead.

To quick test -

std::vector<Integer> arr{Integer(1), Integer(4), Integer(3)};
sort(arr.begin(), arr.end());

// now print Integer_count