package com.example.demo.test;
 
import java.util.Vector;
 
/**
 
*
 
* VectorTest
 
*
 
* Description: JDK 1.8
 
* 测试Vector的扩容方式，通过测试可以看出其每次以2的倍数形式扩充Object数组
 
*
 
* @author Jalen
 
* @date 2019/8/27 13:31
 
*/
 
public class VectorTest {
 
public static void main(String[] args) {
 
createEmptyVector();
 
}
 
/**
 
* 创建Vector
 
* 调用链1(初始化)：
 
* {@link java.util.Vector#Vector(int)}
 
* 传入capacity为2，如果为空，默认capacity是10
 
* {@link java.util.Vector#Vector(int, int)}
 
* 第一个参数为初始容量initialCapacity，为2，第二个参数是capacityIncrement，默认在初始化时传0
 
* 该操作创建一个2个长度的Object数组，且capacityIncrement赋值为0
 
* 代码：
 
* super();
 
* if (initialCapacity < 0)
 
* throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
 
* this.elementData = new Object[initialCapacity];
 
* this.capacityIncrement = capacityIncrement;
 
* 调用链2：
 
* {@link java.util.Vector#add(Object)}
 
* synchronized修饰，modCount自增，计算容量(如果不够会执行扩容)，根据下标为elementData赋值
 
* 代码：
 
* modCount++;
 
* ensureCapacityHelper(elementCount + 1); //elementCount=0,只需确保有一个空间可用
 
* elementData[elementCount++] = e;
 
* return true;
 
* {@link java.util.Vector#ensureCapacity(int)}
 
* 这里传入的参数minCapacity为1，即我们需要的最小容量是1，elementData length是我们初始化时的容量2，此时不会扩容
 
* if (minCapacity - elementData.length > 0)
 
* grow(minCapacity);
 
* elementData[elementCount++] = e; //因为无需扩容，直接根据数组下标赋值就好啦
 
* 调用链3：
 
* 此时和调用链2是一样的，不存在扩容
 
* 调用链4：
 
* {@link java.util.Vector#add(Object)}
 
* synchronized修饰，modCount自增，计算容量(如果不够会执行扩容)，根据下标为elementData赋值
 
* 代码：
 
* modCount++;
 
* ensureCapacityHelper(elementCount + 1); //elementCount=0,只需确保有一个空间可用
 
* elementData[elementCount++] = e;
 
* return true;
 
* {@link java.util.Vector#ensureCapacity(int)}
 
* 这里传入的参数minCapacity为3，即我们需要的最小容量是3，elementData length是我们初始化时的容量2，此时会扩容
 
* if (minCapacity - elementData.length > 0)
 
* grow(minCapacity);
 
* {@link java.util.Vector#grow(int)}
 
* 计算新的容量，因为capacityIncrement初始化时是0，所以newCapacity = oldCapacity + oldCapacity，
 
* 即新容量等于旧容量的2倍，elementData扩容为原来的2倍数，即4
 
* 代码：
 
* int oldCapacity = elementData.length;
 
* int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity);
 
* if (newCapacity - minCapacity < 0)
 
* newCapacity = minCapacity;
 
* if (newCapacity - MAX_ARRAY_SIZE > 0)
 
* newCapacity = hugeCapacity(minCapacity); //MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8
 
* elementData = Arrays.copyOf(elementData, newCapacity);
 
* 最后根据下标赋值就好啦
 
* 代码：
 
* elementData[elementCount++] = e;
 
* 调用链5：
 
* 因为上一步扩容到4，此时不会扩容
 
* 调用链6：
 
* 此时因为容量4已用完，会触发扩容，容量扩大到8
 
*/
 
private static void createEmptyVector(){
 
Vectorvector = new Vector<>(2); //1
 
vector.add("aaa"); //2
 
vector.add("bbb"); //3
 
vector.add("ccc"); //4
 
vector.add("ddd"); //5
 
vector.add("eee"); //6
 
System.out.println(vector.toString());
 
}
 
/**
 
* 这里初始化时指定每次扩容的大小，交给用户设置
 
*/
 
private static void createEmptyVectorWithIncrement(){
 
Vectorvector = new Vector<>(2, 3);//初始容量为2，每次扩容空间为3
 
vector.add("aaa"); //不扩容，容量为2
 
vector.add("bbb"); //不扩容，容量为2
 
vector.add("ccc"); //扩容，扩容为5
 
vector.add("ddd"); //不扩容，容量为5
 
vector.add("eee"); //不扩容，容量为5
 
System.out.println(vector.toString());
 
}
 
}
 
