C++

Forum

 
 
Ordered List & Templates

NickLSSU (6)
I have an assignment to create an ordered list using templates so that it will accept all data types. I believe I have the template part of the program correct, but for some reason I can't get my list to come out in order. Here's my code so far: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
 
#include <fstream>
#include <iostream>
#include <iomanip>
#include <cstdlib>

using namespace std;

template <class item>
class OrderedList
{
public:
  OrderedList();
  OrderedList(const OrderedList &);
  ~OrderedList();

  int size(); 
  void clear();
  void add(const item newItem);
  void remove(const int location);

  item& operator[] (int);

private:
  int currSize, maxSize;
  item* data;
};


template <class item>
OrderedList<item>::OrderedList()
{
  currSize = 0;
  maxSize = 10;

}

template <class item>
OrderedList<item>::OrderedList(const OrderedList &a)
{
  currSize = a.currSize;
  maxSize = a.maxSize;

  if (currSize > 0)
    for(int k = 0; k < currSize; k++)
      data[k] = a.data[k];
  else
    data = NULL;

}


template <class item>
OrderedList<item>::~OrderedList()
{
  currSize = maxSize = 0;
  if (data != NULL)
    delete []data;
  data = NULL;

}

template <class item>
int OrderedList<item>::size()
{
  return currSize;
}

template <class item>
void OrderedList<item>::clear()
{
  currSize = maxSize = 0;
  if (data != NULL)
    delete []data;
  data = NULL;
}


template <class item>
void OrderedList<item>::add(const item newItem)
{

  if(currSize >= maxSize)
    maxSize +=5;

  for(int k = 0; k < currSize; k++)
    {
      if(newItem < data[k])
	{
	  for(int j = currSize; j >= k; j--)
	    data[j+1] = data[j];
	  data[k] = newItem;
	  currSize++;
	  return;
	}
    }

}


template <class item>
void OrderedList<item>::remove(const int location)
{
  data[location] = NULL;
  for(int k = location; k < currSize; k++)
    data[k] = data[k+1];
  currSize--;
  return;


}

template <class item>
item& OrderedList<item>::operator[] (int a)
{
  return data[a];
}



//From here on out is a main function my instructor provided us, only the above code is mine





struct testStruct
{
  int iValue;
  double dValue;
  bool operator< (testStruct x) {return iValue <  x.iValue; }
  bool operator<=(testStruct x) {return iValue <= x.iValue; }
  bool operator==(testStruct x) {return iValue == x.iValue; }
  bool operator>=(testStruct x) {return iValue >= x.iValue; }
  bool operator> (testStruct x) {return iValue >  x.iValue; }
  bool operator!=(testStruct x) {return iValue != x.iValue; }
};

int main()
{
  ofstream out ("Project6.txt");

  // Start off easily with an ordered list of integers

  OrderedList<int> intList;
  int value;

  for (int k = 0; k < 25; k++)
  {
    value = rand() % 1000;
    out << setw(5) << value;
    if ((k+1) % 5 == 0) out << endl;
    intList.add(value);
  }
  out << endl << endl;
  for (int k = 0; k < intList.size(); k++)
  {
    value = intList[k];
    out << setw(5) << value;
    if ((k+1) % 5 == 0) out << endl;
  }
  out << endl << endl;

  // Now work with an ordered list of doubles

  OrderedList<double> doubleList;
  double dValue;
  out << fixed << showpoint << setprecision(2);
  for (int k = 0; k < 25; k++)
  {
    dValue = rand() % 1000 + (0.01 * (rand() % 100));
    out << setw(8) << dValue;
    if ((k+1) % 5 == 0) out << endl;
    doubleList.add(dValue);
  }
  out << endl << endl;
  for (int k = 0; k < doubleList.size(); k++)
  {
    dValue = doubleList[k];
    out << setw(8) << dValue;
    if ((k+1) % 5 == 0) out << endl;
  }
  out << endl << endl;

  // Now get fancy and create an ordered list of structures!
  
  /*  OrderedList <testStruct> structList;
  testStruct sValue;
  for (int k = 0; k < 25; k++)
  {
    sValue.iValue = rand() % 1000;
    sValue.dValue = rand() % 1000 +  (0.01 * (rand() % 100));
    out << setw(5) << sValue.iValue << "  " << setw(8) << sValue.dValue;
    if ((k+1) % 2 == 0) out << endl;
    structList.add(sValue);
  }
  out << endl << endl;
  for (int k = 0; k < structList.size(); k++)
  {
    sValue = structList[k];
    out << setw(5) << sValue.iValue << "  " << setw(8) << sValue.dValue;
    if ((k+1) % 2 == 0) out << endl;
  }
  */
  out << endl;
  
  return 0;
}


