LINUX.ORG.RU

Segmentation fault на удалении элемента вектора .erase(...)

 ,


0

1

Всем привет!

Помогите разрулить проблему, уже второй час бьюсь!

Быдлокожу алгоритм парсинга формулы. Парсинг работает нормально. Теперь пишу упрощение - раскрытие скобок, функция Simplify.

Весь исходник: http://pastebin.com/C9he4AEK Запускаю так: $ g++ -std=c++11 semantic.cpp -o semantic && ./semantic

При запуске выдает Segmentation fault на удалении элемента из вектора operands.

Еще интересно, что, если убрать вставку (operands.insert(...)) то Segmentation fault нет. Сама вставка проходит корректно и итератор i указывает куда нужно.

Что не так???

Сам код:

void CSum::Simplify()
{
FUNC("");
	vector<CFunction*>::iterator i,j,prev;
	CSum *tmp;
	
	LOG("We are in '"<<PrintTree()<<"'");
	
	for (i=operands.begin();i!=operands.end();i++){
		if ((*i)==nullptr)
			throw "Error in SC: empty operands in Sum";
		LOG("Simplifying operand type:"<<(*i)->PrintType());
		(*i)->Simplify();
		if ((*i)->type==sum){ // Opening Brackets
			LOG("Opening brackets of "<< PrintTree() <<"...");
			j=i;
			j++;
			operands.insert(j,((CBinaryFunction*)(*i))->operands.begin(),((CBinaryFunction*)(*i))->operands.end());
			LOG("...deleting old one "<<(*i)->PrintTree()<<", type:"<<(*i)->PrintType()<<", from "<<PrintTree()<<"...");
// 			tmp=(CSum*)(*i);
// 			delete[] tmp;
			*i=nullptr;
			operands.erase(i);
			LOG("...done");
			i=operands.begin(); // TODO: this is incorrect. We need to continue just from previous element. Fix this!
		}
	};
	
	RETURN("");
};

Структура классов:

class CFunction{
public:
	enum TFunctionType {
		var,
		sum,
		mul
	};
	const TFunctionType type;
	
	CFunction(const TFunctionType t):type(t){};
	
	virtual TFormula Get()=0;
	virtual uint GetOperandsNum()=0;
	virtual bool IsValid()=0;
	
	string PrintType(){ // For debugging needs
		switch (type) {
			case var: return "var";
			case sum: return "sum";
			case mul: return "mul";
		}
		return "unknown";
	}
	virtual string PrintTree()=0; // For debugging needs; prints even invalid structures
	virtual void Simplify()=0; // Expand brackets etc
};

//////////////////////////
class CVariable: public CFunction{
public:
	TValue value;
	bool inverted;
	
	CVariable():CFunction(var),value(""),inverted(false){};
	CVariable(TValue v):CFunction(var),value(v),inverted(false){};
	CVariable(TValue v,bool i):CFunction(var),value(v),inverted(i){};
	
	virtual TFormula Get();
	virtual uint GetOperandsNum(){return 1;};
	virtual bool IsValid(){return !value.empty();};
	virtual string PrintTree(){ if (value.empty()) return "''"; else return value;}; // For debugging needs; TODO: should print invalid structures ; TODO: inversion
	virtual void Simplify(){return;}; // Nothing to simplify in a simple variable
};

//////////////////////////
class CBinaryFunction:public CFunction{ // Actually - function with many arguments
public:
	vector<CFunction*> operands;
	
	CBinaryFunction(const TFunctionType t):CFunction(t){};
	CBinaryFunction(const TFunctionType t,CFunction *o1):CFunction(t){
		AddOperand(o1);
	};
	CBinaryFunction(const TFunctionType t,CFunction *o1,CFunction *o2):CFunction(t){
		AddOperand(o1);
		AddOperand(o2);
	};
	~CBinaryFunction(){
		for (auto i:operands)
			if (i!=nullptr)
				delete[] i;
		operands.erase(operands.begin(),operands.end());
	};
	
	virtual uint AddOperand(CFunction *f){operands.push_back(f);};
	virtual uint GetOperandsNum(){return operands.size();};
	virtual bool IsValid();
};

//////////////////////////
class CSum: public CBinaryFunction{
public:
	CSum():CBinaryFunction(sum){};
	CSum(CFunction *o1):CBinaryFunction(sum,o1){};
	CSum(CFunction *o1,CFunction *o2):CBinaryFunction(sum,o1,o2){};
	~CSum();
	virtual TFormula Get();
	virtual string PrintTree(); // For debugging needs; prints even invalid structures
	virtual void Simplify();
};

//////////////////////////
class CMul: public CBinaryFunction{
public:
	CMul():CBinaryFunction(mul){};
	CMul(CFunction *o1):CBinaryFunction(mul,o1){};
	CMul(CFunction *o1,CFunction *o2):CBinaryFunction(mul,o1,o2){};
	~CMul();
	virtual TFormula Get();
	virtual string PrintTree(); // For debugging needs; prints even invalid structures
	virtual void Simplify();
};

Лог:

semantic.cpp:261: >>> Simplify()
semantic.cpp:265: We are in '(a+(b+c))'
semantic.cpp:270: Simplifying operand type:var
semantic.cpp:270: Simplifying operand type:sum
semantic.cpp:261: >>> Simplify()
semantic.cpp:265: We are in '(b+c)'
semantic.cpp:270: Simplifying operand type:var
semantic.cpp:270: Simplifying operand type:var
semantic.cpp:287: <<< Simplify() returns 
semantic.cpp:273: Opening brackets of (a+(b+c))...
semantic.cpp:277: ...deleting old one (b+c), type:sum, from (a+(b+c)+b+c)...
Segmentation fault

