Vector insert out of range...

Hi,

I'm getting a vector insert out of range error in the given function. Parameters are:

aHaystack - a very large vector.
aReplaceAt - 1
aReplacing - {0}
aReplaceWith - {0,0}

Could you see if there is something obvious I'm missing here...

Thank you,
Uni
/*********************************************************************************
This replaces the vector aReplacing with aReplacewith at the iterator given. This
method assumes that aReplacing is valid for the aReplaceAt variable as no bounds
checking is done.
*********************************************************************************/
void replaceVectorInVector(vector<BIT> &aHaystack, const vector<BIT>::iterator &aReplaceAt, const vector<BIT> &aReplacing, const vector<BIT> &aReplaceWith){
	aHaystack.erase(aReplaceAt, aReplaceAt+aReplacing.size());
	aHaystack.insert(aReplaceAt, aReplaceWith.begin(), aReplaceWith.end());
}
/********************************************************************************/

Open in new window

LVL 3
Unimatrix_001Asked:
Who is Participating?

Improve company productivity with a Business Account.Sign Up

x
 
Infinity08Connect With a Mentor Commented:
>> invalidates the aReplaceAt iterator.

Well, that's most likely why the debug mode complains, but is the iterator ACTUALLY invalidated by it ? We're erasing after the iterator after all.

What I mean is : the debug mode complains about something that MIGHT be a problem in certain cases, but in this specific case, it shouldn't ... or am I spoiled by gcc ? The code works fine ...


>> the attached code seems to be a workaround, but a bit of a nasty one... Is it valid?

Looks good.
0
 
Infinity08Commented:
>> aReplaceAt - 1

Are you actually passing 1 as parameter ?

Or haystack.begin() + 1 ?
0
 
Unimatrix_001Author Commented:
It is being called as follows:

vector<BIT> &aHaystack;
vector<BIT>::iterator &aReplaceAt;
vector<BIT> &aReplacing;
vector<BIT> &aReplaceWith;

replaceVectorInVector(aHaystack, aReplaceAt, aReplacing, aReplaceWith);
0
Free Tool: IP Lookup

Get more info about an IP address or domain name, such as organization, abuse contacts and geolocation.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

 
Infinity08Commented:
>> vector<BIT>::iterator &aReplaceAt;

And how is it initialized ?
0
 
Unimatrix_001Author Commented:
Sorry... that's no help at all... Try again:

void myFunc(vector<BIT> &aHaystack, vector<BIT> &aLHS, vector<BIT> &aRHS){
    vector<BIT>::iterator searchFromIterator=aHaystack.begin();
    vector<BIT>::iterator foundLHSIterator=search(searchFromIterator, aHaystack.end(), aLHS.begin(), aLHS.end());
    bool result=isValidSwap(aHaystack, foundLHSIterator, aLHS, aRHS);
}

bool isValidSwap(vector<BIT> &aHaystack, vector<BIT>::iterator &aReplaceAt, vector<BIT> &aReplacing, vector<BIT> &aReplaceWith){
    replaceVectorInVector(aHaystack, aReplaceAt, aReplacing, aReplaceWith);
}
0
 
Unimatrix_001Author Commented:
...put into the code snippet for easier reading...

void myFunc(vector<BIT> &aHaystack, vector<BIT> &aLHS, vector<BIT> &aRHS){
    vector<BIT>::iterator searchFromIterator=aHaystack.begin();
    vector<BIT>::iterator foundLHSIterator=search(searchFromIterator, aHaystack.end(), aLHS.begin(), aLHS.end());
    bool result=isValidSwap(aHaystack, foundLHSIterator, aLHS, aRHS);
}
 
bool isValidSwap(vector<BIT> &aHaystack, vector<BIT>::iterator &aReplaceAt, vector<BIT> &aReplacing, vector<BIT> &aReplaceWith){
    replaceVectorInVector(aHaystack, aReplaceAt, aReplacing, aReplaceWith);
}
 
    * Accept and Award Points
    * Accept as Solution

Open in new window

0
 
Infinity08Commented:
What if the search does not find anything, and thus returns the end() iterator ?
0
 
Unimatrix_001Author Commented:
Here's my test function...
	vector<BIT> haystack;
	haystack.push_back(0);
	haystack.push_back(0);
	haystack.push_back(1);
	haystack.push_back(1);
	haystack.push_back(1);
	haystack.push_back(0);
	haystack.push_back(0);
 
	vector<BIT>::iterator replaceAt=haystack.begin();
 
	vector<BIT> replacing;
	replacing.push_back(0);
 
	vector<BIT> replaceWith;
	replaceWith.push_back(0);
	replaceWith.push_back(0);
 
	printBitIterator(haystack.begin(), haystack.end());
	replaceVectorInVector(haystack, replaceAt, replacing, replaceWith);
	printBitIterator(haystack.begin(), haystack.end());

