How does adding and removing elements "rescale" the data? How is the size of the vector calculated (I believe it is kept track of)? Any other additional resources to learn about vectors would be appreciated.
如何添加和删除元素“重新缩放”数据?如何计算矢量的大小(我相信它是跟踪的)?任何其他额外的资源来了解矢量将不胜感激。
4 个解决方案
#1
30
In terms of sizing, there are two values of interest for an std::vector: size, and capacity (accessed via .size() and .capacity()).
在大小调整方面,std :: vector有两个值:size和capacity(通过.size()和.capacity()访问)。
.size() is the number of elements that are contained in the vector, whereas .capacity() is the number of elements that can be added to the vector, before memory will be re-allocated.
.size()是向量中包含的元素数,而.capacity()是在重新分配内存之前可以添加到向量的元素数。
If you .push_back() an element, size will increase by one, up until you hit the capacity. Once the capacity is reached, most (all?) implementations, re-allocate memory, doubling the capacity.
如果你.push_back()一个元素,大小将增加1,直到你达到容量。一旦达到容量,大多数(全部?)实现,重新分配内存,使容量加倍。
You can reserve a capacity using .reserve. For example:
您可以使用.reserve预留容量。例如:
std::vector<int> A;
A.reserve(1); // A: size:0, capacity:1 {[],x}
A.push_back(0); // A: size:1, capacity:1 {[0]}
A.push_back(1); // A: size:2, capacity:2 {[0,1]}
A.push_back(2); // A: size:3, capacity:4 {[0,1,2],x}
A.push_back(3); // A: size:4, capacity:4 {[0,1,2,3]}
A.push_back(4); // A: size:5, capacity:8 {[0,1,2,3,4],x,x,x}
Reallocations of memory would occur at lines 4, 5, and 7.
内存的重新分配将发生在第4,5和7行。
#2
7
The vector usually has three pointers. If the vector has never been used they are all 0, or NULL.
矢量通常有三个指针。如果从未使用过向量,则它们都是0或NULL。
- One to the first element of the vector. (this is the begin() iterator)
- One to last element of the vector + 1. (this is the end() iterator)
- And one more to the last allocated but unused element + 1. (this minus begin() is the capacity)
一到矢量的第一个元素。 (这是begin()迭代器)
向量的最后一个元素+ 1.(这是end()迭代器)
还有一个到最后分配但未使用的元素+ 1.(这减去begin()就是容量)
When an element is inserted, the vector allocates some storage and sets its pointers. It might allocate 1 element, or it might allocate 4 elements. Or 50.
插入元素时,向量会分配一些存储并设置其指针。它可能会分配1个元素,或者它可能会分配4个元素。或者50。
Then it inserts the element and increments the last element pointer.
然后它插入元素并递增最后一个元素指针。
When you insert more elements than are allocated the vector has to get more memory. It goes out and gets some. If the memory location changes then it has to copy all the elements into the new space and free the old space.
当您插入的元素多于分配的元素时,向量必须获得更多内存。它出去了,得到了一些。如果内存位置发生变化,则必须将所有元素复制到新空间并释放旧空间。
A common choice for resizing is to double the allocation every time it needs more memory.
调整大小的一个常见选择是每次需要更多内存时将分配加倍。
#3
2
The implementation of std::vector changed slightly with C++0x and later with the introduction of move semantics (see What are move semantics? for an introduction).
std :: vector的实现稍微改变了C ++ 0x,后来引入了移动语义(参见什么是移动语义?)。
When adding an element to a std::vector which is already full then the vector is resized which involves a procedure of allocating a new, larger memory area, moving the existing data to the new vector, deleting the old vector space, and then adding the new element.
将元素添加到已满的std :: vector时,将调整向量的大小,其中包括分配新的更大内存区域,将现有数据移动到新向量,删除旧向量空间,然后添加的过程。新元素。
std::vector is a collection class in the Standard Template Library. Putting objects into a vector, taking them out, or the vector performing a resize when an item is added to a full vector all require that the class of the object support an assignment operator, a copy constructor, and move semantics. (See type requirements for std::vector as well as std::vector works with classes that are not default constructible? for details.)
std :: vector是标准模板库中的集合类。将对象放入向量中,将它们取出,或者将项目添加到完整向量时执行调整大小的向量都需要对象的类支持赋值运算符,复制构造函数和移动语义。 (有关详细信息,请参阅std :: vector的类型要求以及std :: vector与非默认可构造的类一起使用吗?)
One way to think of std::vector is as a C style array of contiguous elements of the type specified when the vector is defined that has some additional functionality to integrate it into the Standard Template Library offerings. What separates a vector from a standard array is that a vector will dynamically grow as items are added. (See std::vector and c-style arrays as well as When would you use an array rather than a vector/string? for some discussion about differences.)
考虑std :: vector的一种方法是在定义向量时指定类型的连续元素的C样式数组,该向量具有将其集成到标准模板库产品中的一些附加功能。将矢量与标准数组分开的是矢量将随着项目的添加而动态增长。 (请参阅std :: vector和c-style数组以及何时使用数组而不是vector / string?来讨论差异。)
Using std::vector allows the use of other Standard Template Library components such as algorithms so using std::vector comes with quite a few advantages over a C style array as you get to use functionality that already exists.
使用std :: vector允许使用其他标准模板库组件,例如算法,因此使用std :: vector与C样式数组相比具有很多优点,因为您可以使用已存在的功能。
You can specify an initial size if the maximum is known ahead of time. (See Set both elements and initial capacity of std::vector as well as Choice between vector::resize() and vector::reserve() )
如果提前知道最大值,则可以指定初始大小。 (请参阅设置std :: vector的元素和初始容量以及vector :: resize()和vector :: reserve()之间的选择)
The basics of std::vector physical representation is of a set of pointers using memory allocated from the heap. These pointers allow for the actual operations for accessing the elements stored in the vector, deleting elements from the vector, iterating over the vector, determining the number of elements, determining its size, etc.
std :: vector物理表示的基础是使用从堆分配的内存的一组指针。这些指针允许实际操作以访问存储在向量中的元素,从向量中删除元素,迭代向量,确定元素的数量,确定其大小等。
Since the physical representation is contiguous memory, deleting items may result in moving of remaining items to close any holes created by the delete operation.
由于物理表示是连续的存储器,因此删除项目可能导致移动剩余的项目以关闭由删除操作创建的任何孔。
With modern C++ move semantics, the overhead of std::vector has been reduced such that it is typically the default container that would be used for most applications as recommended by Bjarne Stroustrup in his book The C++ Programming Language 4th Edition which discusses C++11.
使用现代C ++移动语义,std :: vector的开销已经减少,因此它通常是Bjarne Stroustrup在其讨论C ++的C ++编程语言第4版中推荐的大多数应用程序的默认容器。 11。
#4
0
I wrote a vector in C++ a year or so ago. It is an array with a set size (ex. 16 chars) which is expanded by that amount when needed. That is to say, if the default size is 16 chars and you need to store Hi my name is Bobby, then it will double the size of the array to 32 chars then store the char array there.
大约一年前我用C ++编写了一个向量。它是一个具有设定大小(例如16个字符)的数组,在需要时会扩展该数量。也就是说,如果默认大小是16个字符而你需要存储你好我的名字是Bobby,那么它会将数组的大小加倍到32个字符然后将char数组存储在那里。
#1
30
In terms of sizing, there are two values of interest for an std::vector: size, and capacity (accessed via .size() and .capacity()).
在大小调整方面,std :: vector有两个值:size和capacity(通过.size()和.capacity()访问)。
.size() is the number of elements that are contained in the vector, whereas .capacity() is the number of elements that can be added to the vector, before memory will be re-allocated.
.size()是向量中包含的元素数,而.capacity()是在重新分配内存之前可以添加到向量的元素数。
If you .push_back() an element, size will increase by one, up until you hit the capacity. Once the capacity is reached, most (all?) implementations, re-allocate memory, doubling the capacity.
如果你.push_back()一个元素,大小将增加1,直到你达到容量。一旦达到容量,大多数(全部?)实现,重新分配内存,使容量加倍。
You can reserve a capacity using .reserve. For example:
您可以使用.reserve预留容量。例如:
std::vector<int> A;
A.reserve(1); // A: size:0, capacity:1 {[],x}
A.push_back(0); // A: size:1, capacity:1 {[0]}
A.push_back(1); // A: size:2, capacity:2 {[0,1]}
A.push_back(2); // A: size:3, capacity:4 {[0,1,2],x}
A.push_back(3); // A: size:4, capacity:4 {[0,1,2,3]}
A.push_back(4); // A: size:5, capacity:8 {[0,1,2,3,4],x,x,x}
Reallocations of memory would occur at lines 4, 5, and 7.
内存的重新分配将发生在第4,5和7行。
#2
7
The vector usually has three pointers. If the vector has never been used they are all 0, or NULL.
矢量通常有三个指针。如果从未使用过向量,则它们都是0或NULL。
- One to the first element of the vector. (this is the begin() iterator)
- One to last element of the vector + 1. (this is the end() iterator)
- And one more to the last allocated but unused element + 1. (this minus begin() is the capacity)
一到矢量的第一个元素。 (这是begin()迭代器)
向量的最后一个元素+ 1.(这是end()迭代器)
还有一个到最后分配但未使用的元素+ 1.(这减去begin()就是容量)
When an element is inserted, the vector allocates some storage and sets its pointers. It might allocate 1 element, or it might allocate 4 elements. Or 50.
插入元素时,向量会分配一些存储并设置其指针。它可能会分配1个元素,或者它可能会分配4个元素。或者50。
Then it inserts the element and increments the last element pointer.
然后它插入元素并递增最后一个元素指针。
When you insert more elements than are allocated the vector has to get more memory. It goes out and gets some. If the memory location changes then it has to copy all the elements into the new space and free the old space.
当您插入的元素多于分配的元素时,向量必须获得更多内存。它出去了,得到了一些。如果内存位置发生变化,则必须将所有元素复制到新空间并释放旧空间。
A common choice for resizing is to double the allocation every time it needs more memory.
调整大小的一个常见选择是每次需要更多内存时将分配加倍。
#3
2
The implementation of std::vector changed slightly with C++0x and later with the introduction of move semantics (see What are move semantics? for an introduction).
std :: vector的实现稍微改变了C ++ 0x,后来引入了移动语义(参见什么是移动语义?)。
When adding an element to a std::vector which is already full then the vector is resized which involves a procedure of allocating a new, larger memory area, moving the existing data to the new vector, deleting the old vector space, and then adding the new element.
将元素添加到已满的std :: vector时,将调整向量的大小,其中包括分配新的更大内存区域,将现有数据移动到新向量,删除旧向量空间,然后添加的过程。新元素。
std::vector is a collection class in the Standard Template Library. Putting objects into a vector, taking them out, or the vector performing a resize when an item is added to a full vector all require that the class of the object support an assignment operator, a copy constructor, and move semantics. (See type requirements for std::vector as well as std::vector works with classes that are not default constructible? for details.)
std :: vector是标准模板库中的集合类。将对象放入向量中,将它们取出,或者将项目添加到完整向量时执行调整大小的向量都需要对象的类支持赋值运算符,复制构造函数和移动语义。 (有关详细信息,请参阅std :: vector的类型要求以及std :: vector与非默认可构造的类一起使用吗?)
One way to think of std::vector is as a C style array of contiguous elements of the type specified when the vector is defined that has some additional functionality to integrate it into the Standard Template Library offerings. What separates a vector from a standard array is that a vector will dynamically grow as items are added. (See std::vector and c-style arrays as well as When would you use an array rather than a vector/string? for some discussion about differences.)
考虑std :: vector的一种方法是在定义向量时指定类型的连续元素的C样式数组,该向量具有将其集成到标准模板库产品中的一些附加功能。将矢量与标准数组分开的是矢量将随着项目的添加而动态增长。 (请参阅std :: vector和c-style数组以及何时使用数组而不是vector / string?来讨论差异。)
Using std::vector allows the use of other Standard Template Library components such as algorithms so using std::vector comes with quite a few advantages over a C style array as you get to use functionality that already exists.
使用std :: vector允许使用其他标准模板库组件,例如算法,因此使用std :: vector与C样式数组相比具有很多优点,因为您可以使用已存在的功能。
You can specify an initial size if the maximum is known ahead of time. (See Set both elements and initial capacity of std::vector as well as Choice between vector::resize() and vector::reserve() )
如果提前知道最大值,则可以指定初始大小。 (请参阅设置std :: vector的元素和初始容量以及vector :: resize()和vector :: reserve()之间的选择)
The basics of std::vector physical representation is of a set of pointers using memory allocated from the heap. These pointers allow for the actual operations for accessing the elements stored in the vector, deleting elements from the vector, iterating over the vector, determining the number of elements, determining its size, etc.
std :: vector物理表示的基础是使用从堆分配的内存的一组指针。这些指针允许实际操作以访问存储在向量中的元素,从向量中删除元素,迭代向量,确定元素的数量,确定其大小等。
Since the physical representation is contiguous memory, deleting items may result in moving of remaining items to close any holes created by the delete operation.
由于物理表示是连续的存储器,因此删除项目可能导致移动剩余的项目以关闭由删除操作创建的任何孔。
With modern C++ move semantics, the overhead of std::vector has been reduced such that it is typically the default container that would be used for most applications as recommended by Bjarne Stroustrup in his book The C++ Programming Language 4th Edition which discusses C++11.
使用现代C ++移动语义,std :: vector的开销已经减少,因此它通常是Bjarne Stroustrup在其讨论C ++的C ++编程语言第4版中推荐的大多数应用程序的默认容器。 11。
#4
0
I wrote a vector in C++ a year or so ago. It is an array with a set size (ex. 16 chars) which is expanded by that amount when needed. That is to say, if the default size is 16 chars and you need to store Hi my name is Bobby, then it will double the size of the array to 32 chars then store the char array there.
大约一年前我用C ++编写了一个向量。它是一个具有设定大小(例如16个字符)的数组,在需要时会扩展该数量。也就是说,如果默认大小是16个字符而你需要存储你好我的名字是Bobby,那么它会将数组的大小加倍到32个字符然后将char数组存储在那里。