Beginner C++: Templates & Ordered List question

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:

Code:

---

#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];
}




// After this is all code our instructor provided to test the program






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:

Code:

---

  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

First: You never allocated memory for item *data.

Also, here:

Code:

---

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;
        }
    }


}

---

You're awfully close.
But notice the part I underlined (and the if statement surrounding that bit of code). What happens when newItem is bigger than everything in the list? What happens with you insert into an empty list?

Ah, that would be two events I should probably handle eh?

Not to be a bother, but I edited my code and tried to handle the cases I had forgotten originally like this:

Code:

---

#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;
}

---

and now my program outputs:

Code:

---

  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

---

It looks like it handles integers fine but not doubles? any further advice?

Thank you in advance, again

Code:

---

maxSize = 10;
data = new item[maxSize];

---

The array you allocate here simply isn't big enough to hold 25 values. You end up writing to chunks of memory outside of what you allocated and weird things will happen.

Now, I see what you're trying to do in the add(item) function, where you increase maxSize as needed, but that doesn't change the actual size of the array, just what the class "thinks" the size of the array is. (Arrays in C can't be resized in-place anyway; you'll have to allocate a new, larger chunk of memory and copy the contents of the old array over.)

Can't use std::vector?

Can't use std::vector because we haven't learned about it yet.

I changed my code to be able to make my array longer when needed:

Code:

---

#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;
  data = new item[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 += 10;
    item* temp = new item [maxSize];


    for(int k = 0; k < currSize; k++)
              temp[k] = data[k];
    delete []data;
    data = temp;


    }
  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;
}

---

and now my result is:

Code:

---

  41  467  334  500  169
  724  478  358  962  464

---

?

Code:

---

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

---

Oh, so if MaxSize == 0, you are going to allocate an array of 0 elements and then toss that away by setting data to NULL? Sounds like a good idea to get memory leaks, if you ask me.

Code:

---

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;
}

---

Since data[location] is not a pointer, setting it to NULL is wrong. Besides, you're overwriting it anyway, so why bother?

Also, deleting a null ptr is perfectly defined, so you don't need to check if data != NULL.
And finally, you need to improve your indentation and stop duplicating so much code. You have several "clean up" snippets all over the place. Organize!

Quote:

---

Originally Posted by Elysia

Oh, so if MaxSize == 0, you are going to allocate an array of 0 elements and then toss that away by setting data to NULL? Sounds like a good idea to get memory leaks, if you ask me.

---

If maxSize is really zero, then you definitely don't need to allocate, but why would maxSize be zero? It should be impossible, since the default constructor doesn't assign maxSize the value of zero.

And what would you leak an array with no elements?

Quote:

---

5.3.4, paragraph 7

When the value of the expression in a direct-new-declarator is zero, the allocation function is called to allocate an array with no elements.

---

Quote:

---

Originally Posted by whiteflags

If maxSize is really zero, then you definitely don't need to allocate, but why would maxSize be zero? It should be impossible, since the default constructor doesn't assign maxSize the value of zero.

---

True, it doesn't make sense. But if it doesn't make sense, then why handle it? Why try to set data to NULL if size <= 0?

Quote:

---

Originally Posted by whiteflags

And what would you leak an array with no elements?

---

That doesn't say anything about whether the runtime will allocate extra "book keeping" information, which it may very well do, even if the size is 0.

Because null is even more useful than zero size allocations. By mandating that C++ return something for zero size allocations, it actually made such mistakes into a special case.

Do you have any examples of such a run-time?

#1. size member function should be const.
#2. remove function should check that location is >= 0 or < currsize before doing anything else.
#3. add member function parameter newItem should be a reference.

Quote:

---

Originally Posted by whiteflags

Because null is even more useful than zero size allocations. By mandating that C++ return something for zero size allocations, it actually made such mistakes into a special case.

Do you have any examples of such a run-time?

---

Visual C++ actually allocates book-keeping data even for a 0-size array, if that's what you mean.
So that's a memory leak.