What's the difference between a set and a map?

[akash16]

As described below on cppreference

Set:
The C++ Set is an associative container that contains a sorted set of unique objects.

Map:
C++ Maps are sorted associative containers that contain unique key/value pairs.

I'm having trouble finding the distinction.

And also the proper use case where we should which mp/set.

[LB]

A map associates unique keys with arbitrary values. A set just holds unique keys and does not associate them with anything.

Each entry in a map has a key and a value. Each entry in a set just has the key.

[dhayden]

The key is in what they contain. A set is just what you'd think it is: a set of objects. Use it when you just need to store and find a bunch of things, like student names.

A map is used to store key/value pairs. For example, if you need to look up a student record from a student ID, you might use a map from ID to record.

Hope this helps.

[akash16]

Thanks for reply.


"Each entry in a map has a key and a value. Each entry in a set just has the key."

Its ok about the map but in case of set...?

Set has only key means???
the values in set itself is a key???

There is no key in set then how it maintain the uniqueness of values it have?

[48T7M4Gy]

http://www.cplusplus.com/reference/set/set/ - a set of values

http://www.cplusplus.com/reference/map/map/ - a set of key-value pairs

[LB]

A set could be a list of student IDs in a class - the same student can't be in a class twice.

A map could be a relationship between student ID and student name - each student can only have one name, but it's ok if two students have the same name (as sometimes happens in real life).

[akash16]

What I can understand about set and map is:

Both are implemented by binary search tree algorithm.

1. Set
Each node in tree has value and pointer to point other nodes.
Usecase : ?

2. Map
Each node has key, value and pointer to point other nodes.
Usecase : ?

[LB]

Don't be concerned with the implementation, it is not relevant to your understanding and may not be the same for all compilers.

I gave example use cases in my previous post.

Both containers are useful when you need to maintain unique values. Only one container is useful when you want to associate each unique value with an arbitrary value.

[akash16]

Thanks.

But I just thinking about the implementation to understand the efficiency/complexity and hence the usecases where we can use specific container.

Points I got:

1. Values in set are constants so we not able to change it.
2. Values in set are not constants so we can able to change it.

At many places I read that set containers are generally slower than unordered_set and same with map.

But why? I am looking for this now...

[coder777]

At many places I read that set containers are generally slower than unordered_set and same with map.

They are not generally slower. The insertion is slower due to the sorting each time.

[LB]

You can freely change the aspects of the values in a set so long as they do not affect the sort order. If you change the values in a way that affects the sort order, you get undefined behavior. It's like having a sorted bookshelf and changing one of the book's names - the bookshelf doesn't know you did that and it might never check.

[tcs]

Implementing sets or maps as binary search trees isn't mandatory. There are many other ways to do it. F.e. hash tables may do a good job in some cases. Or you may even use a list or an array, ... But it may be expensive to ensure uniqueness in lists and arrays. So they may be useful if the set or map will contain only a few items (f.e. in small embedded systems with poor memory resources).

There may be thousands of use cases for sets and maps:

//Map absolute magnitude of some stars on the sky

typedef float Magnitude;
class Star { /* ... */ };
typedef map<Star*, Magnitude> Star2Magnitude;

// A set of stars having an attribute named `magnitude´ may do it similar if the comparison
// operator compares two stars by their `magnitude´.
// NOTE: The concept of a set (like `std::set´) forces uniqueness of its items. So there
//       cannot exists two stars with the same magnitude in it! (But have a look at
//       `std::multiset´)

typedef unsigned long Magnitude;
class Star
{
private:
    Magnitude _magnitude;  // A stars key attribute. Should NEVER be modified.
                           // It cannot be declared `const' due to loss of the
                           // copy constructor in case of a `const' attribute.
    // ...
public:
    Star(Magnitude theMagnitude = 0) :
        _magnitude(theMagnitude)
    {}

    // Only define a getter.
    // Never modify _magnitude as long as the Star is member of a set.
    Magnitude magnitude()
    { return _magnitude; }

    // A Stars comparison operator uses its key attribute
    bool operator<(const Star &right) const
    { return _magnitude < right._magnitude; }

    // ...
};
typedef set<Star> Stars;

// Looking for a Star by magnitude is also a little bit more difficult.
static bool lookupStarByMagnitude(const Stars &stars, Magnitude magnitude,
                                  Star &starFound)
{
    const Star rightStar(magnitude);
    const Stars::iterator lookupResult = stars.find(rightStar);
    const bool found = (lookupResult != stars.end());

    if (found)
    {
        starFound = *lookupResult;
    }

    return found;

} /* lookupStarByMagnitude() */

// A galaxy contains some stars

class Star { /* ... */ };
typedef set<Star*> Stars;

Stars galaxy;

[LB]

Note that a set of pointers or a map with pointers as the key only guarantees uniqueness of memory location (unless you provide a specialized comparison operator).

[keskiverto]

The reference doc for unordered_set on this site writes:

unordered_set containers are faster than set containers to access individual elements by their key, although they are generally less efficient for range iteration through a subset of their elements.

There are trade-offs. How big is the difference? Depends on the use case.


Think of a linked list that has numbers in ascending order. You can insert and remove numbers, but if you would want to change a number that would probably require reordering of the nodes in the list, which in turn is easiest to do by remove(old) + insert(new). But why provide a change(old, new) when the user can do the same with existing insert() and remove() with relative ease?

However, it is really easy to loop over the first N (smallest) values of the list.


Lets do something different. Have ten buckets 0..9. Put all values that start with digit k into bucket k. That is quick and simple. Again, changing a value probably means that it cannot stay in the same bucket. In addition, it does take more bookkeeping, if you want to remember in which order the values were inserted into the buckets.

[akash16]

Got it. :)

[48T7M4Gy]

In order to change a value already in a set, the value in the set has to be be erased and replaced with the new value. Similarly you can't directly change the key in a map without creating problems.

[akash16]

Thanks LB.

"Note that a set of pointers or a map with pointers as the key only guarantees uniqueness of memory location (unless you provide a specialized comparison operator)."

Its very true. We need to override comparison operator in above case.

[LB]

Better option: don't use pointers ;)

[akash16]

Thanks kesk.

But in your linked list example, I think even while insert and remove needs reordering.

Thanks tcs.

And I would like to know one thing to my self that set or map not only can implemented by Binary search tree.

[48T7M4Gy]

Ordering or re-ordering when an element is erased or inserted is automatic,