Open in new window

0
 
Unimatrix_001Author Commented:
>>What if the search does not find anything, and thus returns the end() iterator ?
That is already handled in some code between the search and the call to isValidSwap. Although as the test function shows, this doesn't seem to be where the problem lies.
0
 
Unimatrix_001Author Commented:
BIT==typedef BIT char;
0
 
Infinity08Commented:
>> That is already handled in some code between the search and the call to isValidSwap.

Not in the code you posted ;)


Did you mean to use an isValidSwap like this ?
bool isValidSwap(vector<BIT> &aHaystack, vector<BIT>::iterator &aReplaceAt, vector<BIT> &aReplacing, vector<BIT> &aReplaceWith){
  if (aReplaceAt != aHaystack.end()) {
    replaceVectorInVector(aHaystack, aReplaceAt, aReplacing, aReplaceWith);
    return true;
  }
  else {
    return false;
  }
}

Open in new window

0
 
Infinity08Commented:
>> Not in the code you posted ;)

In case the actual code is different, it might be interesting to see the actual code - ie. a complete code sample that reproduces the problem.
0
 
Unimatrix_001Author Commented:
Hi Infinity...

Ignore the isValidSwap etc. for now, since the problem can be replicated using the test function above. I've put all the relevant code below...
/********************************************************************************/
int main(){
 
	vector<BIT> haystack;
	haystack.push_back(0);
	haystack.push_back(0);
	haystack.push_back(1);
	haystack.push_back(1);
	haystack.push_back(1);
	haystack.push_back(0);
	haystack.push_back(0);
 
	vector<BIT>::iterator replaceAt=haystack.begin();
 
	vector<BIT> replacing;
	replacing.push_back(0);
 
	vector<BIT> replaceWith;
	replaceWith.push_back(0);
	replaceWith.push_back(0);
 
	printBitIterator(haystack.begin(), haystack.end());
	replaceVectorInVector(haystack, replaceAt, replacing, replaceWith);
	printBitIterator(haystack.begin(), haystack.end());
 
	return 0;
}
/********************************************************************************/
 
 
/*********************************************************************************
This replaces the vector aReplacing with aReplacewith at the iterator given. This
method assumes that aReplacing is valid for the aReplaceAt variable as no bounds
checking is done.
*********************************************************************************/
void replaceVectorInVector(vector<BIT> &aHaystack, const vector<BIT>::iterator &aReplaceAt, const vector<BIT> &aReplacing, const vector<BIT> &aReplaceWith){
	aHaystack.erase(aReplaceAt, aReplaceAt+aReplacing.size());
	aHaystack.insert(aReplaceAt, aReplaceWith.begin(), aReplaceWith.end());
}
/********************************************************************************/

Open in new window

0
 
Infinity08Commented:
That code works fine for me ...
0
 
Infinity08Commented:
Unless the problem is in printBitIterator ?
0
 
Unimatrix_001Author Commented:
I've commented them out with still the error there. The exact error is: Ack... why can't they make the text selectable... See the pic.

=======================================================
Debug assertion failed
File: \vc\include\vector
Line: 932
Expression: vector insert iterator outside range
=======================================================
{ text description added by PenguinMod, EE Moderator, per http:/Q_23488224.html, and attachment removed. }
0
 
Unimatrix_001Author Commented:
>>That code works fine for me ...
Gulp... That's not good, the exact same two functions fail with me!
0
 
Unimatrix_001Author Commented:
Okay, after a bit of testing - it looks to be the aReplaceAt that it's choking on, since this works fine.

Hold up, just had a thought, if I erase aReplaceAt to aReplaceAt+aReplacing.size(), won't this then invalidate the aReplaceAt iterator meaning I can't insert at it?
aHaystack.erase(aReplaceAt, aReplaceAt+aReplacing.size());
aHaystack.insert(aHaystack.begin(), aReplaceWith.begin(), aReplaceWith.end());

Open in new window

0
 
evilrixSenior Software Engineer (Avast)Commented:
0
 
Infinity08Commented:
>> Hold up, just had a thought, if I erase aReplaceAt to aReplaceAt+aReplacing.size(), won't this then invalidate the aReplaceAt iterator meaning I can't insert at it?

aReplaceAt+aReplacing.size() will give you an iterator that is aReplacing.size() positions past aReplaceAt.
Since aReplacing.size() is only 1, and aReplaceAt is the begin() of the haystack, and the haystack is large enough, there should be no problem.


>> The exact error is: Ack... why can't they make the text selectable... See the pic.

Maybe we're missing something small. Can you post the complete file you used to get this result ? Just so I work with the exact same code here ...
0
 
