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

This is a discussion on vector<...>::iterators and insert - I'm stumped. within the C++ Programming forums, part of the General Programming Boards category; Hey y'all. First post here in the C++ section. I'm working on a commission for a client, and I'll be ...

  1. #1
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Katy, Texas
    Posts
    2,309

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

    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]:

    Code:
    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:

    Code:
    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:
    Code:
    [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????!!!

    Code:
    #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
    Last edited by CornedBee; 12-24-2007 at 08:24 PM. Reason: Broke some long lines

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    22,304
    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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Katy, Texas
    Posts
    2,309
    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

  4. #4
    and the hat of sweating
    Join Date
    Aug 2007
    Location
    Toronto, ON
    Posts
    3,545
    vector::insert() returns a new iterator which you don't seem to be using. You should save that iterator like this:
    Code:
    it = vec.insert( it, value );

  5. #5
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Katy, Texas
    Posts
    2,309
    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!

  6. #6
    ZuK
    ZuK is offline
    Registered User
    Join Date
    Aug 2005
    Location
    Austria
    Posts
    1,990
    Code:
    #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

  7. #7
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Katy, Texas
    Posts
    2,309
    Perfect!!

    Thanks!

    Todd

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. insert into binary tree question..
    By transgalactic2 in forum C Programming
    Replies: 32
    Last Post: 11-18-2008, 03:21 PM
  2. How to insert an item to a ListView
    By ysabelle in forum C++ Programming
    Replies: 2
    Last Post: 05-07-2007, 08:03 AM
  3. How to insert data to the top of exist text file?
    By ooosawaddee3 in forum C++ Programming
    Replies: 4
    Last Post: 08-16-2005, 09:08 AM
  4. Insert unique record into database
    By groorj in forum C Programming
    Replies: 4
    Last Post: 12-29-2004, 11:06 AM
  5. Replies: 1
    Last Post: 09-17-2001, 06:46 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21