[HeartyBowl]

If you will be constantly inserting numbers in a descending order, what would be more efficient memory wise?
a vector or a list?

[r.stiltskin]

Is this a test question? What do you think?

[HeartyBowl]

yes this was a question on my test and I'm having doubts and i don't want to wait a week to find out if i got it wrong. the anxiety is killing me!

My answer was that a list was a better choice because a vector is implemented as a dynamic array. and whenever a vector exceeds its capacity, it creates a new array with bigger memory. and i think i remember hearing my teacher say that lists are better for sorting and such but i could be wrong...

so am i wrong/right?

[Oler1s]

Maybe you should think of it this way. Find the most efficient way to use a vector. Then find the most efficient way to use a list. Now compare te two.

[turboscrew]

List: hashing.

[Crunch]

HeartyBowl, on 18 May 2012 - 03:43 AM, said:

lists are better for sorting

Lists are implemented as as doubly-linked lists. Therefore you cannot have direct access as in like vector's. This suggests that lists are less efficient than vectors when using sorting algorithms that requires direct access.

This post has been edited by Crunch: 18 May 2012 - 06:09 AM

[sepp2k]

HeartyBowl, on 18 May 2012 - 02:39 AM, said:

If you will be constantly inserting numbers in a descending order, what would be more efficient memory wise?
a vector or a list?

What do you mean by inserting in a descending order here? Do you mean you insert the last item first, then the second to last, ..., then the first, i.e. you're adding items to the front instead of the back? Or do you mean that each number that is added will be less than the one before it (how would that affect memory efficiency though?)? Or do you mean that you add numbers in arbitrary order and the list should remain sorted (descendingly)?

Quote

My answer was that a list was a better choice because a vector is implemented as a dynamic array. and whenever a vector exceeds its capacity, it creates a new array with bigger memory

In common implementations of vectors, the capacity of a vector will be at most doubled when exceeded. That is to say the memory consumed by a vector will be at most twice the memory needed to store all its elements.

