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

Это функция добавления члена:

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 Опыт: 5 Коэффициент: -2 Опыт: 7 Коэффициент: 3 Опыт: 6 Коэффициент: -11 Опыт: 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

---

Кстати, вместо add вы могли бы сделать это operator+= вместо этого, как:

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));

Демо: 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 постоянной функцией как:

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

Еще лучше, перегрузка operator<<.

В любом случае демонстрация печати в обратном порядке: http://www.ideone.com/Vk6XB

Answer 2

Помимо проблемы, указанной @Nawaz, есть также проблема в функции Polynomial::add.

Если выполняется блок if(terms.size()==1), в список добавляется новый элемент.Но это увеличивает размер списка на единицу, поэтому блок if(terms.size()>1) также будет выполнен.И это может вставить один и тот же узел еще раз.

Чуть дальше в цикле while вы увеличиваете l и продолжаете использовать следующий узел, не проверяя его действительность (т. Е. Не сравнивая с terms.end()).

Таких ошибок может быть и больше, но они появились после беглого взгляда.

Answer 3

Ваш тестовый цикл (тот, который печатает в потоке строки) неверен: это неопределенное поведение для разыменования итератора end (). Вероятно, ваш "std :: list" реализован по кругу (то есть с begin == end + 1), поэтому разыменование "end" дает вам * begin в вашем цикле тестирования.

Используйте обратные итераторы для печати списка в обратном порядке:

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