Solved

Vector insert out of range...

Posted on 2008-06-16
39
1,242 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
ID: 21793258
>> aReplaceAt - 1

Are you actually passing 1 as parameter ?

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

Author Comment

by:Unimatrix_001
ID: 21793271
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
ID: 21793281
>> vector<BIT>::iterator &aReplaceAt;

And how is it initialized ?
0
PRTG Network Monitor: Intuitive Network Monitoring

Network Monitoring is essential to ensure that computer systems and network devices are running. Use PRTG to monitor LANs, servers, websites, applications and devices, bandwidth, virtual environments, remote systems, IoT, and many more. PRTG is easy to set up & use.

 
LVL 3

Author Comment

by:Unimatrix_001
ID: 21793294
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
ID: 21793297
...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
ID: 21793360
What if the search does not find anything, and thus returns the end() iterator ?
0
 
LVL 3

Author Comment

by:Unimatrix_001
ID: 21793363
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
ID: 21793375
>>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
ID: 21793383
BIT==typedef BIT char;
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 21793419
>> 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
ID: 21793424
>> 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
ID: 21793445
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
ID: 21793499
That code works fine for me ...
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 21793500
Unless the problem is in printBitIterator ?
0
 
LVL 3

Author Comment

by:Unimatrix_001
ID: 21793568
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
ID: 21793589
>>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
ID: 21793698
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
ID: 21793765
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 21793775
>> 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
 
LVL 3

Author Comment

by:Unimatrix_001
ID: 21793841
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
ID: 21793897
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
ID: 21793910
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
ID: 21793919
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
ID: 21793942
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
ID: 21793952
>> 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
ID: 21793989
>>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
ID: 21794037
Can you spot anything wrong in the code evilrix ? Did you run it ?
0
 
LVL 40

Expert Comment

by:evilrix
ID: 21794104
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
ID: 21794131
>>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
ID: 21794258
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
ID: 21794331
>> 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
ID: 21794350
>>or am I spoiled by gcc
I think so, I'm running VS2K8 here...
0
 
LVL 3

Author Comment

by:Unimatrix_001
ID: 21794357
Thank you. :)
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 21794365
>> 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
ID: 21795828
>> 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
ID: 21795938
>> 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
ID: 21796017
>> 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
ID: 21796020
s/bust/busy :)
0
 
LVL 40

Expert Comment

by:evilrix
ID: 21801448
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

NAS Cloud Backup Strategies

This article explains backup scenarios when using network storage. We review the so-called “3-2-1 strategy” and summarize the methods you can use to send NAS data to the cloud

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
Move constructor only called if marked noexcept? 6 104
GUI: DIalog Stacking and Popping in MS C++ 4 76
Dialogbox API leak? 18 96
Which Linux flavors will this run on? 6 88
Often, when implementing a feature, you won't know how certain events should be handled at the point where they occur and you'd rather defer to the user of your function or class. For example, a XML parser will extract a tag from the source code, wh…
Many modern programming languages support the concept of a property -- a class member that combines characteristics of both a data member and a method.  These are sometimes called "smart fields" because you can add logic that is applied automaticall…
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

777 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