basic types

Posted on 1999-01-25
Last Modified: 2010-04-02
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.

Question by:alfino
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 5
  • 4

Accepted Solution

MaDdUCK earned 720 total points
ID: 1185087
answer pending...
LVL 86

Expert Comment

ID: 1185088
MaDdUCK - an interesting answer... Hunting points?

Expert Comment

ID: 1185089
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
Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!


Expert Comment

ID: 1185090
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.
LVL 86

Expert Comment

ID: 1185091
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.

LVL 86

Expert Comment

ID: 1185092
>>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 ;-)


Author Comment

ID: 1185093
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...

Expert Comment

ID: 1185094
und von wo aus dem Schwabenländle? Bin zwar gerade in Amerika-land, aber dennoch eigentlich in Bayern zu Hause...
LVL 86

Expert Comment

ID: 1185095
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 **
LVL 86

Expert Comment

ID: 1185096
>>jkr: do you want points too? if so, I could ask Linda to
If you think i earned some ;-)

Featured Post

[Webinar] Learn How Hackers Steal Your Credentials

Do You Know How Hackers Steal Your Credentials? Join us and Skyport Systems to learn how hackers steal your credentials and why Active Directory must be secure to stop them. Thursday, July 13, 2017 10:00 A.M. PDT

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

In days of old, returning something by value from a function in C++ was necessarily avoided because it would, invariably, involve one or even two copies of the object being created and potentially costly calls to a copy-constructor and destructor. A…
IntroductionThis article is the second in a three part article series on the Visual Studio 2008 Debugger.  It provides tips in setting and using breakpoints. If not familiar with this debugger, you can find a basic introduction in the EE article loc…
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
The viewer will learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.

690 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question