iterators and lists

[chineerat]

here i am storing intergers using a list structure
to add or minus polynomials
eg.
2x^2 - 3x^1 + 10
5x^2 - 2
coefficents are stored as num.coeff and the powers are stored as num.pwrs.

struct numbers {
int coeff;
int pwrs;
};
numbers num ;
std::list<numbers> poly1 ;
std::list<numbers> poly2 ;

int main () and whatever

num.coeff=z ;
poly1.push_back(num);
num.pwrs = y;
poly1.push_back(num) ;

num.coeff=z ;
poly2.push_back(num);
num.pwrs = y;
poly2.push_back(num) ;

now using iterators how do i get the elements of the same value stored in num.pwrs of poly 1 and poly2 to add or minus??????????
thanks

 

[ArkM]

As I wrote some days ago: try

std::map<int/*power*/,int/*coeff*/>

(or <int,long>
but not

std::list

for polynoms coding. You can address factors via p[0], p[1] etc.
It takes some time to write a sort of Polynom class derived (or adapted) from map, but it seems you can waste more time to dawdle over low-level list iterator traversals.

 

[globos]

Hi,

I take a little hour this morning to code a class that is based on what ArkM suggested. It is just a proposal, if you want to use it as a basis, test this class before.

So here is the class Poynomial whose internal reprensation for the terms is a map<int, int>. Keys are degrees, and values are coefficients.
From STL documentation, the generic class map is a &quot;Sorted Associative Container&quot; so terms in the map are sorted along ascending degrees.

Here is the class and a little main test :

#include <iostream>
#include <map>
#include <assert.h>

using namespace std;

typedef map<int, int>::const_iterator t_term_iterator;

class Polynomial
{
public:
  //Constructs a polynomial = 0
  Polynomial ()
  {
    _poly[0] = 0;
  }

  //Constructs a polynomial from another
  Polynomial (const Polynomial& other)
  {
    t_term_iterator iterm = other.first_term ();
    while (iterm != other.after_last_term ())
      {
	set_coefficient ((*iterm).first, (*iterm).second);
	iterm++;
      }
  }    

public:
  //Return this + other
  Polynomial operator+ (const Polynomial& other) const
  {
    Polynomial result (other);

    t_term_iterator iterm = first_term ();
    while (iterm != after_last_term ())
      {
	result.set_coefficient ((*iterm).first,
				result.coefficient ((*iterm).first) +
				(*iterm).second);
	iterm++;
      }

    return result;
  }

  //Iterator on the term whose degree is the smallest.
  t_term_iterator first_term () const
  {
    return _poly.begin ();
  }

  //Iterator on the end of the polynomial.
  t_term_iterator after_last_term () const
  {
    return _poly.end ();
  }

  //Degree of the polynomial.
  int degree () const
  {
    t_term_iterator last_term = after_last_term ();

    last_term--;
    assert ((*last_term).first >= 0);
    return (*last_term).first;
  }

  //Coefficient of term whose degree = power.
  int coefficient (int power) const
  {
    assert (power >= 0);
    t_term_iterator iterm = _poly.find (power);

    if (iterm == after_last_term ())
      return 0;
    else
      return (*iterm).second;
  }

  //Set coefficient of term whose degree = power
  void set_coefficient (int power, int coeff)
  {
    assert (power >= 0);

    if (coeff == 0)
      _poly.erase (power);
    else
      _poly[power] = coeff;

    assert (coefficient (power) == coeff);
  }

private:
  map<int, int> _poly;
};

//Print poly on out
ostream& operator<< (ostream& out, const Polynomial& poly)
{
  t_term_iterator iterm = poly.first_term ();
  while (iterm != poly.after_last_term ())
    {
      out << (*iterm).second << &quot;X^&quot; << (*iterm).first << &quot; &quot;;
      iterm++;
    }
  return out;
}

//Little test
int main ()
{
  Polynomial p1;

  p1.set_coefficient (0, 5);
  p1.set_coefficient (1, 15);
  p1.set_coefficient (2, -20);
  p1.set_coefficient (3, 50);

  Polynomial p2 (p1);

  p2.set_coefficient (0, -5);
  p2.set_coefficient (4, 100);

  cout << p1 + p2 << endl;

  return 0;
}

--
Globos

 

[ArkM]

Globos, you are Magnificent! It's bliss to read your code. If chineerat could add some ornamental members, it will be true polynomial engine. For example,

typedef pair<int,int> T;
...
Polynomial::Polynomial(const char* str = &quot;0&quot;);
Polynomial& operator << (const T&);
...
Polynomial p(&quot;5x^2-2&quot;);
...
p << T(2,5) << T(0,-2)... // in spirit of C++ stream i/o
// I feel too lazy to write set_coefficient twice or more

and so on...