using C++ list library as a linked list

Question

I am trying to make a farey seq program with C++ list library

My program works fine when I use the first level, however, it crashes after that with all other levels for some reason.

I am using visual studio as a compiler. I tried the debugger mode as well as the resource. The program doesn't crash in the resource mode, however, it doesn't give me the even numbers levels output. In addition, it gives me half of the odds levels output for some reason.

I want to fix this problem and I want it to work in the dubgger mode as well.

Any suggestions?

Here is what I've done so far

  class RULLZ: public list<Fraction>
  {
    private:
    list<Fraction>::iterator head,tail,buf,buf1;
    public :
      Farey2()
    {
      this->push_front( Fraction(1,1));
      this->push_front( Fraction(0,1));

}

  void Add(int level)

  {
    Fraction *tmp,*tmp2;
    buf=this->first();
    for(int i=0;i<level-1;i++)  
    {


      head=this->first();
      tail=this->last();
      while(head!=tail)
      {

        tmp=new Fraction(head->num,head->den);
        head++;
        if(tmp->den+head->den<=level)
        {
          tmp2=new Fraction(tmp->num+head->num,tmp->den+head->den);
          this->insert(head,*tmp2); 
          head--;
        }


      }
      this->pop_back();
    }





  }

  friend ostream& operator<<(ostream& out,  RULLZ& f)
  {
    for(list<Fraction>::iterator it=f.first();it !=f.last();it++)
      out <<*it;
    return out;
  }

  };

In release mode, allocated memory is usually cleared, while in debug mode it's filled with some hex pattern like 0xcdcdcdcd. For example, uninitialized pointers maybe NULL in release mode, but always invalid in debug mode. — rcgldr, Feb 18 '14 at 19:15

score 0 · Answer 1 · edited May 23 '17 at 12:03

class RULLZ: public list<Fraction>

Before even looking at your question, the above code is a problem. The C++ standard containers are deliberately not designed to be base classes (none of them have a virtual destructor), so this will cause problems. For reasons why you should not publicly derive from a standard container, see the following:

It appears you want the Add function to add the next X number of fractions together (if I understand your intent correctly). A better way to do that is to use a std::stack:

std::stack<Fraction, std::list<Fraction>> expression;
// add fractions to your stack here
Fraction Add(unsigned int count)
{
    // assume count is greater than 1 (as adding 0 fractions makes no sense, and adding 1 is trivial)
    Fraction result(0, 1);
    for (int i = 0; i < count; ++i)
    {
        Fraction a = expression.top();
        expression.pop();
        Fraction b = expression.top();
        expression.pop();
        result += a + b; // assume operators + and += have been implemented for Fraction
    }
    expression.push(result);
    return result;
}

Another problem you appear to have is a logic problem (again, assuming I understand your intent correctly):

for(int i=0;i<level-1;i++)

If level is the number of fractions you want to add, and you pass in 2, this loop will only include the first one. That is, it will not add fractions 0 and 1, but rather just grab fraction 0 and return it. I think you meant for this to be

for(int i=0; i < level; i++)

Which will grab both fractions 0 and 1 to add together.

I'm not sure where, but your logic for generating the series appears to be off. A more simple approach can be found here:

#include <algorithm>
#include <cstdint>
#include <iterator>
#include <iostream>
#include <vector>

struct Fraction
{
    std::uint32_t Numerator;
    std::uint32_t Denominator;
    Fraction(std::uint32_t n, std::uint32_t d) : Numerator(n), Denominator(d) { }
};

std::ostream& operator<<(std::ostream& os, const Fraction& f)
{
    os << "(" << f.Numerator << " / " << f.Denominator << ")";
    return os;
}

typedef std::vector<Fraction> FareySeries;

FareySeries generate_series(std::uint32_t depth)
{
    std::uint32_t a = 0;
    std::uint32_t b = 1;
    std::uint32_t c = 1;
    std::uint32_t d = depth;
    FareySeries results;
    results.emplace_back(a, b);
    while (c <= depth)
    {
        std::uint32_t k = (depth + b) / d;
        std::uint32_t nc = (k * c) - a;
        std::uint32_t nd = (k * d) - b;
        a = c;
        b = d;
        c = nc;
        d = nd;
        results.emplace_back(a, b);
    }
    return results;
}

int main()
{
    const std::uint32_t DEPTH = 4;
    FareySeries series = generate_series(DEPTH);
    std::copy(series.begin(), series.end(), std::ostream_iterator<Fraction>(std::cout, "\n"));
    return 0;
}

Actually there is nothing wrong with this implementation as I've used it before in another program using the list library — rullzing, Feb 18 '14 at 18:17
Not having a virtual destructor does not lead to them not being good base classes. This inheritance does not necessarily cause problems. — juanchopanza, Feb 18 '14 at 18:17
@ZacHowland I know what you're saying but I simply want to use the list standard library of C++ — rullzing, Feb 18 '14 at 18:28
@rullzing Then use it - don't derive from it. Declare a `std::list` as a member variable to your `RULLZ` class. — Zac Howland, Feb 18 '14 at 18:31
@rullzing Alternatively, you *can* use private inheritance for this (which is effectively the same as composition). But bear in mind that if you really wanted to use a `std::list`, you can just pass it as the second template parameter to the `std::stack`: `std::stack>`. — Zac Howland, Feb 18 '14 at 18:42

using C++ list library as a linked list

1 Answers1