Unimatrix_001Author Commented:
Here we go... I've just noticed something strange - this seems to work in release mode, but in debug mode is where the error is? I've only just noticed as I always run in debug until I'm ready...
/****************************************************************************/
#include <algorithm>
#include <fstream>
#include <iostream>
#include <math.h>
#include <ostream>
#include <string>
#include <vector>
using namespace std;
/****************************************************************************/
 
 
/****************************************************************************/
typedef char BIT;
/****************************************************************************/
 
 
/*********************************************************************************
Main entry point.
*********************************************************************************/
int main();
/********************************************************************************/
 
 
/*********************************************************************************
This replaces the vector aReplacing with aReplacewith at the iterator given. This
method assumes that aReplacing is valid for the aReplaceAt variable as no bounds
checking is done.
*********************************************************************************/
void replaceVectorInVector(vector<BIT> &aHaystack, const vector<BIT>::iterator &aReplaceAt, const vector<BIT> &aReplacing, const vector<BIT> &aReplaceWith);
/********************************************************************************/
 
 
/*********************************************************************************
Prints the vector from the start up to and including the end.
*********************************************************************************/
void printBitIterator(const vector<BIT>::iterator &aStart, const vector<BIT>::iterator &aEnd);
/********************************************************************************/
 
 
/*********************************************************************************
Main entry point.
*********************************************************************************/
int main(){
 
	vector<BIT> haystack;
	haystack.push_back(1);
	haystack.push_back(0);
	haystack.push_back(1);
	haystack.push_back(1);
	haystack.push_back(1);
	haystack.push_back(0);
	haystack.push_back(0);
 
	vector<BIT>::iterator replaceAt=haystack.begin();
 
	vector<BIT> replacing;
	replacing.push_back(0);
 
	vector<BIT> replaceWith;
	replaceWith.push_back(0);
	replaceWith.push_back(0);
 
	printBitIterator(haystack.begin(), haystack.end()); cout<<endl;
	replaceVectorInVector(haystack, replaceAt, replacing, replaceWith);
	printBitIterator(haystack.begin(), haystack.end()); cout<<endl;
 
	return 0;
}
/********************************************************************************/
 
 
/*********************************************************************************
This replaces the vector aReplacing with aReplacewith at the iterator given. This
method assumes that aReplacing is valid for the aReplaceAt variable as no bounds
checking is done.
*********************************************************************************/
void replaceVectorInVector(vector<BIT> &aHaystack, const vector<BIT>::iterator &aReplaceAt, const vector<BIT> &aReplacing, const vector<BIT> &aReplaceWith){
	aHaystack.erase(aReplaceAt, aReplaceAt+aReplacing.size());
	aHaystack.insert(aReplaceAt, aReplaceWith.begin(), aReplaceWith.end());
}
/********************************************************************************/
 
 
/*********************************************************************************
Prints the vector from the start up to and including the end.
*********************************************************************************/
void printBitIterator(const vector<BIT>::iterator &aStart, const vector<BIT>::iterator &aEnd){
	vector<BIT>::iterator currentIterator=aStart;
	while(currentIterator!=aEnd)
		cout<<(int)currentIterator++[0];
}
/********************************************************************************/

Open in new window

0
 
evilrixSenior Software Engineer (Avast)Commented:
I'm pretty sure that bounds are checked in debug but not release.
http://msdn.microsoft.com/en-us/library/aa985982(VS.80).aspx

"The Visual C++ runtime library now detects incorrect iterator use and will assert and display a dialog box at run time. To enable debug iterator support, a program must be compiled with a debug version of a C run time library..."
0
 
Infinity08Commented:
Since the error seems to point to the insert operation, can you add these lines, and see what output you get ?
void replaceVectorInVector(vector<BIT> &aHaystack, const vector<BIT>::iterator &aReplaceAt, const vector<BIT> &aReplacing, const vector<BIT> &aReplaceWith){
        std::cerr << (aReplaceAt - aHaystack.begin()) << std::endl;   // <---
        aHaystack.erase(aReplaceAt, aReplaceAt+aReplacing.size());
        std::cerr << (aReplaceAt - aHaystack.begin()) << std::endl;   // <---
        aHaystack.insert(aReplaceAt, aReplaceWith.begin(), aReplaceWith.end());
        std::cerr << (aReplaceAt - aHaystack.begin()) << std::endl;   // <---
}

Open in new window

0
 
Unimatrix_001Author Commented:
This is strange, because in release I get the correct result, but in debug I get an error...
0
 
Unimatrix_001Author Commented:
In debug mode it prints:
0
Then I get an error:
Vector Iterators Incompatible

In release mode it prints:
0
0
0
0
 
evilrixSenior Software Engineer (Avast)Commented:
>> This is strange, because in release I get the correct result, but in debug I get an error...
The debug error tells me that although you see the correct result in release this is probably by luck than design -- remember, accessing out of bounds means you are taking a swim in the lake of undefined behavior with very skimpy trunks on and lots of sharks waiting to bite you when you least expect it (have I gone too far now maybe?) :)
0
 
