access violation question

[Thomas]

Any hints on the following issue?

I wrote a fairly small program which typically runs for seconds up to a
minute or so, going through the code millions of times, then produces an
access violation message.

I am fairly sure that the program code does not overstep vector
boundaries. I haven't declared any pointer type variables directly. The
program never uses more than a couple (3 or 4) MB of memory.

The Borland compiler locates the problem in the line

swap (vtemp[x], vtemp[y]);

When I replace the swap function by my own 3-line routine with a temp
variable, the same thing happens.

When I "guard" the swapping by writing

if (x < vtemp.size() && y < vtemp.size())
swap (vtemp[x], vtemp[y]);

an access violation message is produced by the harmless-looking line

while (vint[0] != 1)

All help appreciated.

T.

 

[AnonMail2005]

Any hints on the following issue?

I wrote a fairly small program which typically runs for seconds up to a
minute or so, going through the code millions of times, then produces an
access violation message.

I am fairly sure that the program code does not overstep vector
boundaries. I haven't declared any pointer type variables directly. The
program never uses more than a couple (3 or 4) MB of memory.

The Borland compiler locates the problem in the line

swap (vtemp[x], vtemp[y]);

When I replace the swap function by my own 3-line routine with a temp
variable, the same thing happens.

When I "guard" the swapping by writing

if (x < vtemp.size() && y < vtemp.size())
    swap (vtemp[x], vtemp[y]);

an access violation message is produced by the harmless-looking line

while (vint[0] != 1)

All help appreciated.

T.

Please post your code.

 

[Thomas]

Please post your code.

Here is the code, that will compile on Codeblocks (gcc compiler), but
leads to an error during execution.

I removed most comments (in Dutch), all ofstream (output to file) parts
(so some of the code must seem pointless now), and I englished some
variable names. I used an input function rather than arguments to
main(), so I could give some suggestions about the input values.
Comments on the miserable coding are welcome, but that's not MY first
concern at the moment.

--------------------------------------------------------------

#include <iostream>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <ctime>

using namespace std;

unsigned int n, hoogste = 0, trnsize, nr_rows, nr_trns,
wissels, rounds;
double poolgem, pooltop, mutatiegraad;
typedef pair < vector<unsigned int>,unsigned int > paar;
vector<paar>vpool;
vector<pair <unsigned int,unsigned int> > vparen;

// rng used in random_shuffle()
class MyRandom // from Josuttis, p. 393-5
{
public:
ptrdiff_t operator() (ptrdiff_t max)
{
double tmp;
tmp = static_cast<double>(rand())
/ static_cast<double>(RAND_MAX);
return static_cast<ptrdiff_t>(tmp * max);
}
};
MyRandom rd;

inline bool groter (const paar& paar1, const paar& paar2)
{
return paar1.second > paar2.second;
}

inline unsigned int terugtel (vector<unsigned int>& vint)
{
unsigned int terugtel = 0, vangst = 0;
while (terugtel != vint.size())
{
terugtel++;
if (vint[terugtel] == terugtel + 1)
{
reverse (vint.begin(), vint.begin()+terugtel+1);
terugtel = 0;
++vangst;
}
}
return vangst;
}

inline unsigned int rvrs (vector<unsigned int> vint)
{
unsigned int teller = 0;
while (vint[0] != 1)
{
teller++;
reverse (vint.begin(), vint.begin()+vint[0]);
}
return teller;
}

void toon_hoogste (const vector<unsigned int>& vi)
{
cout << hoogste << " - ronde " << rounds << endl;
vector<unsigned int> vidup(n);
copy (vi.begin(), vi.end(), vidup.begin());
unsigned int bijtellen = terugtel (vidup);
}

void toon_pooltop ()
{
cout << "round " << rounds << ", average " << pooltop
<< endl;
}

double poolgemiddelde ()
{
double pooltotaal = 0.0;
for (unsigned int i = 0; i != nr_rows; ++i)
pooltotaal += vpool.second;
return pooltotaal / nr_rows;
}

