problem with C++ stl (deque and vector)

P

pieter.eendebak

Dear newsgroup,

I am trying to run the program below. When I use a STL vector the
program runs fine, but when using a deque I get a segmentation fault
at the line

sort ( hlist.begin(), hlist.end() );

I do not have the same problem when I use deque<int> instead of my own
class deque<array_link>. I checked the program with Valgrind, and
these are warnings about uninitialized values, but these are generated
within the C++ STL code.

Can sort be used with the deque iterations begin() and end()?
Have I defined all necessary assignment and copy constructor functions
for my class?

With kind regards,
Pieter Eendebak

#include <stdio.h>
#include <stdlib.h>

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>


using namespace std;

struct array_link
{
int size;
int index;
int * array;

array_link();
~array_link();
array_link(const array_link &);
array_link(int size, int index);

array_link &operator=(const array_link &rhs);
int operator==(const array_link &rhs) const;
int operator<(const array_link &rhs) const;
};


array_link::array_link(): size(-1), index(-1), array(0)
{
//printf("array_link::default constructor\n");
}

array_link::~array_link()
{
//printf("array_link:destructor() %d\n", index);
}

array_link::array_link(int s, int index_): size(s), index(index_)
{
this->array = new int;
for(int i=0;i<size;i++)
array=i*i;
}

array_link::array_link(const array_link &A): size(A.size), index
(A.index), array(A.array)
{
//printf("array_link::default copy constructor: count %d\n", count);
}


/**
* @brief Assignment operator
*/
array_link & array_link::eek:perator=(const array_link& rhs)
{
this->size = rhs.size;
this->index = rhs.index;
this->array = rhs.array;
return *this;
}

int array_link::eek:perator<(const array_link& b) const
{
if (this->size != b.size) {
printf("array_link::eek:perator< comparing arrays (%d %d) with
different sizes: (%d) (%d)!\n", this->index, b.index, this->size,
b.size);
return 0;
}

return memcmp(this->array, b.array, sizeof(int)*this->size) <= 0;
}

// Comparision operator for the array link
int array_link::eek:perator==(const array_link& b) const
{
if (this->size != b.size) {
printf("array_link::eek:perator== comparing arrays (%d %d) with
different sizes: (%d) (%d)!\n", this->index, b.index, this->size,
b.size);
return 0;
}

return memcmp(this->array, b.array, sizeof(int)*this->size)==0;
}

int main ( int argc, char* argv[] ) {

deque<array_link> hlist;
//vector<array_link> hlist;

const int defaultsize=4;

for ( int hcol=0; hcol<120; hcol++ ) {
cout << "loop " << hcol << endl;
array_link link ( defaultsize, hcol+100 );
hlist.push_back ( link ); hlist.push_back ( link );

for ( unsigned int xx=0;xx<hlist.size();xx++ ) {
printf ( "hlist[%d]: index %d, size %d \n", xx, hlist[xx].index,
hlist[xx].size );
}
printf ( "sorting: %d values\n", hlist.end()-hlist.begin() );
sort ( hlist.begin(), hlist.end() );
}
}
 
T

tni

The comparison function must define a strict weak ordering, yours doesn't.

int array_link::eek:perator<(const array_link& b) const {
return memcmp(this->array, b.array, sizeof(int)*this->size) <= 0;
}

Instead of '<=', use '<'.
 
P

pieter.eendebak

The comparison function must define a strict weak ordering, yours doesn't..

int array_link::eek:perator<(const array_link& b) const {
     return memcmp(this->array, b.array, sizeof(int)*this->size) <= 0;

}

Instead of '<=', use '<'.

Thanks! Solved my problem.
 
J

jason.cipriani

Dear newsgroup,

I am trying to run the program below. When I use a STL vector the
program runs fine, but when using a deque I get a segmentation fault
at the line

sort ( hlist.begin(), hlist.end() );

