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 theT
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()
).
- Note that the dynamic memory allocation is "× capacity (
- 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.
- Only when inserting at the end position (
- 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 theT
type is small.- It does not have the concept of capacity and always consumes memory in the order of "× number of elements (
size()
)".
- It does not have the concept of capacity and always consumes memory in the order of "× number of elements (
- 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.)
- Even sequential scans tend to waste CPU cache lines and are generally slower than
- 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.