扩容方法：
 
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
 
private void grow(int minCapacity) {
 
// overflow-conscious code
 
int oldCapacity = elementData.length;
 
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
 
capacityIncrement : oldCapacity);
 
if (newCapacity - minCapacity < 0)
 
newCapacity = minCapacity;
 
if (newCapacity - MAX_ARRAY_SIZE > 0)
 
newCapacity = hugeCapacity(minCapacity);
 
elementData = Arrays.copyOf(elementData, newCapacity);
 
}
 
注意不同于ArrayList的扩容方式
 
ArrayList扩容公式为：newCapacity  =  oldCapacity + oldCapacity >> 1

vector的resize()函数的作用是改变vector元素个数
 
reverse（）函数的作用是改变容量
 
如果v.reserve(n)函数的n的大小比vector原来的容量小。容量没有变化。size也没有变：
 
如果v.resize(n)函数的n比vector原来的size小，结果是size减小到n，然后删除n之后的数据。

一、求容器大小的函数：
 
size():返回当前vector元素的个数。
 
capacity():返回当前vector中最大能够存储的元素的个数。
 
二、扩容的两种情况：
 
情况1：当元素添加时导致的扩容。
 
int main()
{
	vector<int> vec;
	
	//扩容1:当元素添加时导致的扩容。VS2012采用的是1.5倍的扩容方式
	for(int i=0;i<30;i++)
	{
		vec.push_back(i);
		cout<<"size="<<vec.size()<<endl;
		cout<<"capacity="<<vec.capacity()<<endl;
	}
	cout<<"---------------------------------------------"<<endl;
	return 0;
}
 
运行结果：
 
 
可以看出对于普通的添加元素，vector在VS2012采用的是1.5倍的扩容方式。其他编译器我还没有测试，先记着，等到测试了再补充。
 
情况2：使用reserve(int new_size)或者resize(int new_size,/*int init_value*/)函数导致的扩容。两者都是将容器扩大到恰好容纳指定的元素。
 
reserve(int new_size):
 
a.将容器扩大到能容纳new_size的大小。
 
b.扩大的只是容器的预留空间，空间内不正真创建元素对象。
 
c.改变capacity()的返回值，不改变size()的返回值。
 
int main()
{
	vector<int> vec;
	
	for(int i=0;i<30;i++)
	{
		vec.push_back(i);
		cout<<"size="<<vec.size()<<endl;
		cout<<"capacity="<<vec.capacity()<<endl;
	}
	cout<<"---------------------------------------------"<<endl;

	//reserve()只为容器开辟预留空间，但在空间内不真正创建对象。
	//reserve()会改变容器capacity()的大小，但是不会改变容器size的大小。
	vec.reserve(50);
	cout<<"size="<<vec.size()<<endl;//30
	cout<<"capacity="<<vec.capacity()<<endl;//50
	/*for(int j=30;j<50;j++)//自己手动插入
	{
		vec.push_back(j);
	}*/
	//vec[36]=8;//自己不插入时，不能访问
	copy(vec.begin(),vec.end(),ostream_iterator<int>(cout," "));
	return 0;
}
 
 
 
 
resize(int new_size,/*int init_value*/):
 
 
 
a.第一个参数是指将要扩大到能容纳多少元素的大小；第二个参数是对扩大的空间进行初始化的值，如果不写，默认调用容器中存的元素的默认构造函数。
 
b.将容器扩大到能容纳new_size的大小。
 
c.改变容器的大小，并且创建对象。
 
d.改变capacity()的返回值，改变size()的返回值。
 