I do not have the same problem when I use deque<int> instead of my own
class deque<array_link>. I checked the program with Valgrind, and
these are warnings about uninitialized values, but these are generated
within the C++ STL code.

Can sort be used with the deque iterations begin() and end()?
Have I defined all necessary assignment and copy constructor functions
for my class?

With kind regards,
Pieter Eendebak

#include <stdio.h>
#include <stdlib.h>

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>

using namespace std;

struct array_link
{
        int size;
        int index;
        int * array;

        array_link();
        ~array_link();
        array_link(const array_link &);
        array_link(int size, int index);

    array_link &operator=(const array_link &rhs);
        int operator==(const array_link &rhs) const;
    int operator<(const array_link &rhs) const;

};

array_link::array_link(): size(-1), index(-1), array(0)
{
        //printf("array_link::default constructor\n");

}

array_link::~array_link()
{
        //printf("array_link:destructor() %d\n", index);

}

array_link::array_link(int s, int index_): size(s), index(index_)
{
        this->array = new int;
        for(int i=0;i<size;i++)
                array=i*i;

}

array_link::array_link(const array_link &A): size(A.size), index
(A.index), array(A.array)
{
        //printf("array_link::default copy constructor: count %d\n", count);

}

/**
 * @brief Assignment operator
 */
array_link & array_link::eek:perator=(const array_link& rhs)
{
        this->size = rhs.size;
        this->index = rhs.index;
        this->array = rhs.array;
        return *this;

}

int array_link::eek:perator<(const array_link& b) const
{
        if (this->size != b.size) {
                printf("array_link::eek:perator< comparing arrays (%d %d) with
different sizes: (%d) (%d)!\n", this->index, b.index, this->size,
b.size);
                return 0;
        }

        return memcmp(this->array, b.array, sizeof(int)*this->size) <= 0;

}

// Comparision operator for the array link
int array_link::eek:perator==(const array_link& b) const
{
        if (this->size != b.size) {
                printf("array_link::eek:perator== comparing arrays (%d %d) with
different sizes: (%d) (%d)!\n", this->index, b.index, this->size,
b.size);
                return 0;
        }

        return memcmp(this->array, b.array, sizeof(int)*this->size)==0;

}

int main ( int argc, char* argv[] ) {

        deque<array_link> hlist;
        //vector<array_link> hlist;

        const int defaultsize=4;

        for ( int hcol=0; hcol<120; hcol++ ) {
                cout << "loop " << hcol << endl;
                array_link link ( defaultsize, hcol+100 );
                hlist.push_back ( link ); hlist.push_back ( link );

                for ( unsigned int xx=0;xx<hlist.size();xx++ ) {
                        printf ( "hlist[%d]: index %d, size %d \n", xx, hlist[xx].index,
hlist[xx].size );
                }
                printf ( "sorting: %d values\n",  hlist..end()-hlist.begin() );
                sort ( hlist.begin(), hlist.end() );
        }

}




You realize you are leaking memory all over the place with this,
right?

void f () {
array_link alink(100, 0);
}

Does not free the array data, and loses the pointer to it, meaning you
can never reclaim it. Also:

void f () {
array_link alink1(100, 0);
array_link alink2;
alink1 = alink2;
// ^ alink1's data not freed, pointer lost, leaked.
}

Again, alink1 allocates a new array and never deletes it, the pointer
value is simply overwritten by alink2's by your shallow copy
assignment operator.

Jason
 
J

James Kanze

I am trying to run the program below. When I use a STL vector
the program runs fine, but when using a deque I get a
segmentation fault at the line
sort ( hlist.begin(), hlist.end() );
I do not have the same problem when I use deque<int> instead
of my own class deque<array_link>. I checked the program with
Valgrind, and these are warnings about uninitialized values,
but these are generated within the C++ STL code.

There are a lot of problems with your code. And errors in your
code can easily cause the STL to access unintialized memory.
Can sort be used with the deque iterations begin() and end()?

