Vectors as a substitute for ArrayLists

Ok, I’m not really sure if this fits to the advanced forum but here it goes:

I’m migrating from processing and doing well so far. I’ve never used C++ in big and relatively complex projects so I’m trying to find the necessary tools in C++ to be able to design well nd create my workflow.

I’m pretty sure that most people migrating from p5 has this problem, and they find out vectors, at least this is what happened to me. However there seems to be some limitations about vectors and I can’t find my way around it.

My first question: I think, vectors can hold only a single type of data. Say I have a base class, and some other classes inheriting from that class. With ArrayLists, I could hold any instances of them in a single list(by boxing and unboxing). If I wanted such a functionality in C++, what would be my options?

Thanks
(oh and OF is rocking my world these days, Thanks again!)

If I understand your question you want to store classes with same base class in a vector. The way to do that is not to store the instances in the vector but their pointers.

If I’m correct there is an other post on the forum about this.

This is how:

  
  
class Animal {  
};  
  
class Cat : public Animal {  
};  
  
class Dog : public Animal {  
}  
  
....  
  
vector<Animal*> animals;  
  
Animal animal;  
Cat cat;  
Dog dog;  
  
animals.push_back(&animal);  
animals.push_back(&cat);  
animals.push_back(&dog);  
  

I hope this helps.

1 Like

By the way. I found a cool script which gives us Associative Arrays / Key Value Pairs / Maps, however you want to call it. It’s very easy to use.

http://www.radcpp.com/article.php?art-id=1170433117%7B13%7D

  
  
Array <int> kv;  
kv["width"]=800;  
kv["height"]=600;  
cout << kv["width"];  
  

wow that script is really interesting !

the vector stuff is interesting - I usually do arrays of pointers but in the same form. something I thought to point out:

  
  
Animal animal;  
Cat cat;  
Dog dog;  
animals.push_back(&animal);  
animals.push_back(&cat);  
animals.push_back(&dog);   
  

at first glance, my thought is to be careful about scope here, since once a variable, like “cat” is out of scope, the pointer that animals holds points to nothing.

alternatively, it seems to me that you can allocate as you push back:

  
  
animals.push_back(new Animal());  
animals.push_back(new Cat());  
animals.push_back(new Dog());   
  

which might be safer, no?

looking at this code. I remembered a question I had before – is there any way to get the type out of the vector? ie, to know that animals[1] is a cat, or is that something you have to remember.

I understand that you can force it, ie:

((Cat *)animals[1])->meow();

but just wondering about knowing type in that kind of situation…

at any rate, thanks for posting the vector stuff, super useful to see.

take care,
zach

Thanks for the quick responses, much appreciated.

Yes, using pointers is neat, I’ll hopefully, eventually get used to thinking more elastically with pointers over time.

at first glance, my thought is to be careful about scope here, since once a variable, like “cat” is out of scope, the pointer that animals holds points to nothing.

Yes, one should watch out for that. Actually I was loking for something like this, as in your example:

  
>     animals.push_back(new Animal());   
>     animals.push_back(new Cat());   
>     animals.push_back(new Dog());  
>     

I didn’t know that this was possible. How would I declare the vector type then? With ? And this would mean that vectors can hold multiple data types with different sizes, no? If I can hold the actual instances of objects in a vector with different sizes and types(they share the same base but they are different types I think, am I wrong?), well then that would be enough for me. I need to try it.

looking at this code. I remembered a question I had before – is there any way to get the type out of the vector? ie, to know that animals[1] is a cat, or is that something you have to remember.

What I do about this is that I declare a variable in class definitions called “myType”, give a number to it and then check that variable to determine the type. It might be a lame solution maybe, I don’t know but works for me.

All these lead me to another question: Since I’m used to the leisure of the automatic garbage collector in Java/Processing, now I’m a bit paranoid about memory management and leaks. What would be the correct way to delete an object instance from a vector in the proposed solutions?

Zach, in your solution(pushing back with new), I guess that the vector will be holding the actual instances so, if I use the erase method on a vector, I think it would free the resources for the instance automatically. Is this right?

What if the class itself has dynamically allocated arrays inside? Do I need to explicitly free them in the destructor?

And how would I go for freeing the object instance if I’m holding the pointers to objects in the vector as proposed by companje?

I dont have answers for the deleting yet, but will check it. I think you will have to manually call delete before you erase the element.

I didn’t know that this was possible. How would I declare the vector type then? With ?

yes, same as before (as the code above) - Animal *, since new returns a pointer.

  
  
vector<Animal*> animals;   
  

And this would mean that vectors can hold multiple data types with different sizes, no?

actually they are holding objects that are the same size (Animal *) but that point to places in memory which have different sizes. This is one of the tricks of OOP

you can see it at work in this example which doesn’t use vectors but uses an array of pointers that are allocated to different types, ie baseModule * [ ], where each module is allocated to be a different type.

http://www.openframeworks.cc/files/moduleExample.zip

some background on it:

