vector<...>::iterators and insert - I'm stumped.

[Dino]

Hey y'all. First post here in the C++ section.

I'm working on a commission for a client, and I'll be doggone if I can't figure this out. The code showing my issue is below. Here's a description of the setup - I'll keep it as short as I can.

I have 2 classes - Sentences and Sentence. Sentences houses each Sentence in a vector of pointers to each dynamically allocated Sentence.

Each Sentence has a "level", like 1, 5, 10, 15, etc. This is akin to COBOL if you are familiar with that. The level defines a hierarchy and groupings. In this example, these are my Sentence[s]:

name=FIELDA     level=1, repeat=4 length=0 
name=FIELDB     level=5, repeat=1 length=5 
name=FIELDC     level=5, repeat=1 length=2 
name=FIELDD     level=1, repeat=1 length=12

The above would show length of 19 is simply added up.

What I am trying to do is apply the repeat factor and expand my vector to look like this:

name=FIELDA     level=1, repeat=4 length=0 
name=FIELDB     level=5, repeat=1 length=5 
name=FIELDC     level=5, repeat=1 length=2 
name=FIELDB#1 level=5, repeat=1 length=5 
name=FIELDC#1 level=5, repeat=1 length=2 
name=FIELDB#2 level=5, repeat=1 length=5 
name=FIELDB#2 level=5, repeat=1 length=2 
name=FIELDB#3 level=5, repeat=1 length=5 
name=FIELDC#3 level=5, repeat=1 length=2 
name=FIELDD     level=1, repeat=1 length=12

The correct total length is 40.

FIELDB and FIELDC get repeated the number of times specified by FIELDA. FIELDD is ignored because it's level is not higher than FIELDA.

Although my test case does not show it, FIELDB or FIELDC could also have a repeat level, and there could be fields under it which would also have to be expanded.

So, my issue!! (finally).

