Hi,
I'm wondering what the benefits of using list<t> and array<t> are !?!?!
Well, the array has more functions to work with...
Are there any other differences/benefits of using the one ore the other ???
array vs list
array vs list
while(!asleep) sheep++;
IrrExtensions:
http://abusoft.g0dsoft.com
try Stendhal a MORPG written in Java
IrrExtensions:
http://abusoft.g0dsoft.com
try Stendhal a MORPG written in Java
Ahh, I thought so, a list is faster than an array... 
thx
thx
while(!asleep) sheep++;
IrrExtensions:
http://abusoft.g0dsoft.com
try Stendhal a MORPG written in Java
IrrExtensions:
http://abusoft.g0dsoft.com
try Stendhal a MORPG written in Java
In most cases array is faster or equally fast, but it really depends on your overall container usage. List is faster when you delete/insert items in the middle.
array has the huge advantage, in that you have random access to the items within. While in a list you can only hop from item to item. This is for instance why array has sort and list hasn't. Sorting a list is inefficient (bubble sort works ok with it, but else...)
While iterating over all items has the same complexity for both, array is more cache friendly.
An array stores its items in a continuous block of memory. This means, if you delete an item in the middle, all items behind it have to be moved accordingly. Same for deletion. Also if the current size gets larger than the size already allocated, then the array has to be reallocated. A new block is allocated and all data moved there.
Such operations are expensive, it is thus important to guess a good size and set it up-front.
array has the huge advantage, in that you have random access to the items within. While in a list you can only hop from item to item. This is for instance why array has sort and list hasn't. Sorting a list is inefficient (bubble sort works ok with it, but else...)
While iterating over all items has the same complexity for both, array is more cache friendly.
An array stores its items in a continuous block of memory. This means, if you delete an item in the middle, all items behind it have to be moved accordingly. Same for deletion. Also if the current size gets larger than the size already allocated, then the array has to be reallocated. A new block is allocated and all data moved there.
Such operations are expensive, it is thus important to guess a good size and set it up-front.
fully agree with JP.
as for 'addon' i would quote a bit from a good "Addison Wesley: Software Engineering and Computer Games" book, which i've read not so long ago:
as for 'addon' i would quote a bit from a good "Addison Wesley: Software Engineering and Computer Games" book, which i've read not so long ago:
hope, it helps!Should we use a list or an array for our collection of critter pointers? Well, iterating through an array is faster than iterating through a list, but deleting objects is faster with a list than with an array. The cost of deleting something from the middle of an array is noticeable because then all of the higher-indexed array members need to be moved down one position in the array. On the whole, we expect more of our computation time to involve iterations than object deletions, so we'll use an array.
This statement is not necessarily true. You can _usually_ swap the last item in an array with the one that you want to remove, and then remove the last item in the array. As long as the list doesn't have to be sorted...The cost of deleting something from the middle of an array is noticeable because then all of the higher-indexed array members need to be moved down one position in the array
This is only the case with a singly-linked list. Most lists are implemented as doubly-linked lists [with pointers to the first and last node], so access to the front and back of the list is constant time. If it is a singly-linked list [with just a pointer to the first node] then access to the front of the list is constant time and access to the tail is linear time.as with the list you have to iterate through all the elements to get to the end, whereas with the array you have instant access
Travis
-
hybrid
- Admin
- Posts: 14143
- Joined: Wed Apr 19, 2006 9:20 pm
- Location: Oldenburg(Oldb), Germany
- Contact:
Moreover, vector, list, queue, map, etc, are usually only abstract data type concepts for access interfaces to containers. Most libraries (among them the STL) make some assumptions about runtime (usually average times) because otherwise some concepts would not make sense. But no one would prohibit a vector which uses a linked list beneath to speed up intermediate removal of elements.
Unless you count common sense too.hybrid wrote:But no one would prohibit a vector which uses a linked list beneath to speed up intermediate removal of elements.
Most efficient way to implement vector with its traits is a continuous block of memory. Eventhough, the standard doesn't say it explicitly, it is implicitly assumed by STL users, that &myvector[0] returns the address to the first item of the container and all others follow behind. If this wasn't the case, you couldn't hand over a vector to a c function expecting a pointer to a block of memory and a count.