#include "stdafx.h"

#include<vector>

#include<iostream>

using namespace std;



int _tmain(int argc, _TCHAR* argv[])

{
vector<int> Index;
int i;

    for ( i= 0; i < 6; i++)

    {
Index.push_back(i);  //元素添加

    }
//第一种用遍历器输出verctor中的元素
vector<int>::iterator iter; //声明遍利器 


for (iter = Index.begin(); iter!=Index.end(); ++iter)
{

       cout<<*iter<<endl; 
 
}
//第二种输出方式可以以数组方式输出
for (i = 0; i < Index.size(); i++)
{
cout<<Index[i]<<endl;
}
return 0;

}

（注意：本文基于JDK1.8）





 

前言

    算上迭代器的add（）方法，Vector中一共有7个添加元素的方法，5个添加单个元素的方法，2个添加多个元素的方法，接下来就一起分析它们的实现……Vector是一个线程安全的容器类，它的添加功能是如何做到线程安全的呢?

 

add（E）方法分析

    public synchronized boolean add(E e) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = e;
        return true;
    }

用于添加1个元素的方法，由synchronized修饰，只有获得对象锁的线程才可以执行该方法，其它未获得对象锁的线程会blocked在方法的入口处，等待已经持有对象锁的线程释放对象锁，传入的参数为即将要添加的元素对象，类型为指定的类型参数E

1、首先修改modCount值

Vecotor的父类AbstractList中，定义了实例变量modCount，这意味着每个Vector对象也持有一个modCount，这里将其+1，表示当前Vector对象持有的元素发生变化，这个modCount值是用于防止用户在多线程下使用容器类而设计的，常被称为fail-fast机制，可Vector本身是线程安全的容器类，为何这里还在使用modCount做++呢？费解……

2、然后检查底层数组容量能否再添加一个新的元素

通过调用ensureCapacityHelper（）方法检查，传入参数是实际元素总数+1后的一个值，用于确认当前数组的容量是否需要扩充容量，如果数组的容量无法再添加一个新的元素，则在此方法中会对当前Vector对象持有的数组对象进行容量扩充（扩容的方法，将在单独的文章中分析，这里只需知道，容量不够，先扩容）

3、将元素赋值到数组对象中某个下标处，并增加表示元素总数的实例变量

先使用Vector对象持有的elmentCount作为数组下标，将新增加的元素赋值给elementData数组中对应的下标处，接着将表示实际持有元素的总数值的elementCount增加1，这里的实例变量elementCount同时扮演着两个角色，一个是用于记录Vector对象实际持有的元素总数，另一个是用于作为Vector对象持有的底层数组对象的下标！

4、返回添加元素的结果

每次都会返回true，表示添加元素成功

 

add（int，E）方法分析

    public void add(int index, E element) {
        insertElementAt(element, index);
    }

用于在指定下标处添加一个元素的方法，第一个参数index表示指定的下标，第二个参数element表示添加的元素

方法体中调用insertElementAt（）方法，并将传入的index、element两个参数同时传入insertElementAt（）方法中，由insertElementAt（）方法完成元素的添加

 

insertElementAt（）方法分析

    public synchronized void insertElementAt(E obj, int index) {
        modCount++;
        if (index > elementCount) {
            throw new ArrayIndexOutOfBoundsException(index
                                                     + " > " + elementCount);
        }
        ensureCapacityHelper(elementCount + 1);
        System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
        elementData[index] = obj;
        elementCount++;
    }

用于在指定下标处添加1个元素的方法，第一参数obj表示添加的元素对象，第二个参数index表示指定的下标……（注意：这里的参数顺序，真是老外思路），同样由synchronized修饰，只有获取到对象锁的线程才能执行该方法，未获取到对象锁的线程处于方法入口处，并处于blocked状态

1、最先修改modCount值

实例变量modCount定义在父类AbstractList中，它用于防止容器类在多线程下使用，常称为fail-fast机制i，此处将该值增加1，表示Vector对象持有的元素发生改变

2、检查传入的下标值是否合法

如果传入的下标值index大于Vector对象实际持有的元素总数elementCount值，此时抛出ArrayIndexOutOfBoundsException对象，并提示用户"index > elementCount"（替换为实际值）

3、检查是否需要扩容

调用ensureCapacityHelper（）方法，同时将elementCount+1的值传了进去

4、拷贝数组元素，腾出一个空余位置

通过System的静态方法arraycopy（）完成元素的拷贝，arraycopy（）的第一个参数为源数组对象，第二个参数为源数组对象的起始下标（从哪个元素开始拷贝），第三个参数为目标数组对象，第四个参数为目标数组对象的起始下标（从哪个元素开始粘贴），第五个参数为需要拷贝的元素数量！此处只需挪出一个位置，即可存放即将要插入的元素！

5、向指定位置插入元素

