c++: STL链接+=复制节点

Question

我正在研究一个使用STL链表的多项式类。其中一个函数需要我把两个多项式相加。由于某种原因，+=操作符似乎在复制节点，而不是仅仅修改内容。

下面是类声明:

class Polynomial
{
    public:
        Polynomial(pair<double,int>); //Specified constructor
        void add(const Polynomial&);
        void print();
    private:
        Polynomial(); //Default constructor
        list<pair<double,int> > terms;
};

这是add成员函数:

void Polynomial::add(const Polynomial& rhs)
    {
    list<pair<double,int> >::const_iterator r;
    list<pair<double,int> >::iterator l;
    for(r=rhs.terms.begin(); r!=rhs.terms.end(); r++)
    {
        bool match=0;
        //Check to see if we have an existing nth order node
        for(l=terms.begin(); l!=terms.end(); l++)
        {
            //If we do, just add the coefficients together
            if(l->second == r->second)
            {
                l->first += r->first;
                match = 1;

            }       
        }
        //If there was no matching existing node, we need to find out
        //where to insert it into the list.
        if(!match)
        {
            l=terms.begin();
            bool inserted=0; //Sentinel for the loop
            while(l!=terms.end() && !inserted)
            {               
                //If there's only one term in the list
                //Just compare and stick it in front or behind the existing node
                if(terms.size()==1)
                {
                    int this_exp = l->second;
                    int exp_to_ins = r->second;
                    if(exp_to_ins > this_exp) terms.push_back((*r));
                    if(exp_to_ins < this_exp) terms.push_front((*r));
                    inserted = 1;
                }
                //If there's more than one node, we need to traverse the list
                if(terms.size()>1)
                {
                    if(l!=terms.begin())
                    {
                        int this_exp = l->second;
                        l++;
                        int next_exp = l->second;
                        int exp_to_ins = r->second;
                        //If the new node value is between the current and next node
                        //Insert between them.
                        if((this_exp < exp_to_ins) && (exp_to_ins < next_exp))
                        {
                            terms.insert(l,(*r));                    
                            inserted = 1;
                        }
                     } 
                     else if(l==terms.begin())
                     {
                        int this_exp = l->second;
                        int exp_to_ins = r->second;

                        //This will be the smallest order node
                        //Put it in the top spot
                        if(this_exp > exp_to_ins) 
                        {
                            terms.push_front((*r));
                            inserted = 1;
                        }
                        l++;                    
                     }                  
                }
            }
            //If we've traversed the list and can't find the right place
            //this must be the greatest order node in the list
            //so just tack it on the end.
            if(!inserted) terms.push_back((*r));
        }
    }

}

以正确的顺序对节点进行排序可以很好地工作，但是我们有一个现有的第n阶节点，而不仅仅是将系数相加，它保留了原始节点，但似乎使第二个节点将系数相加，我不知道为什么。

如果我运行打印函数，应该是F(x) = -2x^7 + 3x^6 - 11x^5 -2x^ 4，而不是F(x) = -2x^7 + 3x^6 - 11x^5 - 10x^5。如果我在列表上调用size()函数，我得到4。但是如果我运行下面的代码来打印列表中节点的信息:

stringstream test;   
for(i=terms.end(); i!=terms.begin(); i--)
{
    test << "Coefficient: " << i->first << " ";
    test << "Exp: " << i->second << endl;
}
cout << "Size: " << terms.size() << endl;
cout << test.str(); 

输出如下:

系数:-10 Exp: 5系数:-2 Exp: 7系数:3 Exp: 6系数:-11 Exp: 5

任何帮助都非常感谢。

编辑:这是测试程序。

Polynomial p(pair<double, int>(-10, 5));
p.add(Polynomial(pair<double,int> (-2,4)));
p.add(Polynomial(pair<double,int> (3,6)));
p.add(Polynomial(pair<double,int> (-2,7)));
p.add(Polynomial(pair<double, int> (-1,5)));

Answer 1

您的add()函数似乎是正确的，除了打印:

for(i=terms.end(); i!=terms.begin(); i--)
{    
    test << "Coefficient: " << i->first << " ";
    test << "Exp: " << i->second << endl;
}

这是完全错误的，并且会调用未定义的行为。i最初是terms.end()，你对它进行了微分?items.end()返回遍历迭代器。即使我暂时假设它是正确的，条件i!=terms.begin()意味着永远不会打印第一个元素!

所以修复是这样的:

for(list<pair<double,int> >::iterator i=terms.begin(); i!=terms.end(); i++)
{
    test << "Coefficient: " << i->first << " ";
    test << "Exp: " << i->second << endl;
}

输出预期输出:

Size: 4
Coefficient: -2 Exp: 4
Coefficient: -11 Exp: 5
Coefficient: 3 Exp: 6
Coefficient: -2 Exp: 7

是不正确的吗?

也可以在这里查看自己的输出:http://www.ideone.com/p8mwJ

---

顺便说一下，你可以把它改成operator+=而不是add，如:

const Polynomial& operator+=(const Polynomial& rhs)
{
    //same code as before
    return *this;
}

如果你这样写，那么你可以添加多项式:

Polynomial p(pair<double, int>(-10, 5));
p += Polynomial(pair<double,int> (-2,4));
p += Polynomial(pair<double,int> (3,6));
p += Polynomial(pair<double,int> (-2,7));
p += Polynomial(pair<double, int> (-1,5));

Demo: http://www.ideone.com/aA1zF

---

我刚刚读了你的评论，知道你想以相反的顺序打印它，在这种情况下，你可以使用rbegin()和rend()代替begin()和end()作为:

for(list<pair<double,int> >::const_reverse_iterator i=terms.rbegin(); 
                                                    i!=terms.rend(); 
                                                    i++)
{
    test << "Coefficient: " << i->first << " ";
    test << "Exp: " << i->second << endl;
}

我还建议您将print作为const函数:

void print() const
            //^^^^ this makes the function const!

最好重载operator<<。

倒序打印演示:http://www.ideone.com/Vk6XB

Answer 2

您的测试循环(在stringstream中打印的那个)是不正确的:取消引用end()迭代器是未定义的行为。可能你的"std::list"是以循环的方式实现的(即begin == end+1)，所以解引用"end"会在测试循环中给你*begin。

使用反向迭代器以相反的顺序打印列表:

for (i = list.rbegin (); i != list.rend (); ++i)
{
   test << "Coefficient: " << i->first ; // etc.
} 

Answer 3

除了@Nawaz指出的问题，Polynomial::add函数也存在问题。

如果if(terms.size()==1)块被执行，则在列表中插入一个新项。但是这会使列表的大小增加1，所以if(terms.size()>1)块也会被执行。这可以再次插入相同的节点。

在while循环中，您增加l，并继续使用下一个节点，而不检查它是否有效(即。(不与terms.end()比较)。

可能还有更多这样的错误，但这些都是粗略浏览后出现的