In Sentence::replicate, I'm using 4 iterators to keep track of my position with the vector of Sentence pointers and iterator elem_start is changing (somehow) after the first loop. When variable j becomes 2, variable tmp gets corrupted due to elem_start being corrupt. I've put a lot of cout statements in the code and stepped through the code in the debugger, but I still cannot figure it out. (I'm using Xcode on Tiger 10.4.11).

Here's my current output:

[Session started at 2007-12-24 07:44:35 -0600.]
Sentence address = 0x3003e0
Sentence address = 0x300420
Sentence address = 0x300410
Sentence address = 0x300450

REPEAT level start=1, and there are 4 elements to add.
Field with REPEAT is FIELDA
	last known good end field is FIELDB
	inspecting name=FIELDC, level=5, current repeat level=1...
	last known good end field is FIELDC
	inspecting name=FIELDD, level=1, current repeat level=1...
starting field name = FIELDB
ending   field name = FIELDC
Replicating FIELDB thru FIELDC 3 times.

J = 1, tmp = 0x300420
Index name = FIELDB
Index=0x300420, Last=0x300410
Top of DO loop...  j = 1
Replicate Sentence address = 0x3004b0
temp name = FIELDB#1
temp length = 5
temp repeat = 1
temp level = 5
Index=0x300410, Last=0x300410
Top of DO loop...  j = 1
Replicate Sentence address = 0x300480
temp name = FIELDC#1
temp length = 2
temp repeat = 1
temp level = 5
J = 2, tmp = 0x1

And here's the code. The clause in RED causes the issue. I stepped through the code in the debugger and when j==2, that clause causes elem_start to become corrupt (0x1 is the corrupted value). What's going on????!!!

#include <iostream>
#include <string> 
#include <vector>
#include <iomanip>
#include <sstream>

using namespace std ; 

//////////////////////////////////////////////////////////////////////////////////////////////////////////

class Sentence { 
	int    level ; 
	int    repeat ; 
	int    length ; 
	string name ;           
public: 

// Member Method Declarations (setters / getters) 
	Sentence() ; 
	void   set_level(int) ; 
	int    get_level() ; 

	void   set_repeat(int) ; 
	int    get_repeat() ; 

	void   set_length(int) ; 
	int    get_length() ; 
	
	void   set_name(string) ; 
	string get_name() ; 
} ; 

// Member Method definitions 

Sentence::Sentence() {    // class Constructor 
	repeat = 1 ;          // assume field does not repeat
}  

void   Sentence::set_level(int n) { level = n ; } 
int    Sentence::get_level()      { return level ; } 

void   Sentence::set_name(string s) { name = s ; } 
string Sentence::get_name() { return name  ; }

void   Sentence::set_repeat(int n) { repeat = n ; } 
int    Sentence::get_repeat() { return repeat ; } 

void   Sentence::set_length(int n) { length = n ; } 
int    Sentence::get_length() { return length ; }  

//////////////////////////////////////////////////////////////////////////////////////////////////////////

class Sentences { 
	vector<Sentence *>  sentences ;  
	vector<Sentence *>::iterator elem , elem2, elem_start , elem_end ; 
	int        i ;   // index 
public: 
	           Sentences::Sentences() ;  // Constructor declaration  
	void       add_sentence(Sentence *) ; 
	int        sentence_count() ; 

	void       reset() ; 
	void       set_range_start() ; 
	void       set_range_end() ;  

	Sentence * next() ; 
	Sentence * next2() ; 
	void replicate(int) ; 
	
} ; 

Sentences::Sentences() { i = 0 ; } 

void Sentences::add_sentence(Sentence * s) { 
	sentences.push_back(s) ; 
} 

int  Sentences::sentence_count()       { return sentences.size() ; } 


void Sentences::reset()       { 
	i = 0 ; 
	elem = sentences.begin() ; 
	elem2 = sentences.begin() ;
} 

void Sentences::set_range_start()  { elem_start = elem2 ; } 
void Sentences::set_range_end()    { elem_end = elem2 ; } 
 
Sentence * Sentences::next()     { elem2 = elem ; return *elem++ ;  }
Sentence * Sentences::next2()    { elem2++ ; return *elem2 ; }   

void Sentences::replicate(int times) { 
	Sentence * temp, * index , * last ;  // we're adding new sentences.  
	stringstream ss ; 
	vector<Sentence *>::iterator tmp_start, tmp ; 
	cout <<  "Replicating " << (*elem_start)->get_name()
		<< " thru " << (*elem_end)->get_name() << " " << times << " times." << endl << endl ; 
	tmp_start = elem_start ; 
	last  = *elem_end ; 
	
	for (int j = 1 ; j <= times ; j++ ) {    // Add "times" elements 
		tmp = tmp_start ; 
		index = *tmp ;
		cout << "J = " << j << ", tmp = " << *tmp << endl ; 

		cout << "Index name = " << index->get_name() << endl ;  
		cout <<  "Index="<< index << ", Last=" << last << endl ;

		do { 
			cout << "Top of DO loop...  j = "<< j << endl ; 

			temp = new Sentence() ;  // Allocate a new sentence 
			cout << "Replicate Sentence address = " << temp << endl ; 
			ss.str("") ;   // reset to empty. 
			ss << index->get_name() << "#" << j ; 
			temp->set_name( ss.str() ) ;    // Add a suffix to the field name 
			cout << "temp name = " << temp->get_name() << endl ; 
			temp->set_length(index->get_length()) ; 
			cout << "temp length = " << temp->get_length() << endl ; 
			temp->set_repeat(index->get_repeat()) ; 
			cout << "temp repeat = " << temp->get_repeat() << endl ; 
			temp->set_level(index->get_level()) ; 
			cout << "temp level = " << temp->get_level() << endl ; 
			sentences.insert(elem+1, temp) ; 
			
			if ( index->get_name() == last->get_name() ) break  ;
				// exit if the field name just added matches the last name.
			
			tmp++ ; 
			index = *tmp ; 
			cout <<  "Index="<< index << ", Last=" << last << endl ; 
		} while (1) ; 
	} 
} 
 
//////////////////////////////////////////////////////////////////////////////////////////////////////////

int main (int argc, char * const argv[]) {

	Sentences * sentences ;        // A pointer to "Sentences" class
	sentences = new Sentences() ;  // We only get one of these. 
	Sentence * sen ;               // A pointer to a Sentence 
		
	sen = new Sentence() ; 
	cout << "Sentence address = " << sen << endl ; 
	sen->set_level(1);  
	sen->set_name("FIELDA") ; 
	sen->set_length(0) ; 
	sen->set_repeat(4) ; 
	sentences->add_sentence(sen) ; 
	
	sen = new Sentence() ; 
	cout << "Sentence address = " << sen << endl ; 
	sen->set_level(5) ;  
	sen->set_name("FIELDB") ; 
	sen->set_length(5) ; 
	sentences->add_sentence(sen) ; 
	
	sen = new Sentence() ; 
	cout << "Sentence address = " << sen << endl ; 
	sen->set_level(5) ;  
	sen->set_name("FIELDC") ; 
	sen->set_length(2) ; 
	sentences->add_sentence(sen) ; 
	
	sen = new Sentence() ; 
	cout << "Sentence address = " << sen << endl ; 
	sen->set_level(1) ;  
	sen->set_name("FIELDD") ; 
	sen->set_length(12) ; 
	sentences->add_sentence(sen) ; 

	sentences->reset() ; 

	
	// Loop through all sentences, and expand all repeating clauses.  
	
	// First, find a clause that contains a REPEAT clause and note it's level number.  Note's it's index. 
	// Get the range of all immediately following sentences with a lower level number.  
	// Reinsert that range "repeat-1" times, altering the name to suffix a "#n", where "n" is the repeat number.  
	// Continue with next clause following "start" until done. 
	
	int current_repeat_level  ; 
	int current_repeat ; 
	Sentence * s_start, * s_end  ;  // first and last to insert 
		
	sentences->reset() ; 
	
	for ( int i = 0 ; i < sentences->sentence_count() ; i++ ) { 
		sen = sentences->next() ; 
		if (sen->get_repeat() > 1) { 
			current_repeat       = sen->get_repeat() ;  
			current_repeat_level = sen->get_level() ; 

			cout << "\nREPEAT level start=" << current_repeat_level
				<< ", and there are " << current_repeat << " elements to add." << endl  ; 
			cout << "Field with REPEAT is " << sen->get_name() << endl ; 
			
			sen = sentences->next2() ;    // set second iterator  
			sentences->set_range_start() ;      // set 2nd iterator up  

			s_start = sen ;        // starting element 
			do {
				s_end = sen ;      // assume this is the last one 
				sentences->set_range_end() ; 
				cout << "\tlast known good end field is " << sen->get_name() << endl ; 
				sen = sentences->next2() ;   // get next sentence 
				cout << "\tinspecting name=" << sen->get_name() << ", level=" << sen->get_level()
					<< ", current repeat level=" << current_repeat_level << "..." << endl;  
			} while (sen->get_level() > current_repeat_level) ;  // see if it's the last one 
		
			// Now, add new elements 
			cout << "starting field name = " << s_start->get_name() << endl ;  
			cout << "ending   field name = " << s_end->get_name() << endl ;  
			sentences->replicate(current_repeat-1 ) ; 
		}
	}
 
	
	//******************************************************************
	
	// Now, loop through all statements, and accumulate the total length
	// Should be 40 
	
	sentences->reset() ; 
	
	int total_length = 0 ; 
	
	for ( int i = 0 ; i < sentences->sentence_count() ; i++ ) { 
		sen = sentences->next() ; 
		
		total_length += sen->get_length() ; 

		cout <<  "Level=" ; 
		cout << right << setw(2) << setfill('0') << sen->get_level() ; 
		cout <<  left << ", " << setw(30) << setfill(' ') << ("'" + sen->get_name() + "'")  ;  // left justify, pad to 30 bytes 
		if (!sen->get_length() == 0) { 
			cout << endl ; 
			continue ; 
		}
		cout << ", len=" << right << setw(2) << setfill('0') << sen->get_length() ; 		
		
	} 
	cout << "Done." << endl ;  
    return 0;
	
}

Any help is appreciated very much.

Thanks, Todd

[laserlight]

Insertions into a vector causes iterators to elements after the insertion point to be invalidated. If reallocation is needed (e.g., the vector needs to expand its capacity), all iterators to any element in the vector are invalidated.

[Dino]

Well, I figured something like that might be happening..

Why does it not show up (why does the pointer not become invalidated) until the new Sentence() call? (which has absolutely nothing to do with the Sentences iterators)

Todd

[cpjust]

vector::insert() returns a new iterator which you don't seem to be using. You should save that iterator like this:

it = vec.insert( it, value );

[Dino]

I've rewritten my routine and it now works like a champ. I'm using a combination of indexing and iterators to traverse the vector, resetting my iterators via my initial indexes after each insert.

Is there a built-in method to convert between an index and an iterator & vice-versa? I wrote one after I couldn't find one.

Todd

Merry Christmas!

[ZuK]

#include <vector>
#include <iostream>

using namespace std;

int main() {
    vector<int> v(10);
    unsigned int idx = 5;
    for ( int i = 0; i < v.size(); ++ i )
        v[i] = i;
    vector<int>::iterator vi = v.begin()+idx;  // iterator from index
    cout << *vi << endl;
    idx = vi - v.begin();  // index from iterator
    cout << "index  " << idx << endl;
}

Works for random access iterators only.
Kurt

[Dino]

Perfect!!

Thanks!

Todd