int main()
{
	vector<int> vec;
	
	for(int i=0;i<30;i++)
	{
		vec.push_back(i);
		cout<<"size="<<vec.size()<<endl;
		cout<<"capacity="<<vec.capacity()<<endl;
	}
	cout<<"---------------------------------------------"<<endl;

	//resize()会改变容器的大小,而且创建对象。
	//resize改变容器的capacity()和容器的size()的大小。
	//resize(int new_size,int init_value)第一个参数是容器新的大小，
	//第二个参数是对开辟的内存的初始化，如果省略第二个参数，则调用其默认构造函数。
	vec.resize(50);

	vector<int>::iterator it=vec.begin();
	for(;it!=vec.end();++it)
	{
		cout<<*it<<endl;
	}
	cout<<"size="<<vec.size()<<endl;//50
	cout<<"capacity="<<vec.capacity()<<endl;//63
	
	vec[49]=49;//可修改
	cout<<"vec[49]="<<vec[49]<<"  "<<"vec[36]="<<vec[36]<<endl;

	return 0;
}
 
 
三、容器的的回收
 
int main()
{
	vector<int> vec;
	
	for(int i=0;i<30;i++)
	{
		vec.push_back(i);
		cout<<"size="<<vec.size()<<endl;
		cout<<"capacity="<<vec.capacity()<<endl;
	}
	cout<<"---------------------------------------------"<<endl;

	//释放空间
	vec.clear();
	cout<<"size="<<vec.size()<<endl;//0
	cout<<"capacity="<<vec.capacity()<<endl;//42

	vec.erase(vec.begin(),vec.end());
	cout<<"size="<<vec.size()<<endl;//0
	cout<<"capacity="<<vec.capacity()<<endl;//42   
        /*
	第一步：先产生一个和原先一样的临时对象
	第二步：临时量调用swap()函数两者进行交换。
	第三步：语句结束，临时量自动析构。
	*/
	vector<int>().swap(vec);
	/*
	vector<int>(vec).swap(vec);  ===>   vec.swap(vector<int>())
	*/

	cout<<"size="<<vec.size()<<endl;//0
	cout<<"capacity="<<vec.capacity()<<endl;//0
	return 0;
}	第一步：先产生一个和原先一样的临时对象
	第二步：临时量调用swap()函数两者进行交换。
	第三步：语句结束，临时量自动析构。
	*/
	vector<int>().swap(vec);
	/*
	vector<int>(vec).swap(vec);  ===>   vec.swap(vector<int>())
	*/

	cout<<"size="<<vec.size()<<endl;//0
	cout<<"capacity="<<vec.capacity()<<endl;//0
	return 0;
}
 
 
总结：
 
使用clear()和erase()两个函数只是清空元素，但不回收内存。
 
先使用clear()再使用swap()，释放空间并且回收内存。

 
 
 
  
“默认情况下，C++标准库提供了合理的性能”。如果你对“合理的”一词暗含的意思有过好奇，请接着读下去……  
 
  
引言 
 
  
假设我们希望从一个文件中将一串类型为double的值读进一个数据结构中，从而允许我们高效地访问这些值，通常的方法如下：  
 
  
vector<double> values;
double x;
while (cin >> x)
    values.push_back(x);  
   
1
2
3
4
   

    
   
   
1
2
3
4
 
  
当循环结束时，values会容纳有所有的值，我们将可以通过values[i]高效地访问任何值。  

在直觉上，标准库vector类就像一个内建数组：我们可以认为它在单块连续的内存中容纳其元素。实际上，尽管C++标准没有明确要求vector的元素要占用连续的内存，然而标准委员会在2000年10月份的会议上裁定此项要求的遗漏归因于工作上的疏忽，并且投票表决将其作为技术勘误的一部分而包含进来。这个迟到的要求谈不上是多大的痛苦，因为每一个现有的vector实现本来就是以这种方式工作的。  

