Sign in to follow this  
ChaosFollowing

[C++] Taking the Pointer Plunge

Recommended Posts

As mentioned in my previous thread, I somehow picked up an extreme aversion to pointers while learning C++, and have been using vector<type>::iterators for quite literally ever-y-thing(thank you, reserve). Reading my book, I get a basic grasp of the pointer concept as applied to simple types, but I'm at a bit of a loss when it comes to converting my iteratorized program to healthier(i.e. non-invalidating) pointers. An example from my old main: (where Village is a class)
Quote:

	vector<Village> world;
	world.reserve(10); //to be removed once pointerized
	for (int i = 1; i <= 5; ++i) {
		world.push_back(Village(i)); //Create two villages
		world.push_back(Village(i)); //for each of the 5 tribes
	}

and later referenced as:

	for (viterator cVillage = world.begin(); cVillage != world.end(); ++cVillage)
		cVillage->Describe();


How do I change world into a vector of pointers(of Villages), add new elements correctly, and later reference them? I get a little lost after adding the * in the first line. Much thanks for any help.

Share this post


Link to post
Share on other sites
You just need to dereference anything one more time to get to the Village.


//vector of pointers
vector<Village*> world;

//typedef of the iterator
typedef vector<Village*>::iterator vpiterator;

//when adding Villages you probably don't want to reference local objects
//so what do you do?
world.push_back(new Village(i));

//dereferencing the iterator
(*cVillage)->Describe();



You shouldn't do this, unless you have a very good reason, though. If you allocate objects with new it is your responsibility to make sure that they will be cleaned up with delete.

Share this post


Link to post
Share on other sites
Quote:
Original post by visitor
You shouldn't do this, unless you have a very good reason, though. If you allocate objects with new it is your responsibility to make sure that they will be cleaned up with delete.


Hmmm, so I have two flawed methods.

Iterators, which decay if the vector needs to be moved to a new address in memory.(my Mortal class has a viterator variable called myLocation, for instance)

Pointers, which I have to make sure I delete when done with them. Alright, that's not too bad...though I'd be curious about any better third option.

I didn't realize that new returned a memory address, all ready for pointers. I assume delete works the same way. Can I just put:

Quote:

for (vpiterator cVillage = world.begin(); cVillage != world.end(); ++cVillage)

delete cVillage;


...at the end of my program, to avoid memory leaks? Does that reset the pointer to NULL, or leave as is but remove the entry?

Share this post


Link to post
Share on other sites
Quote:
Original post by ChaosFollowing

Iterators, which decay if the vector needs to be moved to a new address in memory.(my Mortal class has a viterator variable called myLocation, for instance)


