A uniform container whose type is known only at runtime

Question

I have a collection of the same type , the type of which is known only at runtime. Once a type is defined, it will never change. I am currently saving pointers to objects in a vector, for example:

std::vector<Animal*> v; 

I am wondering if it is possible to store instances in continuous memory. My intention is to write code that is more convenient for caching and faster iterate through the container.

I could use boost :: variant for each vector element, e.g.

 std::vector<boost::variant< Cat, Dog > > 

but if sizeof(Dog) much larger than sizeof(Cat) , then there is memory loss when the objects are of type Cat .

I could also use the container option:

 boost::variant< std::vector<Cat>, std::vector<Dog> > 

but I don’t know how the iterators will be in this case, and if they will introduce additional overhead.

Is a "pointer vector" the best we can do?

Additional information: the sizes of the objects are from 50 to 250 bytes, and the length of the containers is from 10 to 1 M elements, and I have to sort the container through a million times.

Thanks.

EDIT : here I found a similar question (with good suggestions too): How to write caching polymorphic code in C ++?

Answer 1

Right - rewrite here and much easier.

I agree with s3rius that you should still use std :: vector. Ideally, if you keep cats, you will use ...

 std::vector<Cat> 

and if you keep dogs, you would like ...

 std::vector<Dog> 

However, you need run-time polymorphism to choose which case you are dealing with.

One way (or inspired) by a strategy design pattern. Define a base class for your interface for these vectors and create a template class that implements this interface containing the vector.

 class Animals_IF { public: virtual int size () const = 0; }; template<typename T> class Animals_Vector { private: std::vector<T> store; public: int size () const; }; template<typename T> int Animals_Vector<T>::size () const { return store.size (); } 

The problem here is that the interface cannot mention Cat or Dog because it does not know the specific type, which, of course, is why I chose size as the approximate method above.

One solution is to pass values ​​using boost::variant possible types, so each of the strategy / wrapper classes can verify that the values ​​it receives are the correct type before using them. Wrapping / unfolding values ​​in a variant can be processed using template methods in the base class (without a template).

In cases where all that wrapping and unpacking becomes ineffective, you must determine what case you are dealing with, and then call the correct type of strategy / shell (and not the base class). To do this, use boost :: variant of all strategy / shell cases. This does not prevent you from having a pointer to the base class. In fact, wrap both the pointer-base-class and boost::variant classes in the class (use template methods if necessary).

 class Animals_IF { public: typedef boost::variant<Cat,Dog> Animal; virtual int size () const = 0; template<typename T> void slow_push (const T &p) { push_ (Animal (p)); } private: virtual void slow_push_ (const Animal &p) = 0; }; template<typename T> class Animals_Vector { public: int size () const; void fast_push (const T &p); private: std::vector<T> store; void slow_push_ (const Animal &p); }; template<typename T> int Animals_Vector<T>::size () const { return store.size (); } template<typename T> void Animals_Vector<T>::fast_push (const T &p) { store.push (p); } template<typename T> void Animals_Vector<T>::slow_push_ (const Animal &p) { const T* item = boost::get<T> (&p); if (T) store.push (*item); // else throw? } class Animals { public: int size () const { // null check needed? return ptr->size (); } template<typename T> void slow_push (const T &p) { // null check needed? ptr->slow_push (p); } template<typename T> void fast_push (const T &p) { Animals_Vector<T> *lptr = boost::get<T> (&store); if (lptr) lptr->fast_push (p); // else throw? } private: Animals_IF* ptr; boost::variant<Animals_Vector<Cat>,Animals_Vector<Dog>> store; }; 

If there is nothing that a common interface can provide (since each method must pass values, and packaging / expanding as options is unacceptable), the whole strategy is not needed. Just use boost :: variant for different types of std :: vector.

Also, the above fast_push won't be fast because push too easy to use - the idea is that this approach is faster for complex methods that can avoid re-checking the type of runtime by doing it once, front-end.

By the way - a good question.

Answer 2

I will return my comment in return.

I would say that it’s best to put all dogs in vector<Dog> and all cats in vector<Cat> , and then iterate over them individually. This way you can keep each vector optimally packed.

With some CRTP, you can automate it to make it easier to add more animals without problems.

Example:

 template <typename T> class Container{ public: static std::vector<T> m_elements; //static vector will contain animals //overloaded operator new adds the Animal to m_elements void* operator new(size_t){ m_elements.push_back( T{} ); return &m_elements[m_elements.size() - 1]; } }; template <typename T> std::vector<T> Container<T>::m_elements; //some example animals class Dog : public Container<Dog>{ public: std::string woof; Dog( char* s = "woof" ){ woof = s; } }; class Cat : public Container<Cat>{ public: std::string meow; Cat( char* s = "meow" ){ meow = s; } }; int main(){ new Dog( "woof" ); new Dog( "rrawoof" ); new Cat( "meow" ); new Cat( "meweeow" ); //easy iteration for( auto dog : Dog::m_elements ) std::cout << dog.woof << "\n"; for( auto cat : Cat::m_elements ) std::cout << cat.meow << "\n"; std::cout << "end"; } 

Whether it is recommended to overload new or not is another question, but it is good for showing.