My result "Project6.txt" prints out:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
   41  467  334  500  169
  724  478  358  962  464
  705  145  281  827  961
  491  995  942  827  436
  391  604  902  153  292




  382.21  716.18  895.47  726.71  538.69
  912.67  299.35  894.03  811.22  333.73
  664.41  711.53  868.47  644.62  757.37
  859.23  741.29  778.16   35.90  842.88
  106.40  942.64  648.46  805.90  729.70


As you can tell, it's not very ordered... Can anyone point out any mistakes I may have made?

Thank you in advance,

Nick
Last edited on
closed account (D80DSL3A)
I think that your OrderedList isn't functioning at all.
The output going to the file comes from lines 150 and 171 where you are writing the values directly after generating them.

You haven't allocated memory space for the data array anywhere. You would be getting lots of segmentation faults, but luckily currSize remains always = 0 so your add() and some of the for loops in main() do nothing (because orderedlist.size() returns 0).

Start fixing this by allocating an array to data in the OrderedList constructor.
Rewrite the add(). There are several logical errors present.
Last edited on
NickLSSU (6)
Thank you for the advice, me being relatively air-headed I managed to overlook several easy things I should have realized. My code is now this:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
 

#include <fstream>
#include <iostream>
#include <iomanip>
#include <cstdlib>

using namespace std;

template <class item>
class OrderedList
{
public:
  OrderedList();
  OrderedList(const OrderedList &);
  ~OrderedList();

  int size(); 
  void clear();
  void add(const item newItem);
  void remove(const int location);

  item& operator[] (int);

private:
  int currSize, maxSize;
  item* data;
};


template <class item>
OrderedList<item>::OrderedList()
{
  currSize = 0;
  maxSize = 10;
  data = new item[maxSize];


}

template <class item>
OrderedList<item>::OrderedList(const OrderedList &a)
{
  currSize = a.currSize;
  maxSize = a.maxSize;

  if (currSize > 0)
    for(int k = 0; k < currSize; k++)
      data[k] = a.data[k];
  else
    data = NULL;

}


template <class item>
OrderedList<item>::~OrderedList()
{
  currSize = maxSize = 0;
  if (data != NULL)
    delete []data;
  data = NULL;

}

template <class item>
int OrderedList<item>::size()
{
  return currSize;
}

template <class item>
void OrderedList<item>::clear()
{
  currSize = maxSize = 0;
  if (data != NULL)
    delete []data;
  data = NULL;
}


template <class item>
void OrderedList<item>::add(const item newItem)
{

  bool notFound = false;
  if(currSize >= maxSize)
    maxSize +=5;

  if(currSize == 0)
    {
    data[0] = newItem;
    currSize = 1;
    return;
    }
  

  for(int k = 0; k < currSize; k++)
    {
      if(newItem < data[k])
	{
	  for(int j = currSize; j >= k; j--)
	    data[j+1] = data[j];
	  data[k] = newItem;
	  currSize++;
	  return;
	}
      notFound = true;
    }

  if(notFound)
    {
      data[currSize] = newItem;
      currSize++;
      return;
    }



}


template <class item>
void OrderedList<item>::remove(const int location)
{
  data[location] = NULL;
  for(int k = location; k < currSize; k++)
    data[k] = data[k+1];
  currSize--;
  return;


}

template <class item>
item& OrderedList<item>::operator[] (int a)
{
  return data[a];
}




