Valgrind says that const-iterator tries to access uninitialised space, but actually it is

Question

I'm trying to use const_iterators to go through a list of elements (the elements of a matrix).

SparseMatrix matd(5,5,0); //5x5 matrix with 0 as default element.
//Follows elements insertion...
SparseMatrix<int>::const_iterator a,b;
a=matd.cbegin();
b=matd.cend();
while(a!=b){
    cout<<*(a->data)<<endl;
    ++a;
}

But there's something wrong, as valgrind reports.

==4662== Use of uninitialised value of size 8

==4662== at 0x403A19: SparseMatrix::findRow(int) const (SparseMatrix.h:120)

==4662== by 0x40431A: SparseMatrix::findNext(el const*) const (SparseMatrix.h:439)

==4662== by 0x4030B3: SparseMatrix::const_iterator::operator++() (SparseMatrix.h:593)

==4662== by 0x401D63: main (main.cpp:121)

==4662==

==4662== Invalid read of size 4

==4662== at 0x403A27: SparseMatrix::findRow(int) const (SparseMatrix.h:123)

==4662== by 0x40431A: SparseMatrix::findNext(el const*) const (SparseMatrix.h:439)

==4662== by 0x4030B3: SparseMatrix::const_iterator::operator++() (SparseMatrix.h:593)

==4662== by 0x401D63: main (main.cpp:121)

==4662== Address 0xa680020611a25ff is not stack'd, malloc'd or (recently) free'd

==4662==

==4662==

==4662== Process terminating with default action of signal 11 (SIGSEGV)

==4662== General Protection Fault

==4662== at 0x403A27: SparseMatrix::findRow(int) const (SparseMatrix.h:123)

==4662== by 0x40431A: SparseMatrix::findNext(el const*) const (SparseMatrix.h:439)

==4662== by 0x4030B3: SparseMatrix::const_iterator::operator++() (SparseMatrix.h:593)

==4662== by 0x401D63: main (main.cpp:121)

since I use findNext and findRow with normal iterators and other class methods, and they work, I think there's something wrong in operator++():

const_iterator& operator++() { const element *tmp=e; e=sm->findNext(tmp); delete tmp; return *this; }

const_iterator's copy constructor:

const_iterator(const const_iterator& it) { e=it.e; }

Moreover, const_iterators created and used inside a class' method work very well.

PS: The code of findRow

    mrow* findRow(int i) const {
    mrow *tmp = matrix;
    while(tmp!=NULL){
        if(tmp->idx == i) return tmp;
        tmp=tmp->next;
    }   
    return NULL;
}

It passes an if(tmp==NULL) check, so it thinks there's something there in memory, but then it says that it's uninitialized, but I'll say it again, if I use normal iterator it works.

Here's code for findNext

    element* findNext(const element* e) const {
    int r=e->i; 
    int c=e->j;
    int riga,colonna; 
    riga=r;
    while(riga!=-1){
            if(riga==r) {
                mrow *m=findRow(riga); 
                colonna=nextCol(m,c);
                if(colonna!=-1) {
                    T* d=&((findCol(findRow(riga),colonna)->data)); 
                    return genElement(riga,colonna,d);      
                }           
            }
            else{
                colonna=nextCol(findRow(riga),-1);
                if(colonna!=-1) {
                    T* d=&((findCol(findRow(riga),colonna)->data));
                    return genElement(riga,colonna,d);      
                }                       
            }
            riga=nextRow(riga);
    }
    return NULL;
}

Code for constructor SparseMatrix(int,int,T)

    SparseMatrix(int r, int c, T d){
    rows=r;
    cols=c;
    def=d;
    msize=0;
    matrix=NULL;
}

If you need more code just ask.

In addition let me confirm again that I use findRow and findNext for other purposes, and they work. I think that it's something related to constness, but can't get what.

Answer 1

This solved my problem: Use of uninitialised value of size 8

It was an error in the code. In iterator assignment operator I forgot to initialize a fundamental value. This caused all the iterators, with the only exception of begin(), to read in the wrong place as their pointer to sparsematrix wasn't initialized.

Answer 2

"Use of uninitialised value of size 8 at 0x403A19: SparseMatrix::findRow(int) const (SparseMatrix.h:120)" and "Invalid read of size 4 at 0x403A27: SparseMatrix::findRow(int) const (SparseMatrix.h:123)"

Tells us that you read from a value that was uninitialized, and then three lines later, you dereference an invalid pointer. From the code you shown, those must correspond with these lines:

mrow *tmp = matrix; //matrix is unassigned, but not NULL.  It's random
tmp=tmp->next; //then dereferenced a completely random place in memory

So, this tells me that your object was invalid. If you're certain that the const iterator has something to do with it, I'd imagine the const_iterator's internal SparseMatrix* pointer is incorrect. Can we see the copy constructor and/or the operator++()?

[Edit] Now that I've seen that operator++ deletes it's e member, and assigns it to the result of findNext, we know that e is a pointer that points to dynamically allocated data (an element). We also see that your copy constructor does a shallow copy of that pointer, meaning that as soon as you create one from anther, the temporary is deleted, and the "new" iterator is pointing at invalid memory. And it will "work" sometimes. Except sometimes it won't. Or it could install a virus. Or Whatever. Don't underestimate Undefined Behavior

a=matd.cbegin();
(1) cbegin() creates an iterator, which allocates a new element.
(2) you assign that temporary to a, and copy the pointer.
(3) The temporary is deleted, and deletes the element.
(4) a now points at that (invalid) deleted element

The normal advice at this point, is always assign allocated memory to a smart pointer, almost always a std::unique_ptr, and you won't have this problem ever again. Tip: if you have delete in your code, you're doing it wrong.