What is the difference between std :: set and std :: vector?

Question

Now I am studying STL. I read about the set container. I have a question when do you want to use set ? After reading the description of the set, it looks useless, because we can replace it with vector . Could you say pluses and cos for vector vs set containers. Thanks

Answer 1

A set ordered. It is guaranteed that he will remain in a certain order, according to the functor you provided. No matter what elements you add or remove (unless you add a duplicate that is not allowed in set ), it will always be ordered.

A vector has exactly and only the order that you explicitly give it. The elements in vector are where you put them. If you expose them to a non-working state, then they are not in order; now you need a sort container to get them back in order.

Admittedly, set has relatively limited use. With the right discipline, you can insert elements into vector and keep them ordered. However, if you constantly insert and remove elements from the container, vector will work in many problems. It will copy / move elements a lot, etc., since it is actually just an array.

The time required to insert an element in vector is proportional to the number of elements already in vector . The time taken to insert an element into a set element is proportional to the log₂ of the number of elements. If the number of items is large, this is a huge difference. log₂ (100 000) - ~ 16; which is a significant improvement in speed. The same goes for deletion.

However, if you do all your inserts at once, during initialization, then there is no problem. You can insert everything in vector , sort it (by paying this price once), and then use the standard algorithms for sorted vectors to search for items and repeat through the sorted list. And while iterating over the elements of a set not too slow, iterating over vector is faster.

So, there are times when a sorted vector superior to a set . In this case, you really should not worry about the costs of such optimization, if you do not know what it is necessary. Therefore, use set if you do not have experience with the system you are writing (and therefore know that you need this performance) or you have profiling data that tells you that you need vector , not set .

Answer 2

These are different things: you decide how the vectors are ordered, and you can also put as many objects into the vector as you wish. Sets are ordered according to established internal rules (you can set rules, but a set will deal with order), and you cannot put several equal elements in a set.

Of course, you could save a vector of unique elements, but your performance will suffer greatly when you perform operations with orientation. For example, suppose you have a set of 10,000 elements and a vector of 10,000 different unordered elements. Suppose now that you need to check if the value of X is one of the values ​​in the set (or among the values ​​in the vector). When X is not among the elements, vector search will be about 100 times slower. You will see similar performance differences when calculating joins and intersections of sets.

To summarize, sets and vectors have different goals. You can use a vector instead of a set, but this will require more work, and this can severely affect performance.

Answer 3

It’s faster to look for an element against the set than the vector (O (log (n)) vs O (n)). To search an element by vector, you need to iterate through all the elements in the vector, but to use the search, use the red and black tree to optimize the search. Look at just a few items to find a match.

The set is ordered, which means that you can only iterate from the smallest to the largest in order or in reverse order.

But the vector is unordered, you can move it in insertion order.

Answer 4

form cpluplus.com recruitment:

Sets are containers in which unique elements, order are stored.

so the set is ordered And the element is uniquely represented

and vect:

Vectors are sequence containers that represent arrays that can be resized.

therefore, the vector is in the order in which you fill it. And may contain several identical elements.

prefers a set:

• if you want to filter multiple identical values
• if you want to analyze the elements in the specified order (for this, in the vector you need to specially sort the vector).

prefer a vector:

• if you want to keep the same values
• if you want to parse the elements in the same order as you clicked them (provided that you do not process the vector order)