471,092 Members | 1,101 Online

# List, set and map

When should I use each of these three containers? What is the
difference?
For list and vector, it is obvious. How about set and map?

Thanks a lot.

Jul 9 '06 #1
5 16164
ju******@gmail.com wrote:
When should I use each of these three containers? What is the
difference?
For list and vector, it is obvious. How about set and map?

Thanks a lot.
A list is a sequence. It has an ordering. Inserts and deletes
are constant time operations (it's effectively a double-linked
list).

Sets and Maps are associative containers. That is, you get
fast (n log n) location of a given element. They effectively
are trees sorted by a key. The difference between set and map
is that set just is a sorted container of single values. Maps
are pairs of keys (which is used for the indexing) and a paired
value.
Jul 9 '06 #2
ju******@gmail.com says...
When should I use each of these three containers? What is the
difference?
For list and vector, it is obvious. How about set and map?
A map has a key, and some data attached to that key. A set only has a
key, with nothing else attached to it.

A couple of examples: if you wanted to print out the words in a file,
sorted into alphabetical order, a set would make sense -- read the
words from the file into a set, then write them out from the set to
the output file.

If you wanted to store data about employees such as their name,
employee ID number, birthday, current pay rate, etc., but wanted to
support looking them up by name, a map would make sense. You'd use
the name as the key, and all the other "stuff" as the data attached
to that key.

Choosing between list and vector might not be as obvious as it
initially appears. It's true that a list supports inserting or
deleting in the middle of the list in constant time. It's also true,
however, that finding that spot in the middle of the list normally
takes linear time. Worse yet, where a vector uses contiguous storage,
a list normally uses non-contiguous storage. That can make it quite
slow to find a particular spot in the list. In a different direction,
std::list requires a doubly-linked list. A list with a lot of nodes
and only a small amount of data in each node can waste a great deal
of memory.

These are useful a lot less often than they might initially appear.
In fact, I'm pretty sure in the 10 years (or so) since I first
started using (then pre-standard) STL, I haven't run into a single
situation where I put an std::list to real use. I've had a couple
that might have been close calls, and I can _imagine_ some where
they'd make but it hasn't arisen in real use for me yet.

--
Later,
Jerry.

The universe is a figment of its own imagination.
Jul 10 '06 #3

"Jerry Coffin" <jc*****@taeus.comwrote in message
news:MP************************@news.sunsite.dk...
ju******@gmail.com says...
These are useful a lot less often than they might initially appear.
In fact, I'm pretty sure in the 10 years (or so) since I first
started using (then pre-standard) STL, I haven't run into a single
situation where I put an std::list to real use. I've had a couple
that might have been close calls, and I can _imagine_ some where
they'd make but it hasn't arisen in real use for me yet.
a list instead of a vector when I don't need to access by
index and I don't know the size ahead of time.

Since vectors maintain contiguous memory, push_backs
can cause a lot of copying if you can't reserve ahead
of time. This is just my opinion.

At the office we constantly have discussions
memory fragmentation. This is sometimes worth
benchmarking though.

If I can reserve the size or if I need to access by
index, I will use a vector. If I can't reserve the
size and don't need to access by index it depends.
Jul 10 '06 #4
Duane Hebert wrote:
"Jerry Coffin" <jc*****@taeus.comwrote in message
news:MP************************@news.sunsite.dk...
ju******@gmail.com says...
>These are useful a lot less often than they might initially appear.
In fact, I'm pretty sure in the 10 years (or so) since I first
started using (then pre-standard) STL, I haven't run into a single
situation where I put an std::list to real use. I've had a couple
that might have been close calls, and I can _imagine_ some where
they'd make but it hasn't arisen in real use for me yet.

a list instead of a vector when I don't need to access by
index and I don't know the size ahead of time.

Since vectors maintain contiguous memory, push_backs
can cause a lot of copying if you can't reserve ahead
of time. This is just my opinion.

At the office we constantly have discussions
memory fragmentation. This is sometimes worth
benchmarking though.

If I can reserve the size or if I need to access by
index, I will use a vector. If I can't reserve the
size and don't need to access by index it depends.
Conventional wisdom dictates that vectors are faster than lists for
"most" purposes. Certainly there are cases where the copying upon
reallocation can be a severe bottleneck, but generally the contiguous
memory storage of vectors and the attendant benefits of spatial locality
provide a significant performance edge over lists.

That said, I often use lists too, notably in situations where I don't
want inserts to invalidate existing iterators.

Jul 10 '06 #5
Duane Hebert wrote:
I sometimes use a list instead of a vector when I don't need to
access by index and I don't know the size ahead of time.

Since vectors maintain contiguous memory, push_backs
can cause a lot of copying if you can't reserve ahead
of time. This is just my opinion.

At the office we constantly have discussions
memory fragmentation. This is sometimes worth
Don't forget std::deque. It has random access, but without
the contiguous memory requirement (and thus without the
copying).

HTH,
Michiel Salters

Jul 11 '06 #6

### This discussion thread is closed

Replies have been disabled for this discussion.