Vectors are a kind of sequence container. As such, their elements are ordered following a strict linear sequence.
Vector containers are implemented as dynamic arrays; Just as regular arrays, vector containers have their elements stored in contiguous storage locations, which means that their elements can be accessed not only using iterators but also using offsets on regular pointers to elements.
But unlike regular arrays, storage in vectors is handled automatically, allowing it to be expanded and contracted as needed.
Vectors are good at:
Accessing individual elements by their position index (constant time).
Iterating over the elements in any order (linear time).
Add and remove elements from its end (constant amortized time).
Compared to arrays, they provide almost the same performance for these tasks, plus they have the ability to be easily resized. Although, they usually consume more memory than arrays when their capacity is handled automatically (this is in order to accommodate extra storage space for future growth).
Compared to the other base standard sequence containers (deques and lists), vectors are generally the most efficient in time for accessing elements and to add or remove elements from the end of the sequence. For operations that involve inserting or removing elements at positions other than the end, they perform worse than deques and lists, and have less consistent iterators and references than lists.
Internally, vectors -like most containers- have a size, which represents the amount of elements contained in the vector. But vectors, also have a capacity, which determines the amount of storage space they have allocated, and which can be either equal or greater than the actual size. The extra amount of storage allocated is not used, but is reserved for the vector to be used in the case it grows. This way, the vector does not have to reallocate storage on each occasion it grows, but only when this extra space is exhausted and a new element is inserted (which should only happen in logarithmic frequence in relation with its size).
Reallocations may be a costly operation in terms of performance, since they generally involve the entire storage space used by the vector to be copied to a new location. You can use member function vector::reserve to indicate beforehand a capacity for the vector. This can help optimize storage space and reduce the number of reallocations when many enlargements are planned.
----
Lists are a kind of sequence container. As such, their elements are ordered following a linear sequence.
List containers are implemented as doubly-linked lists; Doubly linked lists can store each of the elements they contain in different and unrelated storage locations. The ordering is kept by the association to each element of a link to the element preceding it and a link to the element following it.
This provides the following advantages to list containers:
Efficient insertion and removal of elements anywhere in the container (constant time).
Efficient moving elements and block of elements within the container or even between different containers (constant time).
Iterating over the elements in forward or reverse order (linear time).
Compared to other base standard sequence containers (vectors and deques), lists perform generally better in inserting, extracting and moving elements in any position within the container, and therefore also in algorithms that make intensive use of these, like sorting algorithms.
The main drawback of lists compared to these other sequence containers is that they lack direct access to the elements by their position; For example, to access the sixth element in a list one has to iterate from a known position (like the beginning or the end) to that position, which takes linear time in the distance between these. They also consume some extra memory to keep the linking information associated to each element (which may be an important factor for large lists of small-sized elements).
Storage is handled automatically by the list object, allowing it to be expanded and contracted automatically as needed.
Vector containers are implemented as dynamic arrays; Just as regular arrays, vector containers have their elements stored in contiguous storage locations, which means that their elements can be accessed not only using iterators but also using offsets on regular pointers to elements.
But unlike regular arrays, storage in vectors is handled automatically, allowing it to be expanded and contracted as needed.
Vectors are good at:
Accessing individual elements by their position index (constant time).
Iterating over the elements in any order (linear time).
Add and remove elements from its end (constant amortized time).
Compared to arrays, they provide almost the same performance for these tasks, plus they have the ability to be easily resized. Although, they usually consume more memory than arrays when their capacity is handled automatically (this is in order to accommodate extra storage space for future growth).
Compared to the other base standard sequence containers (deques and lists), vectors are generally the most efficient in time for accessing elements and to add or remove elements from the end of the sequence. For operations that involve inserting or removing elements at positions other than the end, they perform worse than deques and lists, and have less consistent iterators and references than lists.
Internally, vectors -like most containers- have a size, which represents the amount of elements contained in the vector. But vectors, also have a capacity, which determines the amount of storage space they have allocated, and which can be either equal or greater than the actual size. The extra amount of storage allocated is not used, but is reserved for the vector to be used in the case it grows. This way, the vector does not have to reallocate storage on each occasion it grows, but only when this extra space is exhausted and a new element is inserted (which should only happen in logarithmic frequence in relation with its size).
Reallocations may be a costly operation in terms of performance, since they generally involve the entire storage space used by the vector to be copied to a new location. You can use member function vector::reserve to indicate beforehand a capacity for the vector. This can help optimize storage space and reduce the number of reallocations when many enlargements are planned.
----
Lists are a kind of sequence container. As such, their elements are ordered following a linear sequence.
List containers are implemented as doubly-linked lists; Doubly linked lists can store each of the elements they contain in different and unrelated storage locations. The ordering is kept by the association to each element of a link to the element preceding it and a link to the element following it.
This provides the following advantages to list containers:
Efficient insertion and removal of elements anywhere in the container (constant time).
Efficient moving elements and block of elements within the container or even between different containers (constant time).
Iterating over the elements in forward or reverse order (linear time).
Compared to other base standard sequence containers (vectors and deques), lists perform generally better in inserting, extracting and moving elements in any position within the container, and therefore also in algorithms that make intensive use of these, like sorting algorithms.
The main drawback of lists compared to these other sequence containers is that they lack direct access to the elements by their position; For example, to access the sixth element in a list one has to iterate from a known position (like the beginning or the end) to that position, which takes linear time in the distance between these. They also consume some extra memory to keep the linking information associated to each element (which may be an important factor for large lists of small-sized elements).
Storage is handled automatically by the list object, allowing it to be expanded and contracted automatically as needed.
Comments
Post a Comment
https://gengwg.blogspot.com/