void verwissel (const unsigned int index)
{
unsigned int score, x, y, hulpwaarde;
double klein;

vector<paar> vtrn(trnsize);
copy (vpool.begin()+index, vpool.begin()+index+trnsize,
vtrn.begin());

sort (vtrn.begin(), vtrn.end(), groter);

vector<paar> vkand_trn;
for (unsigned int deeln = 0; deeln != trnsize; ++deeln)
{
random_shuffle (vparen.begin(), vparen.end(), rd);
vector<paar> vkand_ouder;
for (unsigned int wisnr = 0; wisnr != wissels; ++wisnr)
{
vector<unsigned int> vtemp = vtrn[deeln].first;

x = vparen[wisnr].first;
y = vparen[wisnr].second;
swap (vtemp[x], vtemp[y]);
// if (x < vtemp.size() && y < vtemp.size())
// swap (vtemp[x], vtemp[y]);

score = rvrs(vtemp);
if (score > hoogste)
{
hoogste = score;
toon_hoogste (vtemp);
}

vkand_ouder.push_back(make_pair(vtemp,score));
}

sort (vkand_ouder.begin(), vkand_ouder.end(), groter);
for (unsigned int i = 0; i != 2; ++i)
vkand_trn.push_back(vkand_ouder);
}

sort (vkand_trn.begin(), vkand_trn.end(), groter);
copy (vkand_trn.begin(),
vkand_trn.begin()+trnsize,
vpool.begin()+index);
}

void initialiseer_pool()
{
vector<unsigned int> row(n);
nr_rows = nr_trns * trnsize;
unsigned int score;
for (unsigned int i = 0; i != n; ++i)
row = i+1;
for (unsigned int i = 0; i != nr_rows; ++i)
{
do
{
random_shuffle (row.begin(), row.end(),rd);
}
while (row[0] == 1 || row[row[0]-1] == 1);

score = rvrs(row);
if (score > hoogste)
{
hoogste = score;
toon_hoogste (row);
}
vpool.push_back(make_pair (row,score) );
}
poolgem = poolgemiddelde();
if (poolgem > pooltop)
{
pooltop = poolgem;
toon_pooltop();
}
}

void gegevensinvoer()
{
cout << "\n\nSettings like ...\n\n";
cout << "n = 20\n";
cout << "trnsize = 4\n";
cout << "nr_trns = 100\n";
cout << "prt = 15\n\n";
cout << "... will cause the program to stop,\n";
cout << "however the round in which this happens\n";
cout << "may as well be round 0 as 200.\n\n";
cout << "n (10-100): ";
cin >> n;
cout << endl << endl;
cout << "trnsize (to be safe, choose 4): ";
cin >> trnsize;
cout << endl << endl;
cout << "nr_trns (couple hundred): ";
cin >> nr_trns;
cout << endl << endl;
unsigned int alle_wissels = n * (n-1) / 2;
double prt;
cout << "prt (a lowish percentage): ";
cin >> prt;
wissels = static_cast<unsigned int>(prt * alle_wissels / 100.0);
cout << endl << endl;
}

int main()
{
srand(time(0));
gegevensinvoer();
// initialize vparen
for (int unsigned i = 0; i != n - 1; ++i)
for (int unsigned j = i + 1; j != n; ++j)
{
pair<unsigned int,unsigned int> p (i,j);
vparen.push_back(p);
}
rounds = 0;
pooltop = 0.0;
initialiseer_pool();

while (true)
{
rounds++;
cout << '=' << rounds << "=\n";
for (unsigned int i = 0; i != nr_trns; ++i)
verwissel (i*trnsize);
poolgem = poolgemiddelde();
if (poolgem > pooltop)
{
pooltop = poolgem;
toon_pooltop ();
}
for (unsigned int schud = 0; schud != nr_rows; ++schud)
random_shuffle (vpool.begin(), vpool.end(),rd);
}

return 0;
}

 

[Thomas]

On 27-12-2010 18:36, Daniel T. wrote:

....

Thanks AnonMail, Paavo Helde and Daniel T. for your replies. Daniel, I
saw your post only after I had posted my code. I am going to study it now.

 

[Ian Collins]

Here is the code, that will compile on Codeblocks (gcc compiler), but
leads to an error during execution.

First error seems to be in the function terugtel():

