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;
};
}
#endif
sequence.cpp:
#include<iostream>
#include "sequence.h"
using namespace sqc;
// C O N S T R U C T O R
sequence::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 location
int 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 value
void 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 value
void 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 array
void 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 index
void 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 array
void 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 shifted
void 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 shifted
void 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 array
int 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 array
int sequence::size() {
return seqSize;
}
//[NON-MEMBER FUNCTION] <SEQUENCE> + <SEQUENCE>
//Returns new sequence containing all values from both sequences and of the combined size
sequence 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 array
sequence 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 value
sequence& 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 sequence
void 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 false
bool 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 SEQUENCE
std::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 BULK
std::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.h"
using 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;
}
std::vector
banned for some reason? If so, it would be a good example to strive for. \$\endgroup\$