http://www.openframeworks.cc/forum/view-…-51&start=0

If I can hold the actual instances of objects in a vector with different sizes and types(they share the same base but they are different types I think, am I wrong?), well then that would be enough for me. I need to try it.

be careful, because they don’t have different sizes (ie, they are all Animal *) it’s just that with some of them, there is more there then just being an animal (they point to areas of memory that have different sizes), and you will need to cast them (as described above or in the module code) to be a specific type.

hope that helps!
zach

Ah, “new” returns a pointer. Right. Totally forgot it.

Then I would dereference from the pointer and cast to correct type. Then I can call delete on the pointed object, after that the pointer in the vector would point to garbage so I can erase that too. Hope I got it right.

Thanks for the guidance, helped much.
BB

Hey,

some more info on this:
you can get back the specific type of your object by using the typeid() function, as the typeid is stored on a per-reference basis.

  
typeid(*animals[2])   

will give you the exact type of object you are pointing to. You can even print it out like this:

  
std::cout << typeid(*animals[2]).name();  

If you know what type of object it is, you can safely cast to a pointer of that type like this:

  
 Dog * myDog=(Dog *)animals[2];   

I personally use a std::map with an instance of all my objects in it so i can quickly check against that table to see what specific object i have in my vectors. I have a very large vector full of stuff all drived form one generic base class.
I hope this helps!

f

About deleting, you have to call delete before calling vector’s delete, if not you’ll leak that memory.

The same with memory reserved by an object. A general rule, can be: if you ‘new’ something inside an object, delete it in that same object (normally in it’s destructor)

When you put something in a vector, array… like Cat*, Dog*… as Animal*, in most cases, best practice here although you can use typeid (also in java although you have instanceof) is: use a collection as general as you will need when you get the objects from the vector.

About associative arrays, you can also us std::map.

1 Like

I found another workaround, but don’t know if it is good practise or a suicide.

If I have the dummy/empty copies of all functions used in all inherited classes defined as virtual in base class, then I can simply dereference from the pointers in vectors without casting to correct type(and of course, the functions are already overriden in inherited classes). I tried it and it seems to work fine.

What do you think?

And about memory management:

About deleting, you have to call delete before calling vector’s delete, if not you’ll leak that memory.

The same with memory reserved by an object. A general rule, can be: if you ‘new’ something inside an object, delete it in that same object (normally in it’s destructor)

Ok, what about vectors defined in objects? When I free the instance, does the vectors take care of the memory themselves? I googled a bit about it, I couldn’t find something aimed for object instances and deallocation, but there are some proposals about giving the vector memory back to the system by swapping with an empty vector and pushing the swapped vector out of scope or similar but some say that such techniques do not guarantee deallocation.

Any hints?

Hi

About having all functions defined in the top of the inheritance hierarchy, definetly it’s not a good idea, it will work but inheritance has also a semantic purpose, so if you end with a dog that can meow :slight_smile: it’s not good.

You can always create several vectors (one for dogs, one for cats…) or define a static constant so you can diferenciate between classes. typeid will also do the work, but it’s slow, so if you have to call it many times, try to avoid it.

About vectors declared in objects, yes you have to explicitly delete them, first the content and then the vector itself. A general rule: for every new, a delete. In c++ nothing gets deleted by itself unless it’s not a pointer.

Yes arturo you are right. In this project(which happens to be my firs OF project) it is ok, I have 4 inherited classes that are doing similar things but in a bigger project, it would cause many problems.

Actually, I’ve considered using different vectors for each type but there is one main issue that makes it impossible for me. I’m sure its possible but I can’t think of a way:

I am creating objects on screen with my mouse, and there is a seperate gui control object which is also being populated automatically and dynamically based on number of objects. So when I create a new object on screen, the gui control element for it is also created automatically, and the only link I have between the objects and gui items are their indexes in vectors(I’m going to hold gui control objects in vectors too).

If I use seperate vectors for each type I can still hold the indexes in objects as variables, but linking gui updates to the correct instance would be hard. It can be done with local variables again on gui side too but things get complicated when I delete some objects from the canvas. When they are deleted, their gui control objects should also be deleted. If I use a single vector, then I can delete the object on canvas AND the gui control object in sync based on their indexes(which will be the same) so when some of the objects are deleted, the remaining gui objects will control correct instances on canvas. As the gap filling shifts caused by deletion of objects and gui items will be identical.

I don’t know if there is an elegant solution to such a problem with this type of design. Using a single vector and relying on indexes with gui control helps me to link them in constant time, I just call the index. If I seperate them, then I would have to iterate all the objects in each operation(to see if they match with my gui control).

Ah… I’m missing the Java ArrayLists already :slight_smile: But I won’t give up!

Thanks for all the help, really helps me.

java ArrayLists and std::vectors are almost the same…

For what you need you can use typeid without problem, or try this:

  
  
#define CAT=0  
#define DOG=1  
  
class Animal{  
public:  
     int animal_type;  
}  
  
