2

I recently wrote my first program from the ground up, but being not a professional of the field, I fear I might not have used the most appropriate solution.

In my program I have to use lists (and lists of lists) of objects in which I continuously add and remove elements, not necessarily at the beginning or end of the lists.
Using lists of pointers is not an option, giving the requirements.

When I started I knew only the std::vector class and thus I used it, despite knowing that it requires contiguous memory and thus this choice would have caused repeated re-allocations.
While trying to solve another problem I discovered that there exist other classes that might be better suited for this task, such as std::list and std::deque.

I mostly access the objects by the use of indexing

myvector[index].function();

and the standard functions that I use the most are

myvector.size();
myvector.begin();
myvector.pop_back();
myvector.push_back();
myvector.insert(myvector.begin()+offset, number, new_element);

and I haven't overloaded any function/operator.

Could you suggest the best container/doubly-linked list for my scope?
Is it possible to seamlessly substitute std::vector with any other standard container?
Are there special issues I have to pay attention to?

Matthieu M.
  • 287,565
  • 48
  • 449
  • 722
Federico
  • 1,092
  • 3
  • 16
  • 36
  • Most `std::vector` implementations are pretty smart, and pre-allocates memory so it doesn't need to do reallocations every time you add or remove an element. And before worrying about performance, *benchmark*! – Some programmer dude Jun 05 '13 at 07:27
  • 1
    And yes, all standard container have almost the same interface so changing to another for benchmarking should be easy. I also recommend a reference [such as this](http://en.cppreference.com/w/cpp/container) (where you can find a nice table of supported finctions for each container). – Some programmer dude Jun 05 '13 at 07:29
  • possible duplicate of [Relative performance of std::vector vs. std::list vs. std::slist?](http://stackoverflow.com/questions/238008/relative-performance-of-stdvector-vs-stdlist-vs-stdslist) – TemplateRex Jun 05 '13 at 07:31
  • @rhalbersma: I do not think, my question is not related to performance, but to appropriate use of `std` library classes. @who voted -1: may I ask why? – Federico Jun 05 '13 at 07:40
  • @JoachimPileborg but note also Scott Meyers's advice "Beware of container independent code" (item 2 of Effective STL), where he explains that the intersection of multiple container interfaces pretty quickly goes to zero. – TemplateRex Jun 05 '13 at 07:41
  • 1
    @Federico I downvoted because you did insufficient research effort. The question is valid but has been asked here before, which you could have found out with a little searching. You cite performance concerns, as well as usage concerns. The performance concerns are addressed in the link I gave earlier, and the container selection is discussed [here](http://stackoverflow.com/questions/471432/in-which-scenario-do-i-use-a-particular-stl-container?lq=1) – TemplateRex Jun 05 '13 at 07:44
  • @rhalbersma: understood. I searched for the second, but haven't found it. The first, I was not searching for it. – Federico Jun 05 '13 at 07:50
  • If you're using myvec[index] only in a loop, you might look instead to iterators. As the others have said, don't pour work into something that isn't a problem; however, in general, middle insertions are best done in a list rather than a vector, depending on what else you're using the data structure for. – Joel Jun 05 '13 at 07:52
  • @Federico: on top of rhalbersma's chart, I proposed a revised version in C++11 [here](http://stackoverflow.com/questions/10699265/how-can-i-efficiently-select-a-standard-library-container-in-c11/10701102#10701102), with rationales to explain the choices. – Matthieu M. Jun 05 '13 at 08:06
  • @Joel even the middle insertion argument has to be considered carefully. If you care about iterator invalidation, then yes, use `list` or even `forward_list`. Otherwise, profile, because there are many factors involved. – juanchopanza Jun 05 '13 at 09:56
  • As noted: don't pour work into something that isn't a problem – Joel Jun 05 '13 at 18:13

2 Answers2

4

Could you suggest the best container/doubly-linked list for my scope?

If you access elements by index, a linked list is not a good solution: you have to traverse the list from the beginning, so it is an O(N) operation. And for this reason, std::list and std::forward_list have no such access in their interface.

Is it possible to seamlessly substitute std::vector with any other standard container?

Not with an std::list, since it has no access by index. std::deque could be suitable, but only if you do not rely on the underlying data being in one continuous block (I assume you don't, since you are asking about linked lists)

Are there special issues I have to pay attention to?

As always with performance, you should first be sure whether you have a problem or not. If you have a performance issue with std::vector, then try something else, and measure the difference in performance in a realistic running scenario. The performance characteristics of different containers can be quite counter intuitive, so measuring is specially important here.

Related links: std::vector vs. std::list vs. std::deque comparison. Bjarne Stroustrup's Going Native 2012 keynote speech.

juanchopanza
  • 223,364
  • 34
  • 402
  • 480
  • Thanks for the answer! "If you access elements by index, a linked list is not a good solution" -> could you propose an alternative? (on the accessing side) The main issue here is the size of the objects, every time I create a new one a decent chunk of memory is needed. – Federico Jun 05 '13 at 07:34
  • 2
    @Federico my alternative would be to use an `std::vector` unless I am 100% sure that there is a problem. Then try with `std::deque`. If there are still problems,either re-design your types so they are cheap to move and have a small size (e.g. they wrap some dynamically allocated memory, as most std library types do). Or store `std::unique_ptr` of your type. – juanchopanza Jun 05 '13 at 07:42
  • One note: `std::deque` is nearly as bad as `std::vector` when it comes to insertion in the middle (moves half the elements at most compared to potentially all elements). – Matthieu M. Jun 05 '13 at 07:59
2

There is one alternative offered by Boost: boost::stable_vector.

The Big O complexity is strictly identical for all operations, however internally it does not shuffle elements but pointers (at the cost of losing contiguity).

For the cost of one extra indirection at each access, stable_vector is a good alternative in two situations:

  • you want to have a stable address for the elements, so you can keep a reference/pointer to it
  • the element is extremely costly to copy, so you want to be guaranteed no copy will take place whatever the operations you are doing

The latter should be substantiated with a profiler pointing out the issue, obviously.

Matthieu M.
  • 287,565
  • 48
  • 449
  • 722