Vector::erase()

[Yawzheek]

Hey guys, how you doing this morning?

Well, I've been trying to expand my horizons and use functions I've never used before, and today I decided to give erase() a shot. Well, after battling with it for awhile (guess who passed it as a const vector? This idiot right here!) I managed to get rid of compiler errors.

The long and short of it is I'm not supposed to print repeat words, BUT ALSO not supposed to change the order in which the words were received. Fair enough. I'll just give relevant code (since input is a standard for with a string control on cin and print is your standard range-for):

  void remove_repeats(std::vector<std::string>& vs) //Helper to exercise 11
{
	for (auto i = vs.begin(); i != vs.end(); ++i) {
		if (i != vs.end() - 1) {
			for (auto j = i + 1; j != vs.end(); ++j) {
				if (*i == *j) vs.erase(j);
			}
		}
	}
}

Now I realize I have a TON of options, not least of which is to just push_back words that aren't repeated into a new vector and return that, but that doesn't seem ideal, and again, trying new things. If I don't repeat words (and thus erase isn't called) I have no problems, but if I do, I get a neat run-time error about incrememnting iterators, and that is also noteworthy because without the unary * it refuses to remove elements at all and repeats words, but with it I get the error.

Any pointers here would be great. I'm kind of at a loss. I'm also wondering if I couldn't just put the first iteration in a range-for but... baby steps.

[AbstractionAnon]

Line 6: If you execute vs.erase(j), what was in j is of course no longer there. vs[j+1] has been moved to vs[j]. Your next iteration of the loop will skip what was in vs[j+1].

[jlb]

The problem is probably that when you erased the element you invalidated the iterator.

Iterator validity
Iterators, pointers and references pointing to position (or first) and beyond are invalidated, with all iterators, pointers and references to elements before position (or first) are guaranteed to keep referring to the same elements they were referring to before the call.

I get a neat run-time error about incrememnting iterators, and that is also noteworthy because without the unary * it refuses to remove elements at all and repeats words, but with it I get the error.

Remember iterators are similar to pointers, you need to dereference them to get the value.

[Yawzheek]

Yup, you guys nailed it.

I guess I'm wondering why even to bother with iterators now? I mean, they're convenient, sure, but this?

void remove_repeats(std::vector<std::string>& vs) //Helper to exercise 11
{
	for (size_t i = 0; i != vs.size(); ++i) {
		for (size_t j = i + 1; j != vs.size() && i != vs.size() - 1; ++j) {
			if (vs[i] == vs[j]) vs.erase(vs.begin() + j);
		}
	}
}

This got the job done with little headache. C++ Primer went nuts about them, "Oh they're what C++ programmers use! They're the best! Get you some iterators!" and I suppose if all I needed to do was traverse a vector and make small changes but leave it largely the same, it works, but in this particular case (with erase) it's just hell.

[Yawzheek]

I guess now the question is: from my first code, is there a (simple) way to do it properly with iterators? I'm certain the question is stupid, since at the first instance of erase it would (as jlb states) invalidate them as it would have to change them, but I'm wondering.

It seems to me the "basic" method above, taught at pretty much the start of every programming book I've read on C++ would be the only way if it added or removed elements, but now I'm curious.

[AbstractionAnon]

Are you required to use a vector? A std::set would ensure that you have no duplicates.

If you are required to use a vector, I would think it would be easier to check at the time you do the push_back onto the vector if the word is already in the vector.

[Yawzheek]

Well, it's an exercise from "The C++ Programming Language." More specifically, this exercise:

/* 11) Read a sequence of words from input. Use Quit as a word that terminates the input.Print the words in the order they were entered.Don’t print a word twice.Modify the program to sort the words before printing them.*/

And you would think, "Then you've done it. Include <algorithm> and sort() it, dummy. What's the problem?" You'll probably notice when I tell you the chapter is titled, "Pointers, Arrays, and References." :/

So yeah, I likely wasn't even supposed to use string or vector, but I wanted to do it with that as well, and haven't implemented it with an array and C-style string yet.

:/ += QQ

But set looks interesting. I glanced it over, and it has, "unique element" limitations, which seems like it would have been ideal for the vector solution.

[Yawzheek]

Well I guess this is the horrific mess I've got as a final solution, and I think I hate everything about it, ESPECIALLY the array versions. Absolutely despise them.

//Exercise 11 vector version
void print_sequence(std::vector<std::string>& vs) //Exercise 11 w/vector
{
	remove_repeats(vs);
	for (const string& s : vs) cout << s << endl;
}
void remove_repeats(std::vector<std::string>& vs) //Helper to exercise 11
{
	for (size_t i = 0; i != vs.size(); ++i) {
		for (size_t j = i + 1; j != vs.size() && i != vs.size() - 1; ++j) {
			if (vs[i] == vs[j]) vs.erase(vs.begin() + j);
		}
	}
}
void sort_vector(std::vector<std::string>& vs) //And print - we're condensing this
{
	sort(vs.begin(), vs.end());
	for (const string& s : vs) cout << s << endl;
}

//Exercise 11 array version
void arr_print_sequence(string* words) //Exercise 11 w/array
{
	arr_remove_repeats(words);
	for (size_t i = 0; i != 20; ++i) {
		if (words[i] == "") continue; //Because the array comes presized
		cout << words[i] << endl;
	}
}
void arr_remove_repeats(string* words) //Exercise 11 w/array
//NOTE: this likely isn't ideal by any stretch of the imagination, but it's functional
{
	for (auto orig = 0; orig != 20; ++orig) {
		for (auto check = orig + 1; check != 20; ++check) {
			if (words[orig] == words[check]) words[check] = ""; //Presized array
		}
	}
}
void arr_sort(std::string* words) //And print - condensing as well
{
	for (size_t i = 0; i != 20; ++i) {
		for (size_t j = 0; j != 20; ++j) {
			if (j != 19 && words[j] > words[j + 1]) swap(words[j], words[j + 1]);
		}
	}
	for (size_t i = 0; i != 20; ++i) {
		if (words[i] == "") continue;
		cout << words[i] << endl;
	}
}