c++ – How to use vector and list properly

Question: Question:

How do you use vector and list properly? I received a question like this.

So I would say vector is an array and list is a list.
When it comes to specific usage, lists are good at cutting and connecting, and vector consumes less array memory.
However, I have no idea how to use it by cutting or connecting it when actually expressing it.
If you frequently delete / insert one data to the waypoint, I feel that map and set are faster if you include the search.
If it is the first or last point, queue should be enough even if it is not list .
When it comes to that, I can't think of a situation where it consumes a lot of memory and requires the operation of cutting and connecting, which is not found in the actual example, and I said, " vector is better."

Is there an algorithm or program that is appropriate to be represented by a list regardless of any of the stl data structures?

Answer: Answer:

In most cases, using vector<T> should be sufficient. ( T is the element type)

Scott Meyers, " Effective STL " also mentions the following in Item 1

vector is the type of sequence that should be used by default.

list<T> is preferable only when the following conditions are met. How often / many / large it can be said depends strongly on the processing content and element type, so it should be judged by actual measurement in the end.

• Elements are frequently inserted / deleted in the middle position,
• The number of elements stored in the container is very large ,
• When the size of sizeof T of the element type is large enough .

---

Below are the main features of vector and list .

std::vector sequence container

• A so-called "variable length array" container.
• Memory usage overhead per element is small. As a guide, only size of sizeof T x capacity + 1 pointer type + 2 integer types of memory is used, which is especially advantageous when the T type is small.

  • Note that the dynamic memory allocation is "× capacity ( capacity() )", not "× number of elements ( size() )". If the number of elements can be predicted in advance, the cost of reallocating memory when inserting elements can be reduced by specifying an appropriate capacity ( reserve() ).

• Random access to arbitrary position elements ( operator[] ) is possible in constant time (nearly zero cost).
• Inserting an element at a position other than the end position takes a linear time.

  • Only when inserting at the end position ( push_back() ) and capacity> number of elements, element insertion can be performed in a constant time. When capacity expansion is required, a maximum of 2.5 to 3 times the memory is required by allocating dynamic memory.

• Since it is guaranteed that all elements are placed in contiguous memory areas, it can be passed to legacy APIs that require array types (such as T* ).

  • CPU cache utilization efficiency is good in sequential scanning of elements, and high-speed scanning can be expected. (High data locality and good compatibility with hardware prefetcher mechanism)

• Inserting / deleting an element invalidates the iterator that points to another element.
• It is possible to get the number of elements ( size() ) in constant time (nearly zero cost).

std::list sequence container

• A so-called "doubly-linked list" container.
• The overhead of memory usage per element is large. As a guide, ( sizeof T + 2 pointer types) x number of elements is used, so waste is large, especially when the T type is small.

  • It does not have the concept of capacity and always consumes memory in the order of "× number of elements ( size() )".

• The first element ( front() ) / end element ( back() ) can be accessed in constant time, but access to the intermediate element requires sequential scanning (linear time).
• Elements can be inserted / deleted at any position in a constant time.
• The elements are placed in separate memory locations.

  • Even sequential scans tend to waste CPU cache lines and are generally slower than vector scans. (Data locality is lost, especially if it is inserted / deleted frequently.)

• Inserting / deleting an element does not invalidate the iterator that points to another element.
• Linear time is required to get the number of elements ( size() ). If it is C ++ 11 or later, constant time is guaranteed by the specifications, but check the compatibility of the compiler and library to be used.