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

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.

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

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 );

---

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!

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

Perfect!!

Thanks!

Todd