alfino
asked on
basic types
could someone please explain to me the differences between the types
vector, list, map, multimap, queue, priority queue, stack, and deque?
this is not for homework, but I am trying to figure out some basic c++ for myself.
thanks
vector, list, map, multimap, queue, priority queue, stack, and deque?
this is not for homework, but I am trying to figure out some basic c++ for myself.
thanks
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
jkr
MaDdUCK - an interesting answer... Hunting points?
alfino,
this is not easy to answer for all the types you addressed are basically arrays (except for multimap) that are optimized for different purposes and actions. Such actions include subscripting, adding, deleting, pushing and popping, sorting, etc. I will run through your list and try my best:
vector: the easiest, comparable to an [] arry of C but with range checking. Optimized for subscripting (vector::at() and vector::operator[]()).
list: like a vector, but optimized for addition, insertion, and deletion. Subscripting is painfully slow and not provided. Lists are easy to sort, split, and merge though.
stack: imagine a stack of papers. the principle "first in last out" applies here. The paper that you put down first (the one at the bottom) is taken out last. Stacks are used for hierarchies and are optimized for pushing and popping (adding and deleting the upper-most element). Sorting and other order-changing operations are not supported, and subscripting and insertions make no sense.
queue: like a supermarket queue: first in first out. The person first in the line (queue) will be first out. Pushing (adding to one end) and popping (removing from the oother) are provided.
deque: like a queue except that popping and pushing can occur on both sides of the queue.
priority queue: like a queue, except that each member can have a priority. this is comparable to a print queue where some documents, although submitted later have to be printed before others.
map and multimap: these are hashes, meaning that they associate pairs like a two-column table. Sometimes they are referred to as dictionaries. They are optimized for search, addition and deletion, and are automatically sorted. A multimap can have multiple entries for one key, a map can only have one value for one specific key.
so I hope this helps and I did not leave anything out.
\\MaD dUCK
this is not easy to answer for all the types you addressed are basically arrays (except for multimap) that are optimized for different purposes and actions. Such actions include subscripting, adding, deleting, pushing and popping, sorting, etc. I will run through your list and try my best:
vector: the easiest, comparable to an [] arry of C but with range checking. Optimized for subscripting (vector::at() and vector::operator[]()).
list: like a vector, but optimized for addition, insertion, and deletion. Subscripting is painfully slow and not provided. Lists are easy to sort, split, and merge though.
stack: imagine a stack of papers. the principle "first in last out" applies here. The paper that you put down first (the one at the bottom) is taken out last. Stacks are used for hierarchies and are optimized for pushing and popping (adding and deleting the upper-most element). Sorting and other order-changing operations are not supported, and subscripting and insertions make no sense.
queue: like a supermarket queue: first in first out. The person first in the line (queue) will be first out. Pushing (adding to one end) and popping (removing from the oother) are provided.
deque: like a queue except that popping and pushing can occur on both sides of the queue.
priority queue: like a queue, except that each member can have a priority. this is comparable to a print queue where some documents, although submitted later have to be printed before others.
map and multimap: these are hashes, meaning that they associate pairs like a two-column table. Sometimes they are referred to as dictionaries. They are optimized for search, addition and deletion, and are automatically sorted. A multimap can have multiple entries for one key, a map can only have one value for one specific key.
so I hope this helps and I did not leave anything out.
\\MaD dUCK
I just want to be sure that if I spend all the time and effort to answer it that noone else will have proposed an answer before I can. I don't think that the method used was inappropriate or against the rules.
alfino - the best descriptions for this are available in Bjarne Stoustroup's book on C++, 'The C++ Programming language', Addison-Wesley. I have to admit that i thought of copying and pasting the descriptions from my online documentation, but that'd be a strange way to earn points ;-)
BTW - That's what most of the explanations you'll get here will contain:
vector: describes an object that controls a varying-length sequence of elements. The sequence is stored as an array.
list: describes an object that controls a varying-length sequence of elements. The sequence is stored as a bidirectional linked list of elements.
map: describes an object that controls a varying-length sequence of elements. The first element of each pair is the sort key and the second is its associated value. The sequence is represented in a way that permits lookup, insertion, and removal of an arbitrary element with a number of operations proportional to the logarithm of the number of elements in the sequence (logarithmic time). Moreover, inserting an element invalidates no iterators, and removing an element invalidates only those iterators that point at the removed element.
BTW - That's what most of the explanations you'll get here will contain:
vector: describes an object that controls a varying-length sequence of elements. The sequence is stored as an array.
list: describes an object that controls a varying-length sequence of elements. The sequence is stored as a bidirectional linked list of elements.
map: describes an object that controls a varying-length sequence of elements. The first element of each pair is the sort key and the second is its associated value. The sequence is represented in a way that permits lookup, insertion, and removal of an arbitrary element with a number of operations proportional to the logarithm of the number of elements in the sequence (logarithmic time). Moreover, inserting an element invalidates no iterators, and removing an element invalidates only those iterators that point at the removed element.
>>I don't think that the method used was inappropriate or
>>against the rules.
I don't either - but it's unusual, anyway ;-)
PS: Gruß aus Schwaben ;-)
>>against the rules.
I don't either - but it's unusual, anyway ;-)
PS: Gruß aus Schwaben ;-)
ASKER
thanks both of you. i got what i wanted (a description and a reference) from both of you so I am happy.
jkr: do you want points too? if so, I could ask Linda to split...
jkr: do you want points too? if so, I could ask Linda to split...
und von wo aus dem Schwabenländle? Bin zwar gerade in Amerika-land, aber dennoch eigentlich in Bayern zu Hause...
Tja, Heilbronn hier, bin aber ein Bayer in der Diaspora ;-)
Da das ja eine (recht teure) PAQ ist, kann ich ja 'mal sorglos meine email posten (mach' ich sonst nich' ;-) - erreichbar unter
** email address removed by Netminder, EE Admin **
Da das ja eine (recht teure) PAQ ist, kann ich ja 'mal sorglos meine email posten (mach' ich sonst nich' ;-) - erreichbar unter
** email address removed by Netminder, EE Admin **
>>jkr: do you want points too? if so, I could ask Linda to
>>split...
If you think i earned some ;-)
>>split...
If you think i earned some ;-)