For one of my assignments, we were asked to create a data structure similar to Bags using dynamic arrays where the order would be important - which I was able to do successfully, that is, the code that follows works fine. We now have to optimize the code according to the memory usage and timing.One of the functions that I know isn't optimized is my INSERT() function, I would appreciate any suggestion to help optimize this and any other function.Here are the files should you not want to copy and paste.sequence.h:#ifndef SEQUENCE_SEQUENCE_H#define SEQUENCE_SEQUENCE_H#include<iostream>namespace sqc { class sequence { public:    sequence(int newSize = DEFAULT_CAPACITY);    int find_empty();    void erase_first(int n);    void erase_last(int n);    void erase_occurence(int occur, int num);    void erase_from(int index);    void insert(int n);    void insert_at(int n, int in);    void insert_first(int n);    int count(int n);    int size();    friend sequence operator+(const sequence& ss, const sequence& s);    friend sequence operator+(const sequence& s, const int& n);    sequence& operator+=(const sequence& s);    sequence& operator+=(const int& n);    void operator=(const sequence& s);    bool operator==(const sequence& s);    friend std::ostream& operator <<(std::ostream& os, const sequence& s);    friend std::istream& operator >> (std::istream& is, sequence& s);   private:    static const int DEFAULT_CAPACITY = 5;    int seqSize;    int *data;    bool *used;};}#endifsequence.cpp:#include<iostream>#include sequence.husing namespace sqc;// C O N S T R U C T O Rsequence::sequence(int newSize) {    seqSize = newSize;    data = new int[newSize];    used = new bool[newSize];    for (int i = 0; i < newSize; i++) {        used[i] = false;    }}//FIND_EMPTY//Returns location of the last empty location//[NULL] [VALUE] [NULL] [NULL]//.................^...........//.................|...........Returns this locationint sequence::find_empty() {    int trueCount = 0;    for (int i = 0; i < seqSize-1; i++) {        if (used[i]==true){           trueCount++;           for (int j=i;j < seqSize-1; j++){                if (used[i] == false) {                    return i;                }                else {                    trueCount++;                }           }        if (trueCount == seqSize) return seqSize+1;        }    }}/*void resizeData() {    data = new int[seqSize + (seqSize / 2)];    int newSize = seqSize + (seqSize / 2);    seqSize = newSize;}*///ERASE_FIRST//Input Integer <Value>//Deletes the first occurence of the given valuevoid sequence::erase_first(int n) {    for (int i = 0; i < seqSize; ++i) {        if (n == data[i]) {            for (int j = i; j < seqSize; ++j) {                data[j] = data[j + 1];            }            int *newData = new int[seqSize - 1];            for (int k = 0; k < seqSize - 1; k++) {                newData[k] = data[k];            }            delete[] data;            data = newData;            seqSize = seqSize - 1;            break;        }    }}//ERASE_LAST//Input Integer <Value>//Deletes the last occurence of the given valuevoid sequence::erase_last(int n) {    for (int i = seqSize; i > 0; --i) {        if (n == data[i]) {            for (int j = i; j < seqSize; ++j) {                data[j] = data[j + 1];            }            int *newData = new int[seqSize - 1];            for (int k = 0; k < seqSize - 1; k++) {                newData[k] = data[k];            }            delete[] data;            data = newData;            seqSize = seqSize - 1;            break;        }    }}//ERASE_OCCURENCE//Input: Integer <Occurence>, Integer <Value>//Deletes the specified occurence of the given value from the arrayvoid sequence::erase_occurence(int occur, int num) {    int occurCount = 0;    for (int i = 0; i < seqSize; ++i) {        if (num = data[i]) {            occurCount++;        }        if (occurCount == occur) {            for (int j = i; j < seqSize; ++j) {                data[j] = data[j + 1];            }            int *newData = new int[seqSize - 1];            for (int k = 0; k < seqSize - 1; k++) {                newData[k] = data[k];            }            delete[] data;            data = newData;            seqSize = seqSize - 1;            break;        }    }}//ERASE_FROM//Input: Integer <Index>//Deletes value from given indexvoid sequence::erase_from(int index) {    for (int j = index; j < seqSize; ++j) {        data[j] = data[j + 1];    }    int *newData = new int[seqSize - 1];    for (int k = 0; k < seqSize - 1; k++) {        newData[k] = data[k];    }    delete[] data;    data = newData;    seqSize = seqSize - 1;}//INSERT//Input: Integer <Value>//Inserts the value to the end of the arrayvoid sequence::insert(int n) {    if (find_empty() > seqSize) {        int newSize = seqSize + (seqSize/2);        int *newData = new (std::nothrow) int[newSize];        for (int i = 0; i < seqSize-1; ++i) {            newData[i] = data[i];        }        newData[seqSize] = n;        delete[] data;        data = newData;        seqSize = newSize;        bool *newUsed = new bool[seqSize + (seqSize / 2)];        for (int i = 0; i < seqSize; ++i) {            newUsed[i] = used[i];        }        for (int j = 0; j < newSize - seqSize; ++j) {            newUsed[j] = false;        }        delete[] used;        used = newUsed;    }    else {        int index = find_empty();        data[index] = n;    }}//INSERT_AT//Input: Integer <Value>, Integer <Index>//Inserts value to the specified index, all following values are shiftedvoid sequence::insert_at(int n, int in) {    int *newData = new (std::nothrow) int[seqSize + 1];    int newSize = seqSize + 1;    for (int i = 0; i < in; ++i) {        if (in > seqSize + 1) {            std::cout << Invalid index, max index is size + 1.;            break;        }        newData[i] = data[i];    }    newData[in] = n;    for (int i = newSize; i > in + 1; --i) {        newData[i] = data[i - 1];    }    delete[] data;    data = newData;    seqSize = newSize;}//INSERT_FIRST//Input: Integer <Value>//Inserts value to the beginning of the array, all following values are shiftedvoid sequence::insert_first(int n) {    int *newData = new (std::nothrow) int[seqSize + 1];    int newSize = seqSize + 1;    for (int i = seqSize; i > 0; i--) {        newData[i + 1] = data[i];    }    newData[0] = n;    delete[] data;    data = newData;    seqSize = newSize;}//COUNT//Input: Integer <Value>//Returns the number of times the value occurs in the arrayint sequence::count(int n) {    int occur = 0;    for (int i = 0; i < seqSize; i++) {        if (data[i] == n) occur++;    }    return occur;}//SIZE//*NO INPUT*//Returns size of the arrayint sequence::size() {    return seqSize;}//[NON-MEMBER FUNCTION] <SEQUENCE> + <SEQUENCE>//Returns new sequence containing all values from both sequences and of the combined sizesequence sqc::operator+(const sequence& ss, const sequence& s) {    sequence toReturn;    int *newData = new (std::nothrow) int[s.seqSize + ss.seqSize];    int newSize = s.seqSize + ss.seqSize;    int index = 0;    for (index; index < ss.seqSize; ++index) {        newData[index] = ss.data[index];    }    for (int i = 0; i < s.seqSize; i++) {        newData[index + i] = s.data[i];    }    delete[] toReturn.data;    toReturn.data = newData;    toReturn.seqSize = newSize;    return toReturn;}//[NON-MEMBER FUNCTION] <SEQUENCE> + <INT>//Returns new sequence containing all values from the //sequence with the integer as the last value of the arraysequence sqc::operator+(const sequence& s,const int& n) {    sequence toReturn;    int *newData = new (std::nothrow) int[s.seqSize + 1];    int newSize = s.seqSize + 1;    for (int i = 0; i < s.seqSize; ++i) {        newData[i] = s.data[i];    }    newData[newSize - 1] = n;    delete[] toReturn.data;    toReturn.data = newData;    toReturn.seqSize = newSize;    return toReturn;}// <SEQUENCE> += <SEQUENCE>//Re-constructs the first sequence such that it contains all values from both sequences and of the combined size sequence& sequence::operator+=(const sequence& s) {    int *newData = new (std::nothrow) int[s.seqSize + seqSize];    int newSize = s.seqSize + seqSize;    int index = 0;    for (index; index < seqSize; ++index) {        newData[index] = data[index];    }    for (int i = 0; i < s.seqSize; i++) {        newData[index + i] = s.data[i];    }    delete[] data;    data = newData;    seqSize = newSize;    return *this;}// <SEQUENCE> += <INT>// Re-constructs the first sequence such that it contains the integer as its last valuesequence& sequence::operator+=(const int& n) {    int *newData = new (std::nothrow) int[seqSize + 1];    int newSize = seqSize + 1;    for (int i = 0; i < seqSize; ++i) {        newData[i] = data[i];    }    newData[newSize - 1] = n;    delete[] data;    data = newData;    seqSize = newSize;    return *this;}// <SEQUENCE> = <SEQUENCE>// Sets the left hand side sequence's attributes to be equal to that of the right hand side sequencevoid sequence::operator=(const sequence& s) {    delete[] data;    data = s.data;    seqSize = s.seqSize;}// <SEQUENCE> == <SEQUENCE>// Returns true if the size and ALL elements of the two sequences are identical// Else, returns falsebool sequence::operator==(const sequence& s) {    if (seqSize == s.seqSize) {        int trueCount = 0;        for (int i = 0; i < seqSize; i++) {            if (data[i] == s.data[i]) {                trueCount++;            }        }        if (trueCount == seqSize) {            return true;        }        else {            return false;        }    }}//OSTREAM OPERATOR : USED TO PRINT ALL VALUES CONTAINED IN A SEQUENCEstd::ostream& sqc::operator <<(std::ostream& os, const sequence& s) {    for (int i = 0; i < s.seqSize; i++) {        os << s.data[i] << \t;    }    return os;}//ISTREAM OPERATOR : USED TO ASSIGN VALUES TO A SEQUENCE IN BULKstd::istream& sqc::operator >> (std::istream& is, sequence& s) {    for (int i = 0; i < s.seqSize; i++) {        is >> s.data[i];        s.used[i] = true;    }    return is;}main.cpp:#include <iostream>#include sequence.husing namespace sqc;int main() {sequence s1(2);std::cout << s1 << std::endl;s1.erase_from(0);std::cout << s1 << std::endl;s1.insert_at(2, 1);std::cout << s1 << std::endl;s1.insert(3);std::cout << s1 << std::endl;s1.insert_first(1);std::cout << s1 << std::endl;sequence s2(2);std::cout << s2 << std::endl;std::cout << s1 + s2 << std::endl;std::cout << s1 + 9 << std::endl;s1 += s2;std::cout << s1 << std::endl;s1 = s2;std::cout << s1 << std::endl;if (s1 == s2) {    std::cout << s1 == s2 << std::endl;}else {    std::cout << not equal << std::endl;}std::cin >> s1;std::cout << s1 << std::endl;return 0;}
Dynamic Array Bags
c++;performance;memory management
I think you find_empty routine is buggy. Also it will always return the first empty location after the first nonempty one. As an example look at [Null] [Value] [Null] [Value] [Null], which is not the last empty location. Also from the name find empty I would expect it to return the first empty slot it finds. So if you really want the first empty spot behind the first nonempty you have to traverse from the back. Also you are inconsistent in your return value. If you found an unused value, you return i, but if you did not found one then you return seqSize+1, which is off by one//FIND_EMPTY//Returns location of the last empty location//[NULL] [VALUE] [NULL] [NULL]//.................^...........//.................|...........Returns this locationint sequence::find_empty() {    int trueCount = 0;    // Bail early if the last element is used    if (used[seqSize-1]) {        return seqSize;    }    for (int i = seqSize-2; i >= 0; --i) {        if (used[i]==true) {           return i+1;        }    }    return 0;}Try to reuse your work. For example insert_first(value) should be equal to insert_at(0, value)//INSERT_FIRST//Input: Integer <Value>//Inserts value to the beginning of the array, all following values are shiftedvoid sequence::insert_first(int value) {    insert_at(0, value);}What is the actual purpose of bool used? Generally i would expect that it tells me whether the data at position used[i] is valid. So a function like erase_from() should simply set the boolean to false and not tamper with the data. Also your code contains an invalid memory access herefor (int j = index; j < seqSize; ++j) {        data[j] = data[j + 1];}As this will access data[seqSize] which is not valid. A similar error is in erase_last()for (int i = seqSize; i > 0; --i) {        if (n == data[i]) {You access data out off bounds. In any case if you want to improve  your code you should have a look at http://www.cplusplus.com/reference/cstdlib/realloc/ . This should considerably simplify your code. What actually worst about all your erase function is that they do not modify the used data completely invalidating your logicAs you need this all the time so you should utilize erase_from for this//ERASE_FROM//Input: Integer <Index>//Deletes value from given indexvoid sequence::erase_from(int index) {    for (int j = index; j < seqSize-1; ++j) {        data[j] = data[j + 1];        used[j] = used[j + 1];    }    seqSize--;    data = (int*)  realloc (data, seqSize * sizeof(int));    used = (bool*) realloc (used, seqSize * sizeof(bool));}//ERASE_FIRST//Input Integer <Value>//Deletes the first occurence of the given valuevoid sequence::erase_first(int value) {    for (int i = 0; i < seqSize; ++i) {        if (value == data[i]) {            erase_from(i);            break;        }    }}//ERASE_LAST//Input Integer <Value>//Deletes the last occurence of the given valuevoid sequence::erase_last(int value) {    for (int i = seqSize-1; i >= 0; --i) {        if (value == data[i]) {            erase_from(i);            break;         }    }}//ERASE_OCCURENCE//Input: Integer <Occurence>, Integer <Value>//Deletes the specified occurence of the given value from the arrayvoid sequence::erase_occurence(int occur, int value) {    int occurCount = 0;    for (int i = 0; i < seqSize; ++i) {        if (value = data[i]) {            occurCount++;        }        if (occurCount == occur) {            erase_from(i);            break;         }    }}Also generally you should really check whether the memory allocation succeeded. Have a look here http://www.cplusplus.com/reference/new/bad_alloc/Your insert function is bogus too. When reassigning the used values, you overwrite the old ones here for (int j = 0; j < newSize - seqSize; ++j). This should start at seqSize+1. Similarly your insert function can benefit from realloc//INSERT//Input: Integer <Value>//Inserts the value to the end of the arrayvoid sequence::insert(int value) {    if (find_empty() >= seqSize) {        int oldSize = seqSize;        seqSize += seqSize/2;        data = (int*)  realloc (data, seqSize * sizeof(int));        used = (bool*) realloc (used, seqSize * sizeof(bool));        data[oldSize] = value;        used[oldSize] = true;        for (int j = oldSize+1; j < seqSize; ++j) {            used[j] = false;        }    }    else {        data[find_empty()] = value;    }}//INSERT_AT//Input: Integer <Value>, Integer <Index>//Inserts value to the specified index, all following values are shiftedvoid sequence::insert_at(int value, int index) {    if (index >= seqSize) {        std::cout << Invalid index, max index is seqSize:  << seqSize << \n;    }    seqSize++;    data = (int*)  realloc (data, seqSize * sizeof(int));    used = (bool*) realloc (used, seqSize * sizeof(bool));    for (int i = index + 1; i < seqSize; ++i) {        data[i] = data[i-1];        used[i] = used[i-1];    }    data[index] = value;    used[index] = true; }