Each node in a doubly linked list (such as C++'s list) contains two pointers and the element itself. Since the elements in question here are numbers, we can assume that the size of an element will not be greater than the size of a pointer. Let's assume for the sake of argument that the size of a pointer is equal to the size of the numeric type you're storing. In that case a linked list will consume three times the memory needed to store all of its elements.

So linked lists are not more memory efficient than dynamic arrays.

turboscrew, on 18 May 2012 - 02:42 PM, said:

List: hashing.

Could you elaborate on that? What do lists have to do with hashing?

Also in what context does hashing reduce memory consumption?

Crunch, on 18 May 2012 - 02:59 PM, said:

HeartyBowl, on 18 May 2012 - 03:43 AM, said:

lists are better for sorting

Lists are implemented as as doubly-linked lists. Therefore you cannot have direct access as in like vector's. This suggests that lists are less efficient than vectors at sorting.

It doesn't really suggest that - at least not obviously. Yes, random access is inefficient on lists, but not all sorting algorithms require random access - in fact most don't (quick sort requires random access if you want to use a random pivot only (though since you really should use a random pivot, quick sort isn't really the algorithm you'd use for a linked list) and merge sort doesn't require random access at all).

[turboscrew]

What I meant, hash-tables are typically implemented as a vector of lists (or map of lists). Finding is quite fast and only used elements need to be present.

This post has been edited by turboscrew: 18 May 2012 - 10:10 AM

[HeartyBowl]

dang... looks like i got this one wrong

[ishkabible]

actually based on some test I saw from Bjarne stroustrup, std::list is actually basically always slower than a vector or deque(which to me at least makes sense given all the allocation and added non-sense a list has). the difference is that a list's iterators and element references are not invalidated by operations. there is an algorithmic difference in the two; you use a list when you need to maintain references to the elements.

as an aside related the topic of sorting...
merge sort can be done in-place with linked with linked lists while maintaining the same time complexity, hence it's really good at sorting lists.

This post has been edited by ishkabible: 18 May 2012 - 03:33 PM

[sepp2k]

ishkabible, on 19 May 2012 - 12:24 AM, said:

actually based on some test I saw from Bjarne stroustrup, std::list is actually basically always slower than a vector or deque(which to me at least makes sense given all the allocation and added non-sense a list has).

I'm sure that's not true for all kinds of operations. For example inserting a bunch of elements in the middle of the list is almost certainly slower on an array or a deque than on a linked list.

[ishkabible]

yes, that's true if you were able to have the middle iterator in the first place(which in some algorithms this would be known). it rarely happens that you just magically, as a side effect of another operation, have an iterator to a desired spot(or close to the spot) in the list. hence this issue didn't fall into 'basically'. that's why I said 'basically'.

if you're talking about inserting an element after the Nth position then a vector is faster actually becuase traversal of half a linked list is slower than moving half an array due to cache misses and the fact it takes like 2-5 instructions for a linked list to increment an iterator where it only takes 1 instruction(a 1 cycle increment at that) to increment an iterator of a vector; that part is sketchy with a deque sense a deque can be broken up into separate parts. there are also special instructions for moving trivially moveable/copyable elements over that memmove uses making this operation even faster in many cases. this still doesn't take into account the cost of the allocation of the linked lists nodes.

so if you're algorithm has some sort of side effect that gives you the middle iterator then yes, it's much faster. the cost of allocating the node of a linked list would probably mean that smaller vectors(like 500 integers or less) would be faster than a linked list.

there are other cases too, they just are not very common. Bjarne's advice was to always start with a vector(if it worked, sometimes you might need a deque) and if there was a need for optimization then try out a list, deque, stack, queue, etc... it might help in your case.

edit:
note, the tests Bjarne did used move semantics. in C++98/03 this wasn't necessarily true if the objects where large enough. with move semantics is basically(there I go with that word again) always true. if the move constructor was sufficiently expensive then a list might start to overtake a vector.

This post has been edited by ishkabible: 18 May 2012 - 05:23 PM

[HeartyBowl]

Hey guys. it turns out my gut feeling, linked lists, was correct after all.
I emailed my professor and asked her why linked lists was correct and why some users thought a vector was more efficient.
I thought I'd post her response for those who are interested. She responded with:

"Hi,

The correct answer is linked list. Those who said that you should choose a vector are probably thinking about binary search, in which case it would be more efficient to have a vector, because you are only searching. But if you need to insert it is a different story. If you use a vector, you can choose the correct position where to insert by doing a binary search, but when you need to make space for the new item, then the vector will need to shift the rest of the items to a new position and possibly re-size the vector, which might end up being O(log n)(search) + O(n)(shifting/possible re-size) + O(1)(insertion). If you use a linked list, then the worst case will simply be O(n)(search) + O(1)(insertion).

You need to remember that there is a good number of programmers who might be very good at knowing lots of syntax but know very little about efficiency."

[Skydiver]

Okay, I'm confused. In the OP the question was:

Quote

If you will be constantly inserting numbers in a descending order, what would be more efficient memory wise?
a vector or a list?

So which data structure is more efficient in terms of memory, not operations. The teacher's response was in the context of operations.

Looking at it in terms of memory it'll if you have N-items, you'll have to take into account the space used by least N+1 pointers plus the space used by N items themselves. This is opposed to a vector which will be the space used by N items plus a pointer to the vector, and an integer to keep track of the current size of the vector. The vector looks more efficient, at least for a static structure.

Taking into account the context of always inserting items, then it'll depend on the growth pattern of the vector (either always grow by 1 as needed, or preallocate X where X is either a N * 2, N * 1.5, or some other heuristic) as opposed to the linked list which will always be growing by just N + the number of link pointers (either 1 or 2 depending on whether it is a single or double linked list). So thing are looking better for the linked list because the "fill ratio" is much better, but that is not taking into account what the memory manager is doing for the runtime library. If it's a naive memory manager, then the linked list will be subject to fragmentation within the heap where some sections may not be usable because of the size of the N separate items, while the vector will have nice contiguous blocks of usable memory.

And then there is also the issue of memory cache coherency. There is a higher probability that the items accessed in the vector will be in the memory cache because of the contiguous blocks, as opposed to the linked list which will be jumping all over the place if the memory manager didn't keep like sized allocations close to each other.

To me, it is still looking like the vector is doing better than the linked list.

Now in terms of operations versus memory, then I do accept the teacher's response, because you'll have to keep moving memory around with a vector to do inserts, where as the linked list will just have to adjust pointers.

So what am I missing? Did I misinterpret the question in the OP? Or is there another cost to the vector that makes the link list win out memory wise?

This post has been edited by Skydiver: 01 June 2012 - 05:42 PM

[HeartyBowl]

I can't remember the exact test question. I made this thread 2 days after the test so I could not remember how the question was asked. Maybe it said "which has a more efficient runtime"? But you can assume that we will be constantly inserting numbers or whatever in a descending order. From my teacher's response, it seems like the linked list is the way to go because the runtime/o-notation is faster for the linked list.