struct testStruct
{
  int iValue;
  double dValue;
  bool operator< (testStruct x) {return iValue <  x.iValue; }
  bool operator<=(testStruct x) {return iValue <= x.iValue; }
  bool operator==(testStruct x) {return iValue == x.iValue; }
  bool operator>=(testStruct x) {return iValue >= x.iValue; }
  bool operator> (testStruct x) {return iValue >  x.iValue; }
  bool operator!=(testStruct x) {return iValue != x.iValue; }
};

int main()
{
  ofstream out ("Project6.txt");

  // Start off easily with an ordered list of integers

  OrderedList<int> intList;
  int value;

  for (int k = 0; k < 25; k++)
  {
    value = rand() % 1000;
    out << setw(5) << value;
    if ((k+1) % 5 == 0) out << endl;
    intList.add(value);
  }
  out << endl << endl;
  for (int k = 0; k < intList.size(); k++)
  {
    value = intList[k];
    out << setw(5) << value;
    if ((k+1) % 5 == 0) out << endl;
  }
  out << endl << endl;

  // Now work with an ordered list of doubles
  
  OrderedList<double> doubleList;
  double dValue;
  out << fixed << showpoint << setprecision(2);
  for (int k = 0; k < 25; k++)
  {
    dValue = rand() % 1000 + (0.01 * (rand() % 100));
    out << setw(8) << dValue;
    if ((k+1) % 5 == 0) out << endl;
    doubleList.add(dValue);
  }
  out << endl << endl;
  for (int k = 0; k < doubleList.size(); k++)
  {
    dValue = doubleList[k];
    out << setw(8) << dValue;
    if ((k+1) % 5 == 0) out << endl;
  }
  out << endl << endl;

  // Now get fancy and create an ordered list of structures!
  /*
    OrderedList <testStruct> structList;
  testStruct sValue;
  for (int k = 0; k < 25; k++)
  {
    sValue.iValue = rand() % 1000;
    sValue.dValue = rand() % 1000 +  (0.01 * (rand() % 100));
    out << setw(5) << sValue.iValue << "  " << setw(8) << sValue.dValue;
    if ((k+1) % 2 == 0) out << endl;
    structList.add(sValue);
  }
  out << endl << endl;
  for (int k = 0; k < structList.size(); k++)
  {
    sValue = structList[k];
    out << setw(5) << sValue.iValue << "  " << setw(8) << sValue.dValue;
    if ((k+1) % 2 == 0) out << endl;
  }
  
  out << endl;
  */
  return 0;
}


When I run the program, windows tells me it needs to be closed and when I check my output text, I see this:

1
2
3
4
5
6
7
8
9
10
11
12
13
 

   41  467  334  500  169
  724  478  358  962  464
  705  145  281  827  961
  491  995  942  827  436
  391  604  902  153  292


   41  145  153  169  281
  292  334  358  391  436
  464  467  478  491  500
  604  705  724  827  827
  902  942  961  962  995


So now my list can keep stuff in order but it just chokes all-together before I get to doubles? Any tips?

Thanks in advance again
closed account (D80DSL3A)
You are exceeding the array bounds in the add() for 2 reasons.

1) Increasing the value of maxSize doesn't increase the # of elements allocated to data:
1
2
 
if(currSize >= maxSize)
    maxSize +=5;

You need to allocate a new larger array to a temp*, copy the values from the existing array to the new one, delete the old array then assign data to point to the new array.

2)More subtle here... currSize = the # of elements in use = 1 more than the max valid array index.
In the for loop on lines 101, 102
1
2
 
for(int j = currSize; j >= k; j--)
	data[j+1] = data[j];

you are referencing data[currSize+1] in the 1st iteration. Keep in mind that if maxSize = 10 then currSize can be as high as 9. Try for(int j = currSize-1; j >= k; j--).
I see a similar issue in your remove().

You need to allocate an array in the copy constructor like you did in the default constructor.
This is all I can see that's wrong with the code. Good luck!
Last edited on
NickLSSU (6)
Alright I finally got it working. Thank you very much for all of your help and pointing out where I could fix it without just telling me what to type. Hopefully I learned something this way ha ha.

Thanks again!
Topic archived. No new replies allowed.