Thread: STL help

  1. #1
    Unregistered
    Guest

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

  2. #2
    S­énior Member
    Join Date
    Jan 2002
    Posts
    982
    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;
    }

  3. #3
    Registered User
    Join Date
    Mar 2002
    Posts
    12
    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.

  4. #4
    Unregistered
    Guest
    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;
    }

  5. #5
    Unregistered
    Guest
    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.

  6. #6
    Registered User
    Join Date
    Mar 2002
    Posts
    12
    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++;
    }
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C Formatting Using STL
    By ChadJohnson in forum C++ Programming
    Replies: 4
    Last Post: 11-18-2004, 05:52 PM
  2. im extreamly new help
    By rigo305 in forum C++ Programming
    Replies: 27
    Last Post: 04-23-2004, 11:22 PM
  3. STL or no STL
    By codec in forum C++ Programming
    Replies: 7
    Last Post: 04-12-2004, 02:36 PM
  4. Prime Number Generator... Help !?!!
    By Halo in forum C++ Programming
    Replies: 9
    Last Post: 10-20-2003, 07:26 PM
  5. include question
    By Wanted420 in forum C++ Programming
    Replies: 8
    Last Post: 10-17-2003, 03:49 AM