Array search algorithms: performance comparison

Question

I'm making a program that compares multi-key sequential search and Interpolation search in a sorted array by the number of array accesses for my assignment.

/*
 * A program that compares Multi-key sequential search and Interpolation search in a sorted array by the number of array accesses.
 *
 * TODO:
 *  - make Exceptions with enum/map/static...?
 *  - enable sequence access count?
 *  - complete generate() and the required BTSort
 */

#include <iostream>
#include <fstream>
#include <string>

using namespace std;
/* Utility class. */
class Exception {
protected:
    short code;
    string text;
public:
    friend ostream& operator <<(ostream& out, const Exception& p_exception) {
        return out << p_exception.text;
    }
    void execute() {
        cerr << text;
        exit(code);
    };
};

class IndexOutOfBoundsException     : public Exception { public: IndexOutOfBoundsException()    { text = "\nERR:    An unsuccessful attempt was made to access the index outside the bounds of the array!"; code = 1; } };
class IndexOfEmptyFieldException    : public Exception { public: IndexOfEmptyFieldException()   { text = "\nERR:    An unsuccessful attempt was made to access the index of an empty field!"; code = 2; } };
class AllocationFailureException    : public Exception { public: AllocationFailureException()   { text = "\nERR:    An unsuccessful attempt was made to allocate dynamic memory!"; code = 3; } };
class OpenFileFailureException      : public Exception { public: OpenFileFailureException()     { text = "\nERR:    An unsuccessful attempt was made to open a file!"; code = 4; } };
class OpenedFileEmptyException      : public Exception { public: OpenedFileEmptyException()     { text = "\nERR:    An unsuccessful attempt was made to read from an empty file!"; code = 5; } };
class ArrayAlreadyExistsException   : public Exception { public: ArrayAlreadyExistsException()  { text = "\nERR:    An unsuccessful attempt was made to create an already existing array!"; code = 6; } };
class InvalidArgumentException      : public Exception { public: InvalidArgumentException()     { text = "\nERR:    An unsuccessful attempt was made to convert a string to an integer!"; code = 6; } };
class NumberTooLargeException       : public Exception { public: NumberTooLargeException()      { text = "\nERR:    An unsuccessful attempt was made to store an exceedingly large number!"; code = 7; } };
/* Main class. */
class SortedArray {
    int *array;
    int length, capacity;
public:
    SortedArray(int p_capacity) : capacity(p_capacity), length(0) {
        try {
            array = new int[p_capacity];
        }
        catch (bad_alloc) { AllocationFailureException exception; exception.execute();
        }
    }
    int getLength() {
        return length;
    }
    int getCapacity() {
        return capacity;
    }
    int getFrom(int i);
    void generate(); // Use BTSort() from dz1p2.cpp to generate a sorted array.
    void loadFromFile(string&);     // In both cases, input is assumed to be ordered, ascending integer array. If input isn't
    void loadFromInput(string&);    // ordered and ascending, it can be sorted with BTSort() used in SortedArray::generate();
    ~SortedArray() {
        if (array) delete array;
    }
};
/* Testing class. */
class TestRecord {
    int accesses;
    unsigned *locations;
    SortedArray array, sequence;
public:
    TestRecord(SortedArray p_array, SortedArray p_sequence) : accesses(0), array(p_array), sequence(p_sequence) {
        int length = sequence.getLength();
        try {
            locations = new unsigned[length];
        }
        catch (bad_alloc) {
            AllocationFailureException exception;
            exception.execute();
        }
        for (int i = 0; i < length; i++) {
            locations[i] = 0;
        }
    }
    int getAccesses() {
        return accesses;
    }
    void resetAccesses() {
        accesses = 0;
    }
    void accessed() {
        accesses++;
    }
    void MultiKeySequentialSearchTest();
    void InterpolationSearchTest();
    ~TestRecord() {
        if (locations) delete locations;
    }
};
/* Main program. */
void main() { // Loads the arrays, tests the search methods and outputs the results.
    //
    return;
}
/* Utility function. */
int readNumber(string& p_text, char& p_delimiter) { // References are used to enable side-effects.
    int integer;
    unsigned *position = new unsigned;
    try {
        integer = stoi(p_text, position);
    }
    catch (invalid_argument) {
        InvalidArgumentException exception;
        exception.execute();
    }
    catch (out_of_range) {
        NumberTooLargeException exception;
        exception.execute();
    }
    p_text.erase(0, ++(*position));                 // Side-effect.
    p_delimiter = p_text[0];                        // Side-effect.
    delete position;
    return integer;
}
/* Getter. */
int SortedArray::getFrom(int p_index) {
    int i = p_index;
    if (!(i < capacity)) {
        IndexOutOfBoundsException exception;
        exception.execute();
    }
    if (!(i < length)) {
        IndexOfEmptyFieldException exception;
        exception.execute();
    }
    return array[i];
}
/* Genereates ascending array of random unique integers. */
void SortedArray::generate() {
    //
}
/* Loads ascending array of random unique integers from a single-line .txt file. */
void SortedArray::loadFromFile(string& p_file_name) {
    string line;
    if (length) {
        ArrayAlreadyExistsException exception;
        exception.execute();
    }
    ifstream file;
    file.open(p_file_name);
    if (!file.is_open()) {
        OpenFileFailureException exception;
        exception.execute();
    }
    if (file.eof()) {
        OpenedFileEmptyException exception;
        exception.execute();
    }
    getline(file, line);
    loadFromInput(line);
    file.close();
}
/* Loads ascending array of random unique integers from single-line keyboard input. */
void SortedArray::loadFromInput(string& p_line) {
    char delimiter;
    int index = 0;
    unsigned last = 16;
    if (length) {
        ArrayAlreadyExistsException exception;
        exception.execute();
    }
    p_line += " #";
    do {
        int number = readNumber(p_line, delimiter);
        array[index++] = number;
        length++;
    } while (delimiter != '#' && length < capacity); // Excess input is ignored (should it be reported?).
}
/* Counts the number of array accesses in the Multi-key sequential search algorithm. */
void TestRecord::MultiKeySequentialSearchTest() {
    int i = 0, j = 0, n = array.getLength(), m = sequence.getLength();
    while (i < n && j < m) {
        while (i < n && sequence.getFrom(j) > array.getFrom(i)) {
            accessed(); // array
//          accessed(); // sequence
            i++;
        }
        if (sequence.getFrom(j) == array.getFrom(i)) {
            accessed(); // array
//          accessed(); // sequence
            locations[j] = i;
        }
        j++;
    }
}
/* Counts the number of array accesses in the  Interpolation binary search algorithm. */
void TestRecord::InterpolationSearchTest() {
    int low = 0, high = array.getLength(), sequence_length = sequence.getLength();
    for (int j = 0; j < sequence_length; j++) {
        int key = sequence.getFrom(j), mid;
//      accessed(); // sequence
        while (low < high) {
            int array_low = array.getFrom(low), array_high = array.getFrom(high), array_mid;
            accessed(); // array
            accessed(); // array
            accessed(); // array
            mid = low + (high - low) * (key - array_low) / (array_high - array_low);
            array_mid = array.getFrom(mid);
            if (key == array_mid)
                continue; // Acknowledge that the key is found.
            else if (key < array_mid)
                high = mid - 1;
            else
                low = mid + 1;
        }
        // Acknowledge that the key isn't found.
    }
}