如果一个vector的元素位于连续的内存中，我们就很容易明白它是如何高效地访问个体元素的 — 只要使用与内建数组相同的机制就可以了。不过，要弄明白一个vector实现是如何处理高效增长的问题就不是这么简单了，因为这种增长将不可避免地涉及到将元素从一块内存区域拷贝到另外一块内存区域。尽管现代处理器通常特别擅长于将一块连续的数据从内存的一个地方拷贝到另一个地方，然而这样的拷贝并非是免费的午餐。因此，思考一个标准库实现可能是如何处理vector的增长而又不消耗过量的时间或空间，很有意义。  

本文的余下部分将讨论一个用于管理vector增长的简单而高效的策略。  
 
  
尺寸和容量 
 
  
要想搞清楚vector类的工作机制，首先要清楚它并不仅仅是一块内存。相反，每一个vector都关联有两个“尺寸”：一个称为尺寸（size），表示vector容纳的元素的数量；另一个称为容量（capacity），表示可被用来存储元素的内存总量。在vector尾部留有额外的内存的用意在于，当使用push_back向vector追加元素时无需分配更多的内存。如果邻接于vector尾部的内存当时恰好未被占用，那么vector的增长只要将那块内存合并过来即可。然而这样的好运气极其罕见，大多数情况下需要分配新的内存，然后将vector现有的元素拷贝到那块内存中，然后销毁原来的元素，最后归还元素先前占用的内存。在vector中留有额外的内存的好处在于，这样的重新分配（代价可能很昂贵）不会每当试图向vector追加一个元素时都发生。  
 
  
重新分配内存的代价有多高昂？它涉及如下四个步骤： 
 
  
•为需要的新容量分配足够的内存； 


•将元素从原来的内存拷贝到新内存中； 


•销毁原来的内存中的元素； 


•归还原来的内存。  


如果元素的数目为n，那么我们知道步骤(2)和(3)都要占用O(n)的时间，除非分配或归还内存的代价的增长超过O(n)，否则这两步将在全部运行时间中占居支配地位。因此我们可以得出结论：无论用于重新分配的容量（capacity）是多少，重新分配一个尺寸（size）为n的vector需要占用O(n)的时间。  

这个结论暗示了一种折衷权衡。假如在重新分配时请求大量的额外内存，那么在相当长的时间内将无需再次进行重新分配，因此总体重新分配操作消耗的时间相对较少，这种策略的代价在于将会浪费大量的空间。另一方面，我们可以只请求一点点额外的内存，这么做将会节约空间，但后继的重新分配操作将会耗费时间。换句话说，我们面临一个经典的抉择：拿时间换空间，或者相反。 
 
  
重新分配策略 
 
  
作为一个极端的例子，假定每当填充vector一次我们就将其容量增加1个单位，这种策略耗费尽可能少的内存空间，但每当追加一个元素时都要重新分配整个vector。我们说过，重新分配一个具有n个元素的vector占用O(n)的时间，因此，如果我们从一个空vector开始并将其增长到k个元素，那么占用的总时间将会是O(1+2+...+k)或者O(k2)，这太可怕了！有没有更好的办法呢？  

比方说，假如不是以1个步幅增长vector的容量，而是以一个常量C的步幅来增长它将会如何？很明显这个策略将会减少重新分配的次数（基于因子C），所以这当然是一种改进，但这个改进到底有多大呢？  

理解这个改进的方式之一是要认识到此一新策略将针对每C个元素块进行一次重新分配。假设我们为总量为KxC个元素分配K块内存，那么，第一次重新分配将会拷贝C个元素，第二次将会拷贝2xC个元素，等等。Big-O表示法不考虑常量因子，因此我们可以将所有的C因子分摊开来而获得O(1+2+...+K)或者O(K2)的总时间。换句话说，时间仍然是元素个数的二次方程，不过是带有一个小得多的因子罢了。  

撇开较小的因子不谈，“二次行为”仍然太糟糕，即使有一个快速的处理器也是如此。实际上，对于快速的处理器来说尤其糟糕，因为快速的处理器通常伴有大量的内存，而访问具有大量内存的快速处理器的程序员常常试图用尽那些内存（这是迟早的事）。这些程序员往往会发现，如果在运行一个二次算法的话，处理器的速度于事无补。  

