C++ Vector Iteratorinvalidierung

[Freezedevil]

Hi,

ich habe folgenden Code welcher sich ueberschneidende Intervalle innerhalb eines Vectors zusammenfuegen soll. Ein Intervall besteht hierbei aus zwei ints fuer jeweils den Start- und Endpunkt. Enthaelt der Vector also die Intervalle

3-5
7-9
4-8
11-15
10-12

Soll er nach dem merge so aussehen

3-9
10-15

Das ganze funktioniert soweit ich das bisher beurteilen kann mit dem folgenden Code auch.

static void sortMerge(std::vector<Interval>* intervals) {
    std::sort(intervals->begin(), intervals->end());
    for (std::vector<Interval>::iterator it = intervals->begin(); it != intervals->end(); ++it) {
        std::vector<Interval>::iterator jt = std::next(it);
        while(it->end >= jt->start && jt != intervals->end()) {
            it->end = it->end >= jt->end ? it->end : jt->end;
            jt = intervals->erase(jt);
        }
    }
}

Mir bereitet es nur ein wenig Bauchschmerzen, dass mir valgrind ein 'Invalid read of size 4' in der Zeile mit dem erase unterstellt. Ausserhalb der Methode kann es keine Iteratoren geben die durch das Loeschen invalidiert werden, da ich nur Kopien des Vectors nach aussen gebe. it sollte meiner Recherche nach nicht invalidiert werden, da er immer vor der Stelle steht an der geloescht wird und jt wird ja direkt wieder auf einen gueltigen Punkt gesetzt.

Ich waere ueber Ideen wie es zu diesem Fehler kommen kann sehr dankbar.

 

[Grantig]

Du versuchst hier:

while(it->end >= jt->start && jt != intervals->end())

jt zu dereferenzieren, was genau solange klappt, bis jt == intervals->end(), da der end()-Iterator (logischerweise) nicht dereferenzierbar ist.

Eigentlich hast dus schon richtig, du musst nur die beiden Bedingungen in der while-Schleife vertauschen.

 

[Nexuiz-Player]

Mir bereitet es nur ein wenig Bauchschmerzen, dass mir valgrind ein 'Invalid read of size 4' in der Zeile mit dem erase unterstellt. Ausserhalb der Methode kann es keine Iteratoren geben die durch das Loeschen invalidiert werden, da ich nur Kopien des Vectors nach aussen gebe. it sollte meiner Recherche nach nicht invalidiert werden, da er immer vor der Stelle steht an der geloescht wird und jt wird ja direkt wieder auf einen gueltigen Punkt gesetzt.

Ich waere ueber Ideen wie es zu diesem Fehler kommen kann sehr dankbar.

Also ich hab mal ein Minimal-Programm geschrieben,

#include <vector>
#include <algorithm>
#include <iterator>
#include <iostream>


class Interval{
	public:
	int start,end;
	Interval(int a, int b):start(a),end(b){};
};

bool operator< (const Interval& lhs,const Interval& rhs){
	return lhs.start<rhs.start || (lhs.start==rhs.start && lhs.end<=rhs.end);
}
bool operator> (const Interval& lhs,const Interval& rhs){
	return rhs<lhs;
}
bool operator== (const Interval& lhs,const Interval& rhs){
	return rhs.start==lhs.start && rhs.end==lhs.end;
}

std::ostream& operator<<(std::ostream& lhs, Interval const& rhs){
	return lhs << "(" << rhs.start << "," << rhs.end <<")";
}


static void sortMerge(std::vector<Interval>* intervals) {
    std::sort(intervals->begin(), intervals->end());
    for (std::vector<Interval>::iterator it = intervals->begin(); it != intervals->end(); ++it) {
        std::vector<Interval>::iterator jt = std::next(it,1);
        while(it->end >= jt->start && jt != intervals->end()) {
            it->end = it->end >= jt->end ? it->end : jt->end;
            jt = intervals->erase(jt);
        }
    }
}

int main(void){
	std::vector<Interval> intervals;
	intervals.push_back(Interval(3,5));
	intervals.push_back(Interval(7,9));
	intervals.push_back(Interval(4,8));
	intervals.push_back(Interval(11,15));
	intervals.push_back(Interval(10,12));
	
	sortMerge(&intervals);
	
    for( std::vector<Interval>::const_iterator it = intervals.begin(); it != intervals.end(); ++it)
       std::cout << *it << std::endl;

	intervals.empty();
	
	return 0;
}

(Keine Garantie für Richtigkeit )


mit valgrind läuft das vollkommen ok, hast du noch irgendwelche Parameter aktiviert?

==18370== Using Valgrind-3.10.0.SVN and LibVEX; rerun with -h for copyright info
==18370== Command: ./interval
==18370==
(3,9)
(10,15)
==18370==
==18370== HEAP SUMMARY:
==18370== in use at exit: 0 bytes in 0 blocks
==18370== total heap usage: 4 allocs, 4 frees, 120 bytes allocated
==18370==
==18370== All heap blocks were freed -- no leaks are possible
==18370==
==18370== For counts of detected and suppressed errors, rerun with: -v
==18370== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

Wenn dein Compiler nicht fehlerhaft ist, liegt es wahrscheinlich an deinem übrigen Code.

 

[Freezedevil]

Du versuchst hier:

while(it->end >= jt->start && jt != intervals->end())

jt zu dereferenzieren, was genau solange klappt, bis jt == intervals->end(), da der end()-Iterator (logischerweise) nicht dereferenzierbar ist.

Eigentlich hast dus schon richtig, du musst nur die beiden Bedingungen in der while-Schleife vertauschen.

Absolut richtig. Ich hab die beiden Bedingungen vertauscht und die Fehler sind weg. Auch wenn es eigentlich logisch ist sieht man manchmal einfach den Wald vor Baeumen nicht. Vielen Dank fuer den Hinweis.

Grosses Danke aber auch an Nexuiz fuer die nicht unerheblichen Muehen.