stl – C++ Set or List

Question:

Hello, is it better to use an array of sets or sheets to represent the adjacency of a graph? What is the difference between a set and a sheet from the inside. Thank you

Answer:

1. No matter how ridiculous it may sound, but practice shows that std::vector is best suited for representing a graph in the form of adjacency lists , and not std::list .

2. The use of std::set is usually unnecessary.

3. Here is an excerpt from the English StackOverflow :

   … in 90% of cases std::vector will be the best choice. Yes, a linked list looks prettier in the vast majority of cases, because the order of the elements is (usually) irrelevant to it. In other words, the added elements are placed at the end of the container buffer [regardless of where they are inserted – approx. trans.] , and the element to be removed is previously exchanged with the end element, so that insertion and deletion affect only the element at the end of this buffer.

   The vector, in turn, copies its elements each time its buffer is expanded, but this is not essential in practice. Exponential growth ensures that the average number of copies tends to some constant, typically three or so.

   Even if copying is really a problem for you (for example, the elements are large), I still would not switch to a linked list. Instead, I would use std::deque . This is, in fact, a vector of pointers to blocks with elements. It rarely copies anything when it expands, and if it does, it only copies those pointers, not the elements themselves. However, a vector is still the preferred choice, unless you need the capabilities inherent in a deck (inserting into and deleting from either end); but even dec is preferable to list. In other words, first std::vector , then std::deque , and only at the very end std::list .