Re: problem with C++ stl (deque and vector)
On Dec 24, 4:22 pm, pieter.eende...@gmail.com wrote:
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[s];
for(int i=0;i<size;i++)
array[i]=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.)
More likely, what you really want is std::vector<int> array in
array_link, so you don't have to worry about it.
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", coun=
t);
}
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::operator=(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::operator<(const array_link& b) const
{
if (this->size != b.size) {
printf("array_link::operator< comparing arrays (%d %d) wi=
th
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::operator==(const array_link& b) const
{
if (this->size != b.size) {
printf("array_link::operator== 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 ;
--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orient=E9e objet/
Beratung in objektorientierter Datenverarbeitung
9 place S=E9mard, 78210 St.-Cyr-l'=C9cole, France, +33 (0)1 30 23 00 34