- Forum
- General C++ Programming
- Design Question - Choice of container
Design Question - Choice of container
Hello all,
I am working on an assignement where i have to collect objects in a container. I will have a decent number of these objects in my container (about a thousand) and these objects will have some attributes of type int, double, string.
The requirements are to use an STL container and being able to sort the objects (using a STL "sort" function) based on one of its attributes (can be the string, can be the int, etc..).
My question is: What would be your choice of container? For the moment i am thinking of using the list container and use the sort function (there is an example of its use on this very site, thanks for that by the way).
Remark: There is an initial upload of objects, and from there there will be limited changes (there won't be any changes to the objects' individual attributes).
Another question: should i really have the "main" container sorted? or should i have another "temporary" container to which the sort function outputs the result? the goal here is only to output the result of the sort to the screen or to a file..
Many thanks in advance!
AS
I am working on an assignement where i have to collect objects in a container. I will have a decent number of these objects in my container (about a thousand) and these objects will have some attributes of type int, double, string.
The requirements are to use an STL container and being able to sort the objects (using a STL "sort" function) based on one of its attributes (can be the string, can be the int, etc..).
My question is: What would be your choice of container? For the moment i am thinking of using the list container and use the sort function (there is an example of its use on this very site, thanks for that by the way).
Remark: There is an initial upload of objects, and from there there will be limited changes (there won't be any changes to the objects' individual attributes).
Another question: should i really have the "main" container sorted? or should i have another "temporary" container to which the sort function outputs the result? the goal here is only to output the result of the sort to the screen or to a file..
Many thanks in advance!
AS
Choice of container is always dependent upon requirements and usage.
You've mentioned that you need to sort the container and you've mentioned that it will have about 1000 elements. You did not say if you need to insert elements at the front, end, or in the middle. You did not say if you need to remove elements from the front, end, or the middle. You did not say if you need to find elements. All of these questions will help determine the best container to choose.
Assuming inserts at the end only, no removes, and no lookups:
std::sort() implements a quicksort. Quicksort operates on ranges of elements such as the 5th through 8th elements. This type of access is called "random access". If you pass random access iterators to std::sort(), "finding" the nth element is a matter of a single addition. If you don't pass a random access iterator, the algorithm has to approximate one by using std::advance(), which simply increments the "begin" iterator N times to get to the Nth element. This is painfully slow.
Not all containers provide random access iterators. std::vector and std::deque both provide them; the rest do not. Therefore, given my assumptions, I would go with one of those. Which one? std::vector<> is best when you know exactly how many elements will be in the container or can at least put an upper bound on it. Why? Because std::vector<> allocates memory for 1 element until you insert the second, at which time it has to reallocate and copy. In this fashion, to build a vector of 1024 elements, 10 reallocations will be performed and you will copy 1023 elements needlessly to insert 1024. So it is always best to use std::vector<>::reserve, which reserves enough memory for the number of elements you specify. (Note: inserts at the front and middle of a std::vector<> is O(n); at the end is O(1) assuming the vector has memory, or O(n) if it has to reallocate).
std::deque<> is best when you don't know the number of elements or can't put a reasonable upper bound on it. When the deque needs to allocate more memory, no copies are necessary.
You've mentioned that you need to sort the container and you've mentioned that it will have about 1000 elements. You did not say if you need to insert elements at the front, end, or in the middle. You did not say if you need to remove elements from the front, end, or the middle. You did not say if you need to find elements. All of these questions will help determine the best container to choose.
Assuming inserts at the end only, no removes, and no lookups:
std::sort() implements a quicksort. Quicksort operates on ranges of elements such as the 5th through 8th elements. This type of access is called "random access". If you pass random access iterators to std::sort(), "finding" the nth element is a matter of a single addition. If you don't pass a random access iterator, the algorithm has to approximate one by using std::advance(), which simply increments the "begin" iterator N times to get to the Nth element. This is painfully slow.
Not all containers provide random access iterators. std::vector and std::deque both provide them; the rest do not. Therefore, given my assumptions, I would go with one of those. Which one? std::vector<> is best when you know exactly how many elements will be in the container or can at least put an upper bound on it. Why? Because std::vector<> allocates memory for 1 element until you insert the second, at which time it has to reallocate and copy. In this fashion, to build a vector of 1024 elements, 10 reallocations will be performed and you will copy 1023 elements needlessly to insert 1024. So it is always best to use std::vector<>::reserve, which reserves enough memory for the number of elements you specify. (Note: inserts at the front and middle of a std::vector<> is O(n); at the end is O(1) assuming the vector has memory, or O(n) if it has to reallocate).
std::deque<> is best when you don't know the number of elements or can't put a reasonable upper bound on it. When the deque needs to allocate more memory, no copies are necessary.
Thanks jsmith, your answer is very helpful. I am sorry for not having provided more information but i did not realize all those questions were important (still a long way to go before i can call myself a programmer).. duly noted!
AS
AS
That's quite alright. The fact that you showed enough insight to give the information you gave speaks well to your future as a programmer.
Topic archived. No new replies allowed.