while (terugtel != vint.size())
{
terugtel++;
if (vint[terugtel] == terugtel + 1)

Here terugtel becomes equal to vint.size() eventually, thus vint
[terugtel] is illegal.

This was easily catched by MSVC++2010 Debug mode build, BTW.

You pipped me to the post! Also easily spotted by Solaris dbx.

Thomas, you should find your self a decent debugger!

 

[Thomas]

On 27-12-2010 17:49, (e-mail address removed) wrote:

Please post your code.

Here is the code, that will compile on Codeblocks (gcc compiler), but
leads to an error during execution.

First error seems to be in the function terugtel():

while (terugtel != vint.size())
{
terugtel++;
if (vint[terugtel] == terugtel + 1)

Here terugtel becomes equal to vint.size() eventually, thus vint
[terugtel] is illegal.

This was easily catched by MSVC++2010 Debug mode build, BTW.

You pipped me to the post! Also easily spotted by Solaris dbx.

Thomas, you should find your self a decent debugger!

As it happens, this problem doesn't arise, because the vector<int>s with
length n in this program are by definition filled with permutations of
the integer range [1..n] (not [0..n-1]). The terugtel() function worked
fine in all previous programs that used it.

 

[Ian Collins]

On 27-12-2010 17:49, (e-mail address removed) wrote:

Please post your code.

Here is the code, that will compile on Codeblocks (gcc compiler), but
leads to an error during execution.

First error seems to be in the function terugtel():

while (terugtel != vint.size())
{
terugtel++;
if (vint[terugtel] == terugtel + 1)

Here terugtel becomes equal to vint.size() eventually, thus vint
[terugtel] is illegal.

This was easily catched by MSVC++2010 Debug mode build, BTW.

You pipped me to the post! Also easily spotted by Solaris dbx.

Thomas, you should find your self a decent debugger!

As it happens, this problem doesn't arise, because the vector<int>s with
length n in this program are by definition filled with permutations of
the integer range [1..n] (not [0..n-1]). The terugtel() function worked
fine in all previous programs that used it.

For some definition of "worked". You are comparing an unallocated bit
of memory, so your results are random.

if (vint[terugtel] == terugtel + 1)
{
reverse (vint.begin(), vint.begin()+terugtel+1);

What happens if the comparison is true? Look at the parameters to
reverse. My guess is your program crashes at some random number of
passes, correct?

 

[Thomas]

For some definition of "worked". You are comparing an unallocated bit of
memory, so your results are random.

if (vint[terugtel] == terugtel + 1)
{
reverse (vint.begin(), vint.begin()+terugtel+1);

What happens if the comparison is true? Look at the parameters to
reverse. My guess is your program crashes at some random number of
passes, correct?

Thanks, by the way, for your replies, Ian.

Yes, the crash moment cannot be predicted.
I just commented out the terugtel() function, as well as the reference
to it, out (it's rather marginal, nothing depends on it), and the
program still crashed (first time in round 174, second time in 16).

 

[Jim Langston]

On 27-12-2010 17:49, (e-mail address removed) wrote:

Please post your code.

Here is the code, that will compile on Codeblocks (gcc compiler), but
leads to an error during execution.

First error seems to be in the function terugtel():

while (terugtel != vint.size())
{
terugtel++;
if (vint[terugtel] == terugtel + 1)

Here terugtel becomes equal to vint.size() eventually, thus vint
[terugtel] is illegal.

This was easily catched by MSVC++2010 Debug mode build, BTW.

You pipped me to the post! Also easily spotted by Solaris dbx.

Thomas, you should find your self a decent debugger!

As it happens, this problem doesn't arise, because the vector<int>s with
length n in this program are by definition filled with permutations of the
integer range [1..n] (not [0..n-1]). The terugtel() function worked fine
in all previous programs that used it.

All *previous* programs that use it. I get an error in the code
inline unsigned int terugtel (vector<unsigned int>& vint)
{
unsigned int terugtel = 0, vangst = 0;
while (terugtel != vint.size())
{
terugtel++;
if (vint[terugtel] == terugtel + 1)
{
reverse (vint.begin(), vint.begin()+terugtel+1);
terugtel = 0;
++vangst;
}
}
return vangst;
}
reverse (vint.begin(), vint.begin()+terugtel+1);

terugtel is currently 18. The vint size is 20. Where is vint.begin() +
terugtel + 1 going to point to? Which element in the 20 element vint?
Oops. 18 + 20 + 1 = 40. So it's going to point to the 40th element in the
array. This may have worked for you in the past in other programs, but
it's not working now. You need to ensure that you do go past .end() which
is expected. The confusion comes in when you mix iterators (begin()) with
array counters (terugtel) you have to do your own manual checking to make
sure "they" (the pointer/iterator you are going to use) is within bounds.

It does not always break, of course, just sometimes when it's working toward
the end of the array. You need to fix your logic.

Incidently, it's very bad to have a function name with the same name as a
variable name. Your function name is terugtel and your variable is
terugtel. *shudder* I am not positive that terugtel + 1 represents the
variable + 1 or the address off the function + 1. If you must, give your
function names a capital letter. This wouldn't compile in C because of the
name clash, but it does in C++ becaue of name mangaling I believe. Still
ugly as sin.



on the line

 

[Thomas]

All *previous* programs that use it. I get an error in the code
inline unsigned int terugtel (vector<unsigned int>& vint)
{
unsigned int terugtel = 0, vangst = 0;
while (terugtel != vint.size())
{
terugtel++;
if (vint[terugtel] == terugtel + 1)
{
reverse (vint.begin(), vint.begin()+terugtel+1);
terugtel = 0;
++vangst;
}
}
return vangst;
}
reverse (vint.begin(), vint.begin()+terugtel+1);

terugtel is currently 18. The vint size is 20. Where is vint.begin() +
terugtel + 1 going to point to? Which element in the 20 element vint?
Oops. 18 + 20 + 1 = 40. So it's going to point to the 40th element in
the array. This may have worked for you in the past in other programs,
but it's not working now. You need to ensure that you do go past .end()
which is expected. The confusion comes in when you mix iterators
(begin()) with array counters (terugtel) you have to do your own manual
checking to make sure "they" (the pointer/iterator you are going to use)
is within bounds.

It does not always break, of course, just sometimes when it's working
toward the end of the array. You need to fix your logic.

Incidently, it's very bad to have a function name with the same name as
a variable name. Your function name is terugtel and your variable is
terugtel. *shudder* I am not positive that terugtel + 1 represents the
variable + 1 or the address off the function + 1. If you must, give your
function names a capital letter. This wouldn't compile in C because of
the name clash, but it does in C++ becaue of name mangaling I believe.
Still ugly as sin.

Thanks Jim and others for alerting me to the faultiness of the
terugtel() function. I now realize that from the fact that it didn't
crash previous programs, it doesn't follow that it's correct code.

 

[Thomas]

Any hints on the following issue?
...

I am rebuilding the program from scratch, now with a (hopefully) correct
terugtel() function.
Something peculiar happened. The program accepts the version of
random_shuffle() with two parameters (using the built-in prng, gcc
compiler), but it invariably crashes within 100,000 calls when I use an
adaptation borrowed from Josuttis:

class MyRandom // from Josuttis, p. 393-5
{
public:
ptrdiff_t operator() (ptrdiff_t max)
{
double tmp;
tmp = static_cast<double>(rand())
/ static_cast<double>(RAND_MAX);
return static_cast<ptrdiff_t>(tmp * max);
}
};
MyRandom rd;

random_shuffle (row.begin(), row.end(), rd);

I have no idea why this happens.

T.

 

[James Kanze]

(double) rand() / RAND_MAX is occasionally 1.0 which means your index
will occasionally be one past the end of the sequence (presumably).

Good point. And a hard one to guard against: (double)rand()
/ (RAND_MAX + 1) is the obvious fix. Except that RAND_MAX can
be equal to INT_MAX.

A better solution is simply "return rand() % max;", which
guarantees a value in the half open interval [0...max).

Both solutions also suffer from a more or less large bias in
favor of some values. If max is small, the bias is also small,
and it may be acceptable to ignore it. If max is RAND_MAX,
however, one value gets chosen twice as often as the others.
(There's also the question of what happens when max is greater
than RAND_MAX. For some strange reason, a number of systems set
RAND_MAX to 32767. Which really isn't very big.)