It is not a good idea to keep vector::iterators around for referencing things (unless you are absolutely sure that the vector won't invalidate the iterators).
Vector indices are a bit more resistant to invalidating: even if the vector is reallocated, vec[n] is still valid (assuming it or anything before it hasn't been erased).
Also, list iterators are more resistant to invalidating (nodes in a list pretty much stay where they were allocated - perhaps more precisely: the location of the object held in the list doesn't tend to change).

Quote:

Pointers, which I have to make sure I delete when done with them. Alright, that's not too bad...though I'd be curious about any better third option.


Smart pointers (such as boost::shared_ptr) take care of looking after the memory. (Although you might get circular references. Perhaps since Mortals probably don't own Villages - and die when the village is destroyed and not keep the village alive while they are - they should hold a regular or a boost::weak_ptr stored in a vector of shared_pointers of Village. You still have to thing which object(s) own other objects.)

Quote:

I didn't realize that new returned a memory address, all ready for pointers. I assume delete works the same way. Can I just put:

Quote:

for (vpiterator cVillage = world.begin(); cVillage != world.end(); ++cVillage)

delete cVillage;


...at the end of my program, to avoid memory leaks? Does that reset the pointer to NULL, or leave as is but remove the entry?

delete only frees the memory. It doesn't set the pointer to NULL, it just invalidates it. The vector then clears up the memory occupied by (now invalid) addresses.

And you can't delete an iterator, you have to delete the pointer that the iterator dereferences to.

Share this post


Link to post
Share on other sites
Quote:
Original post by ChaosFollowing
As mentioned in my previous thread, I somehow picked up an extreme aversion to pointers while learning C++,


Congratulations! this is a sign that you have actually learned something. Use X when you can, and pointers only when you really have to. There are quite a few possible values of X.

Quote:
and have been using vector<type>::iterators for quite literally ever-y-thing


Er?

First off, there are quite few things you can use the actual iterator for. Basically, you can use them for, well, iterating. The actual storing of elements, for example, is done by the container.

What you're trying to get at is that you're storing elements by value in containers. Which is fine; it's what you should do, if you don't have a reason otherwise.

Quote:
(thank you, reserve).


Huh? The .reserve() function of vectors has nothing to do with this. There is nothing that prevents you from calling .push_back() on a vector that doesn't have enough reserved space. In fact, the fact that you can do that is one of the main reasons to use a vector in the first place.

The only place where you might have a problem is if your object can't be copied properly, but that (a) is not something you're likely to get into if you're avoiding pointers anyway, and (b) really should prevent you from using the container *at all*.

Quote:
Reading my book, I get a basic grasp of the pointer concept as applied to simple types, but I'm at a bit of a loss when it comes to converting my iteratorized program to healthier(i.e. non-invalidating) pointers.


I can't figure out what you think you mean here.

First off, there are two completely separate issues here. One is storing elements by value vs. storing pointers as elements; and the other is using iterators vs. using pointers to elements.

Iterators get invalidated in particular circumstances. These are almost exactly the same circumstances, in general, in which a pointer to the element would become invalid. The pointer would either now point to the wrong element, or to somewhere in "garbage" memory that is no longer used by the container, or something else of that sort. With the iterator, it's not specified what happens, because the whole point is that you're not supposed to think about it: the iterator isn't valid, so don't freakin' use it, mm'kay? However, the reasons for invalidation are, by and large, the same however you do it.

This is completely unrelated to the issue of storing pointers as the elements of the container, such that those pointers point to the "real" elements. The vector doesn't care about any of that. All it knows is that it holds elements, and the elements are of a given type. The fact that that type is a pointer type is something it doesn't care about, and the fact that those pointers point at something you dynamically allocated with 'new' is something it definitely doesn't care about.

The rules are simple: the vector cleans up the memory it allocates. You clean up the memory you (manually) allocate.

Cleaning up memory *properly* is hard. That's why we, generally speaking, don't manually allocate memory if we can avoid it.

Quote:
How do I change world into a vector of pointers(of Villages), add new elements correctly, and later reference them? I get a little lost after adding the * in the first line.


You add the elements exactly the same way as you would elements of any other type. You just have to remember that your elements are the pointers. Then you use the pointers to access the pointed-at things, which are indirectly referred to from the container. This is where the term "indirection" comes from.

Quote:
Iterators, which decay if the vector needs to be moved to a new address in memory.(my Mortal class has a viterator variable called myLocation, for instance)


They don't "decay"; they get invalidated.

You should, practically speaking, never have iterators as data members of a class.

Quote:

Pointers, which I have to make sure I delete when done with them. Alright, that's not too bad...though I'd be curious about any better third option.


Aha... finally I get a sense of what you're really trying to do.

You want the Mortal to be able to refer to the same Village (its "location") that is in the container, rather than making a copy; and you want to keep referring to the same Village even if it gets "moved" (actually copied, and the original destroyed) around in memory by the container.

We can't really do that, but we can compromise, by making the container and the Mortal refer to the same Village, which is stored somewhere else. That's where the vector-of-pointers ideas comes in. But to avoid the memory management problem, we want to use some kind of smart pointer instead. Here, the important idea is that we're sharing the Village between container and Mortal, so we want something like boost::shared_ptr.

However, for this particular situation, it turns out there's a simpler way to do it. The standard library linked list container, std::list, never moves inserted elements around in memory, because it has no reason to (removing or inserting elements involves "re-linking", instead). Thus, pointers and iterators to elements only get invalidated if *that element itself* is removed.

Quote:
I didn't realize that new returned a memory address, all ready for pointers.


Er, well, how did you think it worked? (Did you think about it at all? Have you seen any code that used 'new'?)

Quote:
...at the end of my program, to avoid memory leaks? Does that reset the pointer to NULL, or leave as is but remove the entry?


'delete' cleans up the pointed-at thing. It does nothing to the pointer, which is a separate entity. There is no need to do anything about the pointer itself.

Remember: You clean up the memory you allocate; the vector cleans up the memory it allocates.

You allocated the (memory for the) new Villages, so you iterate and call 'delete' on each Village*. If you can be sure that (a) the vector contains *exactly one* pointer to *each* Village you allocated, and that *none* of those Villages will get deallocated by *something else* then that is sufficient and correct, yes. But ensuring these kinds of things, in general, is a pain - which is why we use smart pointers. At this point, the Village* s held in the vector are invalid (because their targets no longer exist). But that's okay, because we're not going to *use* them ever again.

The vector allocated the memory which holds the Village* s. It will not do anything about the pointed-at Village instances. It will "call destructors" for the Village* s (since Village* is a primitive type, this does nothing), and then call delete[] for its memory allocation. That causes all the invalid Village* s to, themselves, stop existing. And all is right with the world (er, program).

Share this post


Link to post
Share on other sites
Thanks for all the advice.

The above and a little experimentation led to the decision that since std::list had (almost) all the features of std::vector I needed, without having to worry(so much) about iterator invalidation, it was the way to go.

So I've painstakingly converted my program from vectors to lists, and it works! :) Had to remove all my iterator +1/-1(for example, when grabbing second-last iterator in the list), but easily replaced with ++/--.

The only (minor) problem was re-implementing random-access(i.e. choosing a random Village or Mortal) with a function that takes parameters(myList.begin(), myList.size()), which works a treat.

Cheers!

Share this post


Link to post
Share on other sites
Quote:
The above and a little experimentation led to the decision that since std::list had (almost) all the features of std::vector I needed, without having to worry(so much) about iterator invalidation, it was the way to go.
Sounds like you may have solved the wrong problem. In general, you don't want to be storing iterators or worrying about whether they're valid. Iterators are for the most part intended to be used as their name suggests - for iterating over a collection of objects. They are not well suited for referencing objects long-term (there are better tools available for that).
Quote:
The only (minor) problem was re-implementing random-access(i.e. choosing a random Village or Mortal) with a function that takes parameters(myList.begin(), myList.size()), which works a treat.
The fact that you had to hack in random access may be another indicator that you've chosen the wrong container.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this