class Dog : public Animal{  
public:  
    Dog(){  
      animal_type=DOG;  
    }  
}  
  
class Cat: public Animal{  
public:  
   Cat(){  
       animal_type=CAT;  
   }  
}  

On the delete topic:

You’ll want each class in your hierarchy to have a virtual destructor, otherwise you will again leak memory:

  
  
class Animal {  
   virtual ~Animal();  
};  
  
class Cat : public Animal {  
   virtual ~Cat();  
};  
  
class Dog : public Animal {  
   virtual ~Dog();  
};  
  

For getting the proper subclass pointer, the “proper” C++ method is:

  
  
Animal *a = new Cat();  
Cat *c = dynamic_cast<Cat *>(a);  
  

If this fails, you will get NULL. See http://publib.boulder.ibm.com/infocenter/lnxpcomp/v8v101/index.jsp?topic=/com.ibm.xlcpp8l.doc/language/ref/keyword-dynamic-cast.htm

[/code]

Another thing about vector<Object *> versus vector. The latter you have to be careful with in terms of calls to the copy constructor. For anything but the most trivial objects like ofVec3, I would use the pointer version. If you did say vector, you will most likely end up in a world of pain because the copy constructor will be invoked a lot unless you’re very careful and even then it’s impossible to avoid it being called at least once.

For instance

  
  
vector<Object> v;  
v.push_back(Object());  
  

This will call the copy constructor _after_ Object() has been called and created a new object, so you will be duplicating things. Once it’s in there however, you can use vector::iterator to get at it without invoking the copy constructor.

It’s instructive to write a simple class with print statements in the constructor, destructor, copy constructor, and assignment operator functions to see exactly what happens under different conditions with respect to vector<>.

[quote author=“otherside”]Another thing about vector<Object *> versus vector. The latter you have to be careful with in terms of calls to the copy constructor.

It’s instructive to write a simple class with print statements in the constructor, destructor, copy constructor, and assignment operator functions to see exactly what happens under different conditions with respect to vector<>.[/quote]

Thanks for the heads up on this. We indeed tried print statements on the following example we recently created to explore vectors (cf. http://forum.openframeworks.cc/t/vector-amp;-list-examples/619/0) and we noticed all those extra copies in the vector version (but not in the list version). Now I know where this was coming from.

Ok, with all your help I managed to use vectors nicely. I will make a simple example and post it here, because I’m pretty sure other beginners will have to tackle this too.

I have one last question about vectors and memory management. I asked if I needed to free vectors explicitly in class destructors, and got the impression that I needed to clear the contents and free the memory by hand.

I’ve searched through the net and actually found out that, vector memory is freed when they fall out of scope just like primitives, and since I’m not declaring vectors by “new”, there is no way for me to “delete” them right? And all resources I could find states that clearing the vector does NOT free the memory it uses but just erases the contents. This is not a problem for me when it is in scope though, but after deleting its owner class, if it doesn’t get freed, then I’d be in trouble.

hey pyramind, I’ve been following this thread and have realised how negligent I’m being with memory so I really look forward to seeing that example.

thanks everybody for the great insights!

I’ve searched through the net and actually found out that, vector memory is freed when they fall out of scope just like primitives

About this, you have to diferenciate where you create things. actually there are two memory zones: the stack and the heap

When you declare a variable like:

  
int a;  

or

  
  
vector<Animal*> animals;  

you’re creating that variables in the stack, every object and function has it’s own stack that it’s automatically deleted when the function returns or the object is destroyed. So you don’t have to worry about memory in the stack.

But when you do:

  
  
vector<Animal*> * animals;  
animals = new vector<Animal*>;  

you’re actually creating the vector in the heap (with a reference/pointer to it in the stack). Note that in the stack you don’t need new, in the heap you need it. The heap is common to every object, function… so you can share data between diferent scopes without copying it once and again, so when you create something there you have to manually delete it.

That’s why I told, about that general rule: a delete for every new.

Hope that clears things out.

1 Like

This is an old thread, but I just came across something helpful.

In Processing you can say println(myVector); and it will print out the values of the vector. STL doesn’t overload the << operator for vector, though, so you can’t just say cout << myVector; What you can do instead is say:

  
  
vector<int> myVector;  
...  
copy(myVector.begin(), myVector.end(), ostream_iterator<int>(cout, " "));  
  

And this will print out the values of myVector with spaces between them.

Also, Zach – you had a question above about getting the type out of something stored as a pointer inside an STL collection. Friedrich is right about typeid, but I read about a good pattern for this recently called “handles” that solves the memory management issue. I’m using it for ofxSvg here:

http://code.google.com/p/kyle/source/browse/trunk/openframeworks/addons/ofxSvg/src/ofxSvgCommandHandle.h

The handle class has a pointer inside it, and implements a few things like operator=, the copy constructor, and the destructor. This way you can have a vector and you can pass xHandle objects around without worrying about the associated pointers getting mixed up.