I'm mostly concerned that Exception sub-classes aren't a good example of object-oriented design, as well as that my file/input readings aren't really safe.

Answer 1

Your program doesn't actually do anything, since main() has an empty body, but there are two major things worth pointing out here.

Exceptions are thrown

In C++, the way you use exceptions is to throw them. You have an out of range access?

throw std::out_of_range("invalid array access");

You have some generic runtime error? throw std::runtime_error("some useful message here"); Don't simply log an error and exit, that is very much non-idiomatic. The C++ standard library comes with a bunch of different exception types. If you want to add your own, that's fine, just inherit from std::exception or std::runtime_error or whatever is appropriate, but when the occasion calls for an exception, throw it!

One other thing worth pointing out. In getFrom(), you perform two different checks. One against capacity and one against length. The latter is a good check, but the former is unnecessary. If p_index is larger than length, it's an invalid operation, full stop, and capacity will always be at least as large as length. The code you want is:

int SortedArray::getFrom(int index) {
    if (index < length) {
        return array[index];
    }
    else {
        throw std::out_of_range("invalid index in getFrom()");
    }
}

Note the removal of the unnecessary local variable i (you already get passed in the index, why copy it?) and the simplified check against bounds.

Rule of Three/Five/Zero

This is a big one. Anytime you need to write a destructor, you should write the copy constructor and copy assignment operator. With C++11, add in the move constructor and move assignment operator. The problem is:

SortedArray my_array(10); // allocated a new array of size 10
{
    SortedArray another_array = my_array; // copied the array
                                          // both SortedArray's hold the 
                                          // SAME pointer

} // another_array goes out of scope, so it deletes its array
  // which is the same array that my_array held... so that

// <== here, when my_array goes out of scope, it will try to
// delete array again. double free, corruption, BOOM

You will want to make sure that you write the copy constructor to actually do a deep copy of array so that this doesn't happen. Alternatively, make the class noncopyable by either.

Even better, just use std::vector<int> internally and let the compiler do all the work for you.