Unimatrix_001Author Commented:
>>remember, accessing out of bounds means you are taking a swim in the lake of undefined behavior with very skimpy trunks on and lots of sharks waiting to bite you when you least expect it (have I gone too far now maybe?) :)
Hehe, your analogies are getting more and more exotic! :D Thing is, I'm not accessing anything out of bounds.
0
 
Infinity08Commented:
Can you spot anything wrong in the code evilrix ? Did you run it ?
0
 
evilrixSenior Software Engineer (Avast)Commented:
This line...

      aHaystack.erase(aReplaceAt, aReplaceAt+aReplacing.size());

invalidates the aReplaceAt iterator.

Change the next line from this...

      aHaystack.insert(aReplaceAt, aReplaceWith.begin(), aReplaceWith.end());

To this...

      aHaystack.insert(aHaystack.begin(), aReplaceWith.begin(), aReplaceWith.end());

and it no longer errors.
0
 
Unimatrix_001Author Commented:
>>and it no longer errors.
I beat you to that one my friend:

http://www.experts-exchange.com/Programming/Languages/CPP/Q_23487955.html#a21793698

;) Is there a way I can get this function working then without resorting to having to pass in an unsigned int instead of the iterator... Maybe a way to find out where the iterator is and recalculate it after the erase?
0
 
Unimatrix_001Author Commented:
Hi there lads, the attached code seems to be a workaround, but a bit of a nasty one... Is it valid?
vector<BIT>::iterator temp=aReplaceAt;
unsigned int difference=aReplaceAt-aHaystack.begin();
aHaystack.erase(aReplaceAt, aReplaceAt+aReplacing.size());	
aHaystack.insert(aHaystack.begin()+difference, aReplaceWith.begin(), aReplaceWith.end());

Open in new window

0
 
Unimatrix_001Author Commented:
>>or am I spoiled by gcc
I think so, I'm running VS2K8 here...
0
 
Unimatrix_001Author Commented:
Thank you. :)
0
 
Infinity08Commented:
>> or am I spoiled by gcc ? The code works fine ...

To clarify, I'm just trying to figure out if the debug mode actually noticed an out-of-bounds access (and if so, why ?), or if it just complains because the code seems to match a few general criteria.
0
 
evilrixSenior Software Engineer (Avast)Commented:
>> To clarify, I'm just trying to figure out if the debug mode actually noticed an out-of-bounds access
http://www.cplusplus.com/reference/stl/vector/erase.html
"This invalidates all iterator and references to elements ***after*** position or first."

Implies the aReplaceAt should still be valid IMHO.

Sorry for not posting back sooner, I had to leave work :)
0
 
Infinity08Commented:
>> Implies the aReplaceAt should still be valid IMHO.

I know that, evilrix. That's why I'm mystified about the debugger's complaints ... I wonder why it does that.
0
 
evilrixSenior Software Engineer (Avast)Commented:
>> I know that, evilrix.
I was agreeing with you :)

>> That's why I'm mystified about the debugger's complaints ... I wonder why it does that.
I've not taken time to look at it in detail yet (I'm a bit bust ATM), but below is what triggers the assert. It seems to think it's outside the valid range.
	template<class _Iter>
		void _Insert(iterator _Where,
			_Iter _First, _Iter _Last, forward_iterator_tag)
		{	// insert [_First, _Last) at _Where, forward iterators
 
 #if _HAS_ITERATOR_DEBUGGING
		if (_Where._Mycont != this
			|| _Where._Myptr < _Myfirst || _Mylast < _Where._Myptr)
			_DEBUG_ERROR("vector insert iterator outside range");      // <----- FIRES HERE
		_DEBUG_RANGE(_First, _Last);
		if (_Debug_get_cont(_First) == this)
			_DEBUG_ERROR("vector insertion overlaps range");
 #endif /* _HAS_ITERATOR_DEBUGGING */
....
}

Open in new window

0
 
evilrixSenior Software Engineer (Avast)Commented:
s/bust/busy :)
0
 
evilrixSenior Software Engineer (Avast)Commented:
have you tried doing this....?

The erase method returns "a random access iterator pointing to the new location of the element that followed the last element erased by the function call, which is the vector end if the operation erased the last element in the sequence".

I should have thought of this yesterday, but I was somewhat distracted by events happening around me.

void replaceVectorInVector(vector<BIT> &aHaystack, const vector<BIT>::iterator &aReplaceAt, const vector<BIT> &aReplacing, const vector<BIT> &aReplaceWith){
	vector<BIT>::iterator tmp = aHaystack.erase(aReplaceAt, aReplaceAt+aReplacing.size());
	aHaystack.insert(tmp, aReplaceWith.begin(), aReplaceWith.end());
}

Open in new window

0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.