Of course.
Have I defined all necessary assignment and copy constructor
functions for my class?

Not correctly.
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
using namespace std;
struct array_link
{
int size;
int index;
int * array;
array_link();
~array_link();
array_link(const array_link &);
array_link(int size, int index);
array_link &operator=(const array_link &rhs);
int operator==(const array_link &rhs) const;
int operator<(const array_link &rhs) const;
};
array_link::array_link(): size(-1), index(-1), array(0)
{
//printf("array_link::default constructor\n");
}
array_link::~array_link()
{
//printf("array_link:destructor() %d\n", index);
}
array_link::array_link(int s, int index_): size(s), index(index_)
{
this->array = new int;
for(int i=0;i<size;i++)
array=i*i;
}


You're dynamically allocating memory in the constructor. You'll
have to define what this means with regards to copy and
assignment, and where you'll delete it. (Deep copy vs. shallow,
but you have to be consistent.)

array_link::array_link(const array_link &A): size(A.size), index
(A.index), array(A.array)
{
//printf("array_link::default copy constructor: count %d\n", count);
}

Here, you've implemented shallow copy. Shallow copy is
difficult to get right in the absense of garbage collection.
/**
* @brief Assignment operator
*/
array_link & array_link::eek:perator=(const array_link& rhs)
{
this->size = rhs.size;
this->index = rhs.index;
this->array = rhs.array;
return *this;
}

And here, if this->array pointed to dynamically allocated
memory, you've leaked it (unless you're using garbage
collection).
int array_link::eek:perator<(const array_link& b) const
{
if (this->size != b.size) {
printf("array_link::eek:perator< comparing arrays (%d %d) with
different sizes: (%d) (%d)!\n", this->index, b.index, this->size,
b.size);
return 0;
}
return memcmp(this->array, b.array, sizeof(int)*this->size) <= 0;
}

This doesn't define a strict weak ordering, and so isn't an
appropriate relationship for ordering in the STL. First, of
course, you've no ordering what so ever if the sizes aren't
equal. In order for a comparison operator to be used in the
STL, the relationship !(a<b) && !(b<a) must define an
equivalence relationship; an equivalence relationship must be
transitive; yours isn't.

Second, the test for the results of memcmp should be <, and not
<=.

And finally, although it might not matter, the ordering returned
by memcmp on a sequence of int's is very arbitrary. Technically,
it's undefined, and might give different results for arrays that
you consider equal. (I don't know of a modern platform where
this is a problem, however.) Practically, the results of
comparing arrays with the same values on two different machines
will often be different, so unless the ordering is purely
arbitrary (e.g. just so the objects can be used in a set),
you're not going to get the correct results on all machines.

The simplest solution to all of these problems would be to use
std::lexicographical_compare, e.g.:

return std::lexicographical_compare(
array, array + size,
rhs.array, rhs.array + rhs.size ) ;

Of course, if you make array an std::vector, as you should, it's
just
return array < rhs.array ;
// Comparision operator for the array link
int array_link::eek:perator==(const array_link& b) const
{
if (this->size != b.size) {
printf("array_link::eek:perator== comparing arrays (%d %d) with
different sizes: (%d) (%d)!\n", this->index, b.index, this->size,
b.size);
return 0;
}
return memcmp(this->array, b.array, sizeof(int)*this->size)==0;
}

This would best be written as a single return statement, since
it is nothing but an and of two conditions:

return size == b.size
&& memcmp( array, b.array, sizeof(int)*this->size) == 0 ;

Except that memcmp is still a bit dubious, better would be:

return size == b.size
&& std::equal( array, array + size, b.array ) ;

(Especially as this is a consecrated idiom, and immediately
recognized by any experienced C++ programmer as such.)

Of course, if array is an std::vector, as it should be, then
this is just:

return array == b.array ;
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,743
Messages
2,569,478
Members
44,899
Latest member
RodneyMcAu

Latest Threads

Top