Solved

Vector insert out of range...

Posted on 2008-06-16
39
1,227 Views
Last Modified: 2008-06-17
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

0
Comment
Question by:Unimatrix_001
  • 18
  • 13
  • 8
39 Comments
 
LVL 53

Expert Comment

by:Infinity08
Comment Utility
>> aReplaceAt - 1

Are you actually passing 1 as parameter ?

Or haystack.begin() + 1 ?
0
 
LVL 3

Author Comment

by:Unimatrix_001
Comment Utility
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
 
LVL 53

Expert Comment

by:Infinity08
Comment Utility
>> vector<BIT>::iterator &aReplaceAt;

And how is it initialized ?
0
 
LVL 3

Author Comment

by:Unimatrix_001
Comment Utility
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
 
LVL 3

Author Comment

by:Unimatrix_001
Comment Utility
...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
 
LVL 53

Expert Comment

by:Infinity08
Comment Utility
What if the search does not find anything, and thus returns the end() iterator ?
0
 
LVL 3

Author Comment

by:Unimatrix_001
Comment Utility
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
 
LVL 3

Author Comment

by:Unimatrix_001
Comment Utility
>>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
 
LVL 3

Author Comment

by:Unimatrix_001
Comment Utility
BIT==typedef BIT char;
0
 
LVL 53

Expert Comment

by:Infinity08
Comment Utility
>> 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
 
LVL 53

Expert Comment

by:Infinity08
Comment Utility
>> 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
 
LVL 3

Author Comment

by:Unimatrix_001
Comment Utility
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
 
LVL 53

Expert Comment

by:Infinity08
Comment Utility
That code works fine for me ...
0
 
LVL 53

Expert Comment

by:Infinity08
Comment Utility
Unless the problem is in printBitIterator ?
0
 
LVL 3

Author Comment

by:Unimatrix_001
Comment Utility
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
 
LVL 3

Author Comment

by:Unimatrix_001
Comment Utility
>>That code works fine for me ...
Gulp... That's not good, the exact same two functions fail with me!
0
 
LVL 3

Author Comment

by:Unimatrix_001
Comment Utility
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
 
LVL 40

Expert Comment

by:evilrix
Comment Utility
0
 
LVL 53

Expert Comment

by:Infinity08
Comment Utility
>> 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
IT, Stop Being Called Into Every Meeting

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

 
LVL 3

Author Comment

by:Unimatrix_001
Comment Utility
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
 
LVL 40

Expert Comment

by:evilrix
Comment Utility
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
 
LVL 53

Expert Comment

by:Infinity08
Comment Utility
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
 
LVL 3

Author Comment

by:Unimatrix_001
Comment Utility
This is strange, because in release I get the correct result, but in debug I get an error...
0
 
LVL 3

Author Comment

by:Unimatrix_001
Comment Utility
In debug mode it prints:
0
Then I get an error:
Vector Iterators Incompatible

In release mode it prints:
0
0
0
0
 
LVL 40

Expert Comment

by:evilrix
Comment Utility
>> 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
 
LVL 3

Author Comment

by:Unimatrix_001
Comment Utility
>>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
 
LVL 53

Expert Comment

by:Infinity08
Comment Utility
Can you spot anything wrong in the code evilrix ? Did you run it ?
0
 
LVL 40

Expert Comment

by:evilrix
Comment Utility
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
 
LVL 3

Author Comment

by:Unimatrix_001
Comment Utility
>>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
 
LVL 3

Author Comment

by:Unimatrix_001
Comment Utility
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
 
LVL 53

Accepted Solution

by:
Infinity08 earned 500 total points
Comment Utility
>> 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
 
LVL 3

Author Comment

by:Unimatrix_001
Comment Utility
>>or am I spoiled by gcc
I think so, I'm running VS2K8 here...
0
 
LVL 3

Author Comment

by:Unimatrix_001
Comment Utility
Thank you. :)
0
 
LVL 53

Expert Comment

by:Infinity08
Comment Utility
>> 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
 
LVL 40

Expert Comment

by:evilrix
Comment Utility
>> 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
 
LVL 53

Expert Comment

by:Infinity08
Comment Utility
>> 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
 
LVL 40

Expert Comment

by:evilrix
Comment Utility
>> 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
 
LVL 40

Expert Comment

by:evilrix
Comment Utility
s/bust/busy :)
0
 
LVL 40

Expert Comment

by:evilrix
Comment Utility
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

Featured Post

How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

Join & Write a Comment

Suggested Solutions

When writing generic code, using template meta-programming techniques, it is sometimes useful to know if a type is convertible to another type. A good example of when this might be is if you are writing diagnostic instrumentation for code to generat…
Errors will happen. It is a fact of life for the programmer. How and when errors are detected have a great impact on quality and cost of a product. It is better to detect errors at compile time, when possible and practical. Errors that make their wa…
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

728 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

9 Experts available now in Live!

Get 1:1 Help Now