CareerCup

This might not be 100% accurate but,

A list is just a list, linked list, doubly linked list, circular linked list, etc. It's just a collection of nodes that can have any number of values.

A set I believe can only have a unique set of items in it. A set usually has some significance to its members. That is, a user may be curious of whether a value is included in the set as some sort of criteria.

A map is an associative construct that maps a key with a value. Each key should only appear once in the map.

Different programming languages and books tend to use the terms in somewhat different ways, hence the confusion about this topic. I present what I take to be the closest thing to consensus on the meanings.

A "list" in CS is generally something like a "sequence" in math, and a "set" in CS is generally like, well, a "set" in math.

A List is a collection where elements are accessed by their index. When we insert an element into a list, we specify where it should be inserted in the sequence, and that's where it stays (subsequent insertions/removals may change the numeric index, of course, but relative positioning is preserved). A list, therefore, contains more information than just the values it holds -- it also contains information on how these values are ordered. In mathematical terms, a list stores a sequence of elements.

A set, on the other hand, cannot be accessed by index, and asking to insert something into a specific position makes no sense. A set's content is determined entirely by what elements it contains, and there is no concept of the elements being contained in a certain order. A set has no information in it aside from what elements it contains. If we do talk about some kind of order on a set, we are simply talking about the natural ordering of the values in the set and not any kind of indexes at which the elements reside, things like the 2nd largest value, 5th smallest value, etc. In a sequence of add operations to a set, the order in which elements are added is irrelevant because there are no indices. Sometimes, the word "set" is used to imply that the datastructure contains only unique values (to match the mathematical definition of "set"), but this meaning is not used universally. Sometimes, sets allowing duplicates are called "multisets".

A map is a function mapping a certain set of input values to output values of a certain type. For instance, a map could map the set of all user IDs currently registered in your application to Strings corresponding to the cryptographic key for that user. It's just a way of associating certain inputs with certain outputs. Often, the meaning is taken to be that the inputs are of some finite and bounded domain already known to your application (your set of users is known to your program, and you would use a map to help you associate cryptographic keys with users quickly and easily).

A map is really a generalization of both an array and a set. An array associates an index integer in the domain [0...N-1] with a value of the type that corresponds to the type of the array. So, an array can be seen conceptually as an int -> type_of_array map where the keys include precisely all the integers between 0 and N-1, inclusive. Note that I'm NOT saying that maps and arrays are implemented in the same way -- they're not! I'm just saying that if you only had a map, you could build an array data structure from it, because an array is sort of a special case of a map. A set is also a special case of a map -- you can put keys in a map with meaningless values attached to them, thus using the map as a set.

Containers in c++