★★★★★

Последнее исправление: Kroz (всего исправлений: 2)

Ответ на: комментарий от Kroz

запусти в gdb, сделай bt и все встанет на свои места.

x0r ★★★★★
()

Помогите разрулить проблему, уже второй час бьюсь!

Не так уж и много, считай только начал. Алсо, запусти в отладчике пошагово, и посмотри где именно крашится.

matrixd
()

ошибка тут:

operands.insert(j,((CBinaryFunction*)(*i))->operands.begin(),((CBinaryFunction*)(*i))->operands.end());
...
operands.erase(i);

anonymous
()

Предлагаю Haskell.

Deleted
()
Ответ на: комментарий от anonymous

В чем ошибка?

Еще наблюдение:
Заменим формулу на такое (574 строка)
str=«a+(b+c)+d»; // То есть добавляем один операнд

Ошибка есть.

Далее заменим в operands.insert последний аргумент на ...->operands.end()-1 . Все работает как надо.

Чего я не вижу?

Kroz ★★★★★
() автор топика
Последнее исправление: Kroz (всего исправлений: 1)
Ответ на: комментарий от anonymous

iterator-invalidation-rules
Insertion
Sequence containers
vector: all iterators and references before the point of insertion are unaffected, unless the new container size is greater than the previous capacity (in which case all iterators and references are invalidated) [23.2.4.3/1]

То есть i корректен после вставки. Ок, это подтверждается логом. Почему я не могу удалить элемент, на который указывает i?

Kroz ★★★★★
() автор топика
#!/bin/bash

rm a.out 2>/dev/null
g++ -x c++ -std=c++11 - <<EOF
#include <iostream>
#include <vector>
int main() {
  const void* tmp = "";
  for(int x=0;x<2;x++) {
    std::vector<const void*> v;
    v.push_back(tmp);
    std::vector<const void*>::iterator i = v.begin();
    v.push_back(tmp);
    if(x==0) i = v.begin();
    std::cout<<"{"<<std::endl;
    v.erase(i);
    std::cout<<"}"<<std::endl;
  }
  return 0;
}
EOF
./a.out
anonymous
()
Ответ на: комментарий от anonymous
#include <iostream>
#include <vector>
int main() {
  const void* tmp = "";
  for(int x=0;x<4;x++) {
    std::vector<const void*> v;
    for(int y=0;y<5;y++) v.push_back(tmp);
    std::vector<const void*>::iterator i = v.begin();
    for(int y=(x<2);y<5;y++) i++;
    if(x%2==0) i = v.begin();
    std::cout<<"{"<<x<<std::endl;
    v.erase(i);
    std::cout<<"}"<<std::endl;
  }
  return 0;
}
anonymous
()
Ответ на: комментарий от anonymous

проблема в изменении размера вектора при insert.

#include <iostream>
#include <vector>
std::vector<int> v;
std::vector<int>::iterator i;
void try_erase() {
  std::cout<<"v.capacity="<<v.capacity()<<std::endl;
  std::cout<<"{"<<std::endl;
  v.erase(i);
  std::cout<<"}"<<std::endl;
}
int main() {
  for(int x=0;x<5;x++)
    v.push_back(x);
  i = v.begin();
  try_erase();

  int n = v.capacity();
  i = v.begin();
  while(n==v.capacity())
    v.push_back(0);
  try_erase();

  return 0;
}

anonymous
()
Ответ на: комментарий от Kroz

unless the new container size is greater than the previous capacity

страница 757

Remarks: Causes reallocation if the new size is greater than the old capacity. If no reallocation happens, all the iterators and references before the insertion point remain valid.

валидны если размер не изменился

anonymous
()
Ответ на: комментарий от tailgunner

Да, я подумаю об этом. Старые C'шные привычки тяжело выбиваются из головы.

Kroz ★★★★★
() автор топика

Первое, что бросилось в глаза:

1. Итерирование сделать вне:

for(i = operands.begin(), end = operands.end(); i != end; )
{
   ++i;
}

2. При удалении элемента:

if(remove_me)
{
   i = operands.erase(i);
   end = operands.end();
   continue;
} 

Итого должно получиться как то так:

for(i = operands.begin(), end = operands.end(); i != end; )
{
   if(remove_me)
   {
      i = operands.erase(i);
      end = operands.end();
      continue;
   } 

   ++i;
}
andreyu ★★★★★
()
Ответ на: комментарий от andreyu

Если я правильно понял отвечавших, то это не сработает, ибо после insert итератор i уже не валиден. Я сделал i uint и использую как operands.begin()+i . Так работает.

Kroz ★★★★★
() автор топика
Ответ на: комментарий от Kroz

Если я правильно понял отвечавших, то это не сработает, ибо после insert итератор i уже не валиден.

Не обратил внимания на инсерт.

andreyu ★★★★★
()

Проблема в том, что ты в том же цикле что и итерируешься удаляешь элемент. Ты удаляешь самого себя, а потом итератору, который никуда уже не указывает ( ты же его удалил ) делаешь ++.

Chubakur ★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.