已经腾出空余空间，只需将元素插入到数组的指定下标处即可

6、元素总数增加

Vector对象持有的elementCount增加1

 

addElement（）方法分析

    public synchronized void addElement(E obj) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = obj;
    }

同样为synchronized修饰，添加一个元素的方法，有一点和add（）方法不同，它没有返回值…………，几乎都一样，这里不再冗余分析

 

addAll（）方法分析

    public synchronized boolean addAll(Collection<? extends E> c) {
        modCount++;
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityHelper(elementCount + numNew);
        System.arraycopy(a, 0, elementData, elementCount, numNew);
        elementCount += numNew;
        return numNew != 0;
    }

用于添加多个元素的方法，传入的参数为Collection对象，表示持有多个元素的集合对象，本身方法同样是由synchronized修饰

1、为modCount值增加1，表示Vecor对象持有的元素发生改变，fail-fast机制会用到该值

2、先将Collection对象，转换成一个Object[]数组对象，并由局部变量a负责保存

3、获取转换数组后的长度，由局部变量numNew负责保存

4、调用ensureCpacityHelper（）方法，将需要的新容量（elementCount+numNew）传入进去，检查现有数组容量能否存储下新的元素数量

5、使用System的静态方法arraycopy（），复制新的元素到旧的数组中，完成添加元素行为

6、更新elementCount总数

7、返回添加结果，只要添加的数量不是0，说明添加元素成功

 

addAll（int，Collection）方法分析

    public synchronized boolean addAll(int index, Collection<? extends E> c) {
        modCount++;
        if (index < 0 || index > elementCount)
            throw new ArrayIndexOutOfBoundsException(index);

        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityHelper(elementCount + numNew);

        int numMoved = elementCount - index;
        if (numMoved > 0)
            System.arraycopy(elementData, index, elementData, index + numNew,
                             numMoved);

        System.arraycopy(a, 0, elementData, index, numNew);
        elementCount += numNew;
        return numNew != 0;
    }

在指定位置添加多个元素的方法，传入的参数index表示指定的下标、传入的参数c表示要添加元素集合对象，同样为synchronized修饰，只有获取到对象锁的线程才能执行该方法，java的线程间同步做的真的太好！

1、更新modCount值，用于fail-fast机制检测

2、检查下标范围是否合法，不合法抛出ArrayIndexOutOfBoundsException提示用户

3、Collection对象转数组对象

4、获取转换后数组对象的长度

5、确认是否需要扩容数组容量

6、计算需要移动元素的数量

7、确定需要移动元素，使用System的静态方法arraycopy（）移动元素

8、将新插入的所有元素，都赋值到elementData数组中，就从指定下标index开始

9、更新元素总数值

10、返回添加结果，不为0，即为True

 

ListItr中的add（）方法分析

        public void add(E e) {
            int i = cursor;
            synchronized (Vector.this) {
                checkForComodification();
                Vector.this.add(i, e);
                expectedModCount = modCount;
            }
            cursor = i + 1;
            lastRet = -1;
        }

迭代器对象，可以添加元素，必须可以

1、先将遍历到哪个元素的游标保存到局部变量i中

2、只有获取到对象锁的线程，才能执行该代码块，此处仍为当前Vector对象作为对象锁

检查fail-fast机制

使用Vector的add（int，E）方法进行添加元素

更新一个预期值，expetcedModCount，这个也是用于fail-fast机制检测用的

3、更新游标值，增加1

4、更新迭代器对象持有的lastRet值为-1，表示上一次并没有进行遍历元素的行为

 

总结

1、Vector使用了一手synchronized，这也是导致效率变低的原因

2、假设1个线程执行插入操作需要5s，而其它n个线程操作任意一个Vecotor的方法，因为没有持有当前的Vector对象锁，所有的n个线程都被阻塞了……，同一时刻，只有1个线程能操作Vector的1个方法

3、如果只是读的操作，完全没有必要线程间同步啊，毕竟读的内存值一直没变啊，所以后来大牛不建议使用Vector

  1、remove并不是删除，仅仅是移除，要加上erase才能完成删除。 

2、remove并不是删除指定位置的元素，而移除所有指定的元素。 

3、用algorithm代替成员函数不是一个好的选择。


删除的方法:
vec.erase(remove(vec.begin(),vec.end(),value),vec.end());



例:ListBox的添加与删除

变量:

CListBox m_List;

vector<CString> m_str:


//Add:(如果存在则删除旧的)

int nlndex;

while ((nIndex = this->m_List.FindString(nIndex , ...)) != LB_ERR)

{

m_List.DeleteString( nIndex );

if((int)m_str.size()>=nIndex)

{

m_str.erase(remove(m_str.begin(),m_str.end(),m_str[nIndex]),m_str.end()); 

}

}


m_List.AddString(...);

m_str.push_back(...);



//delete:

