-
STL help
Hello if anyone is kind enough to help me out with this problem. Basically what I am trying to do is after two polynomials gets multiplied, I want to simplify all the like terms. For example lets say after multiplication of two polynomials the answer is "2x^3+3x+4x^2+5x+1". I want the simplify function to put the like terms together. Now the answer gets stored in a list called TermList. I know my code works except for one place. That is where I am deleting the node. I am new to stl, I know how to handle this issue with regular link list but with stl I am not sure how to do it. The logic of this function is one pointer will point to the first node (curTerm), and an another pointer (nextTerm) will traversre the list looking for like term. If not found nextTerm pointer will move on. But if found nextTerm node's base will get added to the curTerm base and nextTerm node will get deleted. Now I know in a link list I would just have an extra pointer trail behind the nextTerm, and during deletion I would just point the trailing pointer point to nextTerm->next. and then delete the nextTerm node. But with stl I know that you do not have to do that. I just do not know how to do it though. I did add my code on the bottom, please tell me what I need to do to make this work. Thank you in advance.
P.S. if anyone has a better algorithm to this, I would be more than glad to take suggestions.
void Polynomial::Simplify()
{
cout<<"simplfy() is getting executed" << endl; //for testing purpose
list<Term>::iterator curTerm; //iter will be compared to
list<Term>::iterator nextTerm;//iter will traverse and compare
list<Term>::iterator delTerm;//iter not really needed added for testing
curTerm = TermList.begin();//iter points at the beggining of the list
nextTerm = TermList.begin();
for(curTerm; curTerm != TermList.end(); curTerm++)
{
nextTerm = curTerm++;
cout<<"simplify: currterm is: " << curTerm->base << " " << curTerm->exp << endl;//testing purpose
for(nextTerm; nextTerm != TermList.end(); nextTerm++)
{
cout<<"nextTerm is: " << nextTerm->base << " " << nextTerm->exp <<endl;//testing purpose
if(curTerm->exp == nextTerm->exp)
{//if like term is found
cout<<"found match" << endl;
curTerm->base = curTerm->base + nextTerm->base;
delTerm = nextTerm;//trying to delete the node
delTerm = TermList.erase(delTerm);
nextTerm++;
}
}
}
}
-
You could use a std::map instead of a list, it may simplify things -
Code:
#include <map>
#include <iostream>
using namespace std;
typedef int exp;
typedef int coef;
int main()
{
map<exp,coef> p;
//polynomial 2x^3+3x+4x^2+5x+1
p[3]+=2;
p[1]+=3;
p[2]+=4;
p[1]+=5;
p[0]+=1;
map<exp,coef>::reverse_iterator i;
for (i=p.rbegin();i!=p.rend();++i)
{
cout << i->second << '^' << i->first << '+';
}
return 0;
}
-
Hey Sorensen,
Thank you for your suggestion, but I really have to use the stl<list>, unfortunatly that is one of the requirment of the project. But Thank you for your time.
-
From my readings about, but extensive use of, STL, it is my understanding that if you are using STL lists and the "nodes" represent simple values like int, double, etc, then you can use the generic find() function to generate an iterator that "points" to thefirst node that has a given value, and then use the list erase() method to erase the iterator. However, if it is a list is complex objects --that is each node in the list has more than one member, then I think you need to use the generic find_if() function which takes a function object rather than a value. here's an example you can try something like :
Goal: remove the Node with value of 3 from the list
WARNING: The following code is untested. It represents my best ideas as to how to work with the STL list class, find_if() and function objects. Who kow what mistakes lurk therein.
#include<iostream>
#include<list>
using namespace std;
//create a struct to hold data
struct Node
{
int value;
int id;
};
//create a class to generate the fucntion object for find_if()
class NodeTester
{
public:
//constructor
NodeTester(int value) {search_value = value;}
//public data member
int search_value = value;
//define a function call operator
bool operator() (Node & node)
{return node.value == search_value}
};
int main{}
//create a list of nodes
list<Node> Data;
int i;
//declare a holding node
Node temp;
//build list adding each new node to tail of list
for(i = 0; i < 4; i++)
{
temp.value = i;
temp.id = i + 1000;
Data.push_back(temp);
}
//declare iterator to define position in list
list<Node>::iterator current;
//now display list of Nodes
for(current = Data.begin(); current != Data.end(); current++)
{
cout << current->value << ' ' << current->id << endl;
}
//declare an instance of the NodeTester looking for any Node with
//value equal to 3
NodeTester nTest(3);
//use the NodeTester as the function object in find_if() and use
//find_if to search for first instance of Node with value == 3;
current = find(Data.begin(), Data.end(), nTest);
//now use current to erase the instance of the Node with value == 3;
Data.erase(current);
//now display altered list
for(current = Data.begin(); current != Data.end(); current++)
{
cout << current->value << ' ' << current->id << endl;
}
return 0;
}
-
I guess I should really log in so I can correct my mistakes. My post should have indicated that I don't have extensive experience with STL containers/routines. Sorry.
-
Thank you so very much for every ones help, it is working now.. For anyone who is maybe interested to learn from my mistake, here is my code that works. You can compare the previous one to this one and see where I made changes.
void Polynomial::Simplify()
{
cout<<"simplfy() is getting executed" << endl;
list<Term>::iterator curTerm;
list<Term>::iterator nextTerm;
list<Term>::iterator delTerm;
curTerm = TermList.begin();
nextTerm = TermList.begin();
while(curTerm != TermList.end())
{
cout<<"simplify: currterm is: " << curTerm->base << " " << curTerm->exp << endl;
nextTerm = curTerm;
nextTerm++;
while(nextTerm != TermList.end())
{
cout<<"nextTerm is: " << nextTerm->base << " " << nextTerm->exp;
if(curTerm->exp == nextTerm->exp)
{
cout<<" : match" << endl;
curTerm->base = curTerm->base + nextTerm->base;
delTerm = nextTerm;
nextTerm++;
TermList.erase(delTerm);
}
else
{
cout<<" : no match"<<endl;
nextTerm++;
}
}
curTerm++;
}
}