List of object or list of pointers to objects?
-
Hi, I have a class similar to the one below: class CBook{ public: char m_szAuthor[256]; char m_szBookname[256]; long m_nID; }; I need to store a list of thousands of CBook objects. I need to do sorting on the list. Assuming that I am going to use the std::list STL object, would it be better for me to create a list of objects or of pointers? ie: list or list ? What are the advantages/disadvantages of each? Thanks in advance, Jeremy. Jeremy Pullicino C++ Developer Homepage
-
Hi, I have a class similar to the one below: class CBook{ public: char m_szAuthor[256]; char m_szBookname[256]; long m_nID; }; I need to store a list of thousands of CBook objects. I need to do sorting on the list. Assuming that I am going to use the std::list STL object, would it be better for me to create a list of objects or of pointers? ie: list or list ? What are the advantages/disadvantages of each? Thanks in advance, Jeremy. Jeremy Pullicino C++ Developer Homepage
It depends on how 'expensive' copying your objects is. If all you need to coppy is two pointers to strings (
std::stringorCString) and a long int, probably having alist < Book >is OK. But if you need to store a lot of data in your objects, copying around the elements gets expensive. The downside for alist < Book* >is that you need to provide all kind of sorting functionality yourself (as you do not want to sort on your pointers numerical value, but on the property of the underlying object. You end up writing a lot of functors yourself. Maybe you can write some sort of proxy-class, which contains a pointer to a Book-object with all the data, and provides the needed operators to get sorted automatically by the STL-build in routines.operator!=()andoperator<()should be sufficient for sorting. Additionally you would probably need constructor/destructor, copy-constructor and assignment-operator, You would then have the best of both worlds: Transparent working with the proxy-objects and cheap copying.
Who is 'General Failure'? And why is he reading my harddisk?!?
-
It depends on how 'expensive' copying your objects is. If all you need to coppy is two pointers to strings (
std::stringorCString) and a long int, probably having alist < Book >is OK. But if you need to store a lot of data in your objects, copying around the elements gets expensive. The downside for alist < Book* >is that you need to provide all kind of sorting functionality yourself (as you do not want to sort on your pointers numerical value, but on the property of the underlying object. You end up writing a lot of functors yourself. Maybe you can write some sort of proxy-class, which contains a pointer to a Book-object with all the data, and provides the needed operators to get sorted automatically by the STL-build in routines.operator!=()andoperator<()should be sufficient for sorting. Additionally you would probably need constructor/destructor, copy-constructor and assignment-operator, You would then have the best of both worlds: Transparent working with the proxy-objects and cheap copying.
Who is 'General Failure'? And why is he reading my harddisk?!?
Thanks for your quick and comprehensive answer. Are you aware of any such proxy-objects? Perhaps auto_ptr would do the trick? Copying could be quite expensive since much more data could exist in the CBook class. Jeremy Pullicino C++ Developer Homepage
-
Thanks for your quick and comprehensive answer. Are you aware of any such proxy-objects? Perhaps auto_ptr would do the trick? Copying could be quite expensive since much more data could exist in the CBook class. Jeremy Pullicino C++ Developer Homepage
Never ever put an auto_ptr in a standard container. auto_ptr has a funny copy semantic, and you end up with your objects getting deleted while being copied. You could use boosts[^]shared_ptr, which does reference counting and has a more intuitive copy semantic. Or you can simply make your own class: Constructor that takes an Book-object, a few Get/Set functions for the underlying object, assignment-op and copy constructor that deletes its contained object and takes ownership of the new one and a set of operators that access the contained Book-object to determine the sorting sequence.
Who is 'General Failure'? And why is he reading my harddisk?!?
-
Hi, I have a class similar to the one below: class CBook{ public: char m_szAuthor[256]; char m_szBookname[256]; long m_nID; }; I need to store a list of thousands of CBook objects. I need to do sorting on the list. Assuming that I am going to use the std::list STL object, would it be better for me to create a list of objects or of pointers? ie: list or list ? What are the advantages/disadvantages of each? Thanks in advance, Jeremy. Jeremy Pullicino C++ Developer Homepage
All of the sort algorithm's in STL have approximately O(N log N) complexity. Maps on the other hand have an insertion complexity of O(N * log(size() + N)), so it may be quicker to add all of the books to a map, which is always sorted rather than having to do it explicitly. It may depend on the application. SGI STL Complexity[^] jhwurmbach correctly pointed out that using pointers will be cheaper, but missed that the sort algorithms can optionally take a predicate. In cases like this, you are almost always going to use a functor to sort your data based on your criteria. jhwurmbach wrote Maybe you can write some sort of proxy-class. ... Additionally you would probably need ... This isn't really true, raw pointers are fine, you don't need anything extra in the container, the extra stuff will go into the sort criteria function object.
If you can keep you head when all about you Are losing theirs and blaming it on you; If you can dream - and not make dreams your master; If you can think - and not make thoughts you aim; Yours is the Earth and everything that's in it. Rudyard Kipling