int count = m_List.GetSelCount();

int* lpIndex = NULL;

if(count<0)

return;

if (count == 0)

m_List.ResetContent();

lpIndex = new int[count];

m_List.GetSelItems(count,lpIndex);

int num = 0;

for(int i = 0;i<count;i++)

{

int delNum = lpIndex[i];

if(delNum>=num &&num>0)

{

delNum = delNum-num;

}


if((int)m_str.size()>=delNum)

{

m_str.erase(remove(m_str.begin(),m_str.end(),m_str[delNum]),m_str.end()); 

}

m_List.DeleteString(delNum);

num++;

}

delete []lpIndex;

1、为什么需要主动释放vector内存


vector其中一个特点：内存空间只会增长，不会减小，援引C++ Primer：为了支持快速的随机访问，vector容器的元素以连续方式存放，每一个元素都紧挨着前一个元素存储。设想一下，当vector添加一个元素时，为了满足连续存放这个特性，都需要重新分配空间、拷贝元素、撤销旧空间，这样性能难以接受。因此STL实现者在对vector进行内存分配时，其实际分配的容量要比当前所需的空间多一些。就是说，vector容器预留了一些额外的存储区，用于存放新添加的元素，这样就不必为每个新元素重新分配整个容器的内存空间。


在调用push_back时，每次执行push_back操作，相当于底层的数组实现要重新分配大小；这种实现体现到vector实现就是每当push_back一个元素,都要重新分配一个大一个元素的存储，然后将原来的元素拷贝到新的存储，之后在拷贝push_back的元素，最后要析构原有的vector并释放原有的内存。



2、怎么释放vector的内存

A、对于数据量不大的vector，没有必要自己主动释放vector，一切都交给操作系统。

B、但是对于大量数据的vector，在vector里面的数据被删除后，主动去释放vector的内存就变得很有必要了！

由于vector的内存占用空间只增不减，比如你首先分配了10000个字节，然后erase掉后面9999个，留下一个有效元素，但是内存占用仍为10000个。所有内存空间是在vector析构时候才能被系统回收。empty()用来检测容器是否为空的，clear()可以清空所有元素。但是即使clear()，vector所占用的内存空间依然如故，无法保证内存的回收。如果需要空间动态缩小，可以考虑使用deque。如果vector，可以用swap()来帮助你释放内存。

 

3、示例代码

新建一个控制台程序，把代码运行起来看输出，且看代码：

#include <iostream>
#include <vector>
#include <string>
#include <Windows.h>
#include <Psapi.h>
#pragma comment(lib, "Psapi.lib")

using namespace std;

//GetCurPorcessMemory
bool GetCurProcessMemory(HANDLE handle, std::wstring& workingSize, std::wstring& peakWorkingSize)
{
	//HANDLE handle = GetCurrentProcess();
	PROCESS_MEMORY_COUNTERS pmc;
	if (GetProcessMemoryInfo(handle, &pmc, sizeof(pmc)))
	{
		int size = pmc.WorkingSetSize/1024;
		wchar_t buf[10] = {0};
		_ltow(size, buf, 10);
		workingSize = std::wstring(buf);

		size = pmc.PeakWorkingSetSize/1024;
		_ltow(size, buf, 10);
		peakWorkingSize = std::wstring(buf);

		return true;
	}
	return false;
}

int _tmain(int argc, _TCHAR* argv[])
{
	std::wstring wszWorking, wszPeakWorking;
	vector<string> ary;

	for (int i=0; i<1000000; i++)
	{
		ary.push_back("hello vector");
	}

	wchar_t wch;
	wcin >> wch;

	GetCurProcessMemory(GetCurrentProcess(), wszWorking, wszPeakWorking);// 此时检查内存情况
	wcout << "Working : " << wszWorking.c_str() << " PeakWorking : " << wszPeakWorking.c_str() << endl;

	wcin >> wch;

	//
	ary.clear();
	wcout << "vector clear" << endl;
	wcout << "vector capacity " << ary.capacity() << endl;	
	GetCurProcessMemory(GetCurrentProcess(), wszWorking, wszPeakWorking);// 此时再次检查
	wcout << "Working : " << wszWorking.c_str() << " PeakWorking : " << wszPeakWorking.c_str() << endl;

	wcin >> wch;
	//vector<string>(ary).swap(ary);
	ary.swap(vector<string>(ary));	
	wcout << "vector swap" << endl;
	wcout << "vector capacity " << ary.capacity() << endl;// 此时容量为0	
	GetCurProcessMemory(GetCurrentProcess(), wszWorking, wszPeakWorking);// 检查内存
	wcout << "Working : " << wszWorking.c_str() << " PeakWorking : " << wszPeakWorking.c_str() << endl;

	wcout << "vector size : " << ary.size() << endl;//0

	//getchar();
	system("pause");

	return 0;
}