我们刚刚证实，一个希望能以小于“二次时间”而分配大型vector的实现是不能使用“每次填充时以常量步幅增长vector容量”的策略的，相反，被分配的附加内存的数量必须随着vector的增长而增长。这个事实暗示存在一种简单的策略：vector从单个元素开始而后每当重新分配时倍增其容量，如何？事实证明这种策略允许我们以O(n)的时间构建一个有着n个元素的vector。  

为了理解是如何获得这样的效率的，考虑当我们已经完全填满它并打算对其重新分配时的vector的状态：  



自最近一次重新分配内存以来被追加到vector中的元素有一半从未被拷贝过，而对于那些被拷贝的元素而言，其中一半只被拷贝了一次，其余的一半被拷贝了两次，以此类推。  

换句话说，有n/2的元素被拷贝了一次或多次，有n/4的元素被拷贝了两次或多次，等等。因此，拷贝元素的总数目为n/2 + n/4 +...，结果可以近似为n（随着n的增大，这个近似值越发精确）。撇开拷贝动作不谈，有n个元素被追加到了vector中，但操作占用的时间总量仍然是O(n)而不是O(n2)。  
 
  
讨论 
 
  
C++标准并没有规定vector类必须以某种特定的方式管理其内存，它只是要求通过重复调用push_back而创建一个具有n个元素的vector耗费的时间不得超过O(n)，我们刚才讨论的策略可能是满足此项要求的最直截了当的一种。  

因为对于这样的操作来说vector具有优秀的时间性能，所以没有什么理由避免使用如下循环：  
 
  
vector<double> values;
double x;
while (cin >> x)
    values.push_back(x);
   
1
2
3
4
   

    
   
   
1
2
3
4
 
  
是的，当其增长时，实现将会重新分配vector的元素，但是，如果我们事先能够预测vector最终尺寸的话，这个重新分配耗费的时间将不会超过“一个常量因子”可能会占用的时间。  
 
  
练习 
 
  
1.设想我们通过以如下方式编写代码而努力使我们那个小型循环速度更快：  
 
  
while (cin >> x)
{
    if (values.size() == values.capacity())
        values.reserve(values.size() + 1000);
    values.push_back(x);
}
   
1
2
3
4
5
6
   

    
   
   
1
2
3
4
5
6
 
  
效果将会如何？成员函数reserve进行一次重新分配，从而改变vector的capacity，使其大于或等于其参数。  

2.设想不是每次倍增vector的尺寸，而是增大三倍，在性能上将会产生什么样的影响？特别是，创建一个具有n个元素的vector的运行时间仍然为O(n)吗？  

3.设想你知道你的vector最终将拥有多少元素，在这种情况下，在填充元素之前你可以调用reserve来预先分配数量合适的内存。试一试你手边的vector实现，看看调用reserve与否对你的程序的运行时间有多大的影响。  
 
  
附STL源码：
 
  
template <class T, class Alloc = alloc>
class vector{
public:
    typedef T value_type;
    typedef value_type* iterator;

protected:
    iterator start; //  指向头结点    
    iterator finish; // 尾结点    
    iterator end_of_storage; //容量

public:
    // 获取容量函数
    size_type capacity() const
    {
        return size_type(end_of_storage - begin());
    }

    // 默认构造函数，可见都被初始化为0
    vector() : start(0), finish(0), end_of_storage(0) {}

    // 带容量的构造函数
    explicit vector(size_type n) { fill_initialize(n, T()); }

    // fill_initialize实现如下    
    void fill_initialize(size_type n, const T& value)
    {
        start = allocate_and_fill(n, value);
        finish = start + n;
        end_of_storage = finish; // 可见容量被设置为n的值    
    }

    // push_back()调用insert搜索_aux函数    
    void insert_aux(iterator position, const T& x)
    {
        if (finish != end_of_storage)    //    
        else
        {
            const size_type old_size = size();
            const size_type len = old_size != 0 ? 2 * old_size : 1;    // 可见，初始为0，添加一个后容量变1，以后空间不够的话，新容量为原先2倍    
        }
    }
};  
   
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
   

    
   
   
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43