stack overflow exception in std::list and std::vector

Question

I am making a test program to check the time for storage of std::list, std::vector, and array. I want to store 2 million random integers in each container. However, std::list and std::vector makes stack overflow exception when about 1550 integers is stored. How can I avoid it except decreasing the number of integers?

#include <list>
#include <vector>
#include <iostream>
#include <iomanip>
#include <string>
#include <ctime>
#include <cstdlib>
using namespace std;

void insert(list<short>& l, const short& value);
void _insert(list<short>& l, list<short>::iterator it, const short& value);
void insert(vector<short>& v, const short& value);
void _insert(vector<short>& v, vector<short>::iterator it, const short& value);
void insert(short arr[], int& logicalSize, const int& physicalSize, const short& value);
void _insert(short arr[], int& logicalSize, const int& physicalSize, const short& value, int& cur);

int main() {
    clock_t start, end;
    srand(time(nullptr));

    const int SIZE = 2000000;
    const short RANGE = 10000;
    list<short> l;
    vector<short> v;
    short* arr = new short[SIZE];
    int logicalSize = 0;

    // list
    cout << "List storage time test...";
    start = clock();
    for (int i = 0; i < SIZE; i++) {
        insert(l, (short)(rand() % (2 * RANGE + 1) - RANGE));
    }
    end = clock();
    cout << "Time: " << difftime(end, start) << endl << endl;

    // vector
    cout << "Vector storage time test...";
    start = clock();
    for (int i = 0; i < SIZE; i++) {
        insert(v, (short)(rand() % (2 * RANGE + 1) - RANGE));
    }
    end = clock();
    cout << "Time: " << difftime(end, start) << endl << endl;

    // array
    start = clock();
    cout << "Array storage time test...";
    for (int i = 0; i < SIZE; i++) {
        try {
            insert(arr, logicalSize, SIZE, (short)(rand() % (2 * RANGE + 1) - RANGE));
        }
        catch (string s) {
            cout << s << endl;
            system("pause");
            exit(-1);
        }
    }
    end = clock();
    cout << "Time: " << difftime(end, start) << endl << endl;

    delete[] arr;
    system("pause");
    return 0;
}

void insert(list<short>& l, const short& value) {
    _insert(l, l.begin(), value);
}

void _insert(list<short>& l, list<short>::iterator it, const short& value) {
    if (it == l.end() || value < *it) {
        l.insert(it, value);
        return;
    }
    else {
        it++;
        return _insert(l, it, value);
    }
}

void insert(vector<short>& v, const short& value) {
    _insert(v, v.begin(), value);
}

void _insert(vector<short>& v, vector<short>::iterator it, const short& value) {
    if (it == v.end()) {
        v.push_back(value);
        return;
    } else if (value < *it) {
        v.insert(it, value);
        return;
    } else {
        it++;
        return _insert(v, it, value);
    }
}

void insert(short arr[], int& logicalSize, const int& physicalSize, const short& value) {
    int cur = 0;
    _insert(arr, logicalSize, physicalSize, value, cur);
}

void _insert(short arr[], int& logicalSize, const int& physicalSize, const short& value, int& cur) {
    if (cur >= physicalSize) throw string("No space for array.");

    if (cur == logicalSize) {
        arr[cur] = value;
        logicalSize++;
        return;
    } else if (value < arr[cur]) {
        for (int i = logicalSize - 1; i >= cur; i--) {
            arr[i + 1] = arr[i];
        }
        arr[cur] = value;
        logicalSize++;
        return;
    } else {
        return _insert(arr, logicalSize, physicalSize, value, ++cur);
    }
}

Why are you writing everything recursively? This isn't Scheme; you don't have tail call elimination. — user2357112, Mar 29 '17 at 22:25
Don't use recursion if you don't need to. You can do all this with loops. — Richard Critten, Mar 29 '17 at 22:26
Worth a read through [What are the rules about using an underscore in a C++ identifier?](http://stackoverflow.com/questions/228783/what-are-the-rules-about-using-an-underscore-in-a-c-identifier). Your `_insert` functions are in danger of colliding with an Standard Library implementation detail. — user4581301, Mar 29 '17 at 22:27
And also, if you want an ordered vector just insert everything and then sort it once. That will be a lot faster. — Bo Persson, Mar 29 '17 at 23:14

score 0 · Answer 1 · answered Mar 29 '17 at 22:32

However, std::list and std::vector makes stack overflow exception when about 1550 integers is stored

Just write it iteratively

void insert(list<short>& l, const short& value) {
    list<short>::iterator it = l.begin();
    for (;it != l.end() && value < *it;it++);
    l.insert(it, value);
}

You can use the same idea for vector... You can even reuse the function:

void insert(list<short>& l, const short& value) {
    list<short>::iterator it = getIterator(l.begin(),l.end(),value);
    l.insert(it, value);
}

void insert(vector<short>& v, const short& value) {
    vector<short>::iterator it = getIterator(l.begin(),l.end(),value);
    v.insert(it, value);
}

template<class InputIterator>
void getIterator(InputIterator it,InputIterator end){
    while (it != end && value < *it) {
        it++;
    }
    return it;
}

stack overflow exception in std::list and std::vector

1 Answers1