STL sort - vector iterators incompatible error

[mp9191]

Hello,

I'm new to these forums (and fairly new to C++), but I read the rules so I hope I don't break any :)

Basically I have a string vector called final, and an iterator for that vector called sortIt. I also have an int variable called q, to which 1 is added each time a new element is added to "final". I initialize sortIt to final.begin(), and after all new elements have been added to final, I have this:

sort(sortIt,final.end());
sortIt+=q;

Then the process repeats, except it should sort only the section of the vector from where sortIt points on. Basically, I'm trying to sort only a section of the vector at a time. However, during runtime, I get the "vector iterators incompatible" error, so I'm assuming it doesn't like me passing my iterator as an argument for sort() (which is the STL sort function).

Can someone please tell me what I'm doing wrong/offer an alternative method?

Thank you :)

[naivnomore]

Any iterator (almost all) into a vector gets invalidated during inserts and deletes. Remember, vector stores all its elements contiguously in memory. Therefore, if there is no memory available for adding new elements, the entire vector will have to be reallocated into a new memory location that has enough room for storing all the existing elements of the vector plus the new one. This process will involve copying all the elements from the old location to the new location & then deleting the elements in the old location. Therefore, any iterator pointing to elements in the old location gets invalidated.

However, for your code to work, you could explicitly do a find (find algorithm) for the newly inserted element post sorting. Find method will get you a valid iterator into the vector if the element exists. You may now do the sorting of the newly inserted elements using this iterator as the starting point on your sort algorithm. This way you will only sort the elements that were newly inserted. However, there is a small caveat with this approach. If any of the newly inserted elements are same as the existing elements, find will try to retrieve the element from the previously sorted range & not from the newly inserted range & thus sorting algorithm will try to sort some of the older elements too.

[R0mai]

Can you post some code?
The problem should be what naivnomore said, but we can't come up with a working solution, if you don't post some code.

[mp9191]

I tried what naivnomore said, but I'm not sure I did it correctly.

Here is my code, minus the irrelevant functions (or so I believe):

int main()
{
	vector<string> dict, inputWords, final; 
	vector<string>::iterator dIt, fIt;
	ifstream ins;
	int i, n, j, k;
	string word, temp, sortWord;

    inputs(word, inputWords, dict, ins);  //asks user for puzzle words, sorts each one, adds       
                                                              //them to vector inputWords; loads all words from
                                                              //dictionary file into vector dict
                                                             

	for(i=0;i<(inputWords.size());i++)  //for each puzzle word
	{
		k=(inputWords[i]).length();
		for(n=3;n<=k;n++)                 //dictionary words are at least 3 letters long
		{
			word.clear();
			temp=(inputWords[i]);
			for(j=0;j<n;j++)
			{
				word.push_back(temp[j]);
			}
			do
			{
				do
				{
			           searchDict(dict, final, word, dIt, fIt, sortWord);  //checks vector dict for 
                                                                                                   //current permutation of word; if
                                                                                                   //found, adds to vector final;
                                                                                                  //sortWord is last word added	   

			    }while(next_permutation(word.begin(),word.end()));    
		    }while(next_combination((inputWords[i]).begin(), (inputWords[i]).end(),
                               word.begin(), word.end()));

			sortVec(final, sortWord);  //***see below***

		}
		printVector(final);    //prints final vector
		final.clear();
	}


system("pause");
return 0;
}


void sortVec(vector<string>& vec, string key)
{
	if(key!="")
	{
		vector<string>::iterator temp=find(vec.begin(), vec.end(), key);
	    sort(temp, vec.end());
	}
}

The program input is one number and however many words that number is, and output is all of the words that can be made from that word (which come from a dictionary file).
(I got the next_combination function from my professor)

Any suggestions? I apologize if I haven't posted enough code.

EDIT: Also forgot to mention that the words added ARE unique, so naivnomore's solution should be valid.

And sorry the code is so spaced out. ><

[naivnomore]

Sorry I am not able to follow your code completely. I am assuming you would like every new word added into your vector to be sorted. If that is the case, you may use a set container with string elements. Any element you add to a set will be sorted automatically for you and the set container will not allow any duplicates as well. Below is a simple example of a set container. Any strings that you pass in the command line to this program will be added to the set container in sorted order & duplicates (if any) will be ignored.

#include <iostream>
#include <set>
#include <string>
#include <algorithm>
#include <iterator>
using namespace std;

int main(int argc, char* argv[])
{
	if (argc > 1){
		set<string> sargs(argv+1, argv+argc);
		copy(sargs.begin(), sargs.end(), ostream_iterator<string>(cout, "\t"));
		cout << endl;
	}
}

[mp9191]

I apologize for making this so confusing. The words in my vector need to be sorted by length first, then alphabetically.

for example, if the original word is "tears" then the words that can be made from that must be sorted like this:

are ear era sear tare tear tares tears (obviously this isn't all the words but you can see the pattern)

That's why I need a way to point to the element where the last word of length n was entered, so that when the words of length n+1 are entered, I can sort from that point onward.

I hope this has cleared it up a bit, thank you for taking time to help me.

[mp9191]

I figured it out myself! Sorry to have bothered you guys, but I do appreciate your help.

I solved it just by adding two int variables, r and q, initializing both to 0 right in the first for loop, and updating q each time a word of length n was entered (in the searchDict function). Then, after the next_combination do while loop, I did

sort(final.begin()+r, final.end());
r=q;

This way, r is always going to be where I left off adding words of length n, and q is always where I will be adding words of length n+1.

Again, I apologize for not being clear in my question. But thank you