Thread: Beginner C++: Templates & Ordered List question

  1. #1
    Registered User
    Join Date
    Oct 2011
    Posts
    4

    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

  2. #2
    Just a pushpin. bernt's Avatar
    Join Date
    May 2009
    Posts
    426
    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?
    Last edited by bernt; 10-23-2011 at 03:08 PM.
    Consider this post signed

  3. #3
    Registered User
    Join Date
    Oct 2011
    Posts
    4
    Ah, that would be two events I should probably handle eh?

  4. #4
    Registered User
    Join Date
    Oct 2011
    Posts
    4
    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

  5. #5
    Just a pushpin. bernt's Avatar
    Join Date
    May 2009
    Posts
    426
    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.)
    Last edited by bernt; 10-23-2011 at 04:50 PM.
    Consider this post signed

  6. #6
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Can't use std::vector?
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  7. #7
    Registered User
    Join Date
    Oct 2011
    Posts
    4
    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
    ?

  8. #8
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    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 Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  9. #9
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    Quote Originally Posted by Elysia View Post
    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.

  10. #10
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    And what would you leak an array with no elements?

    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.

  11. #11
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Quote Originally Posted by whiteflags View Post
    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 View Post
    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.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  12. #12
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    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?

  13. #13
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,817
    #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.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  14. #14
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Quote Originally Posted by whiteflags View Post
    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.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Problem with search function within an ordered list
    By drew99 in forum C Programming
    Replies: 8
    Last Post: 09-02-2011, 01:03 PM
  2. insertion in an ordered list ?
    By jack_carver in forum C Programming
    Replies: 1
    Last Post: 03-21-2009, 11:11 AM
  3. ordered linked list
    By redmondtab in forum C Programming
    Replies: 48
    Last Post: 10-22-2006, 06:09 AM
  4. problme with ordered linked list
    By palku in forum C Programming
    Replies: 5
    Last Post: 09-19-2005, 04:33 PM

Tags for this Thread