C++ vector的用法小结
投稿：shangke
字体：[ ] 类型：转载 时间：
这篇文章主要介绍了c++中，vector是一个十分有用的容器，下面对这个容器做一下总结
c++ vector用法
C++内置的数组支持容器的机制，但是它不支持容器抽象的语义。要解决此问题我们自己实现这样的类。在标准C++中，用容器向量（vector）实现。容器向量也是一个类模板。
标准库vector类型使用需要的头文件：#include &vector&。vector 是一个类模板。不是一种数据类型，vector&int&是一种数据类型。Vector的存储空间是连续的,list不是连续存储的。
一、 定义和初始化
vector& typeName & v1;&&&&&& //默认v1为空，故下面的赋值是错误的v1[0]=5;
vector&typeName&v2(v1); 或v2=v1;或vector&typeName& v2(v1.begin(), v1.end());//v2是v1的一个副本，若v1.size（）&v2.size()则赋值后v2.size()被扩充为v1.size()。
vector& typeName & v3(n,i);//v3包含n个值为i的typeName类型元素
vector& typeName & v4(n); //v4含有n个值为0的元素
int a[4]={0,1,2,3,3}; vector&int& v5(a,a+5);//v5的size为5，v5被初始化为a的5个值。后一个指针要指向将被拷贝的末元素的下一位置。
vector&int& v6(v5);//v6是v5的拷贝
vector& 类型 & 标识符（最大容量，初始所有值）；
二、 值初始化
1&&&&& 如果没有指定元素初始化式，标准库自行提供一个初始化值进行值初始化。
2&&&&& 如果保存的式含有构造函数的类类型的元素，标准库使用该类型的构造函数初始化。
3&&&&& 如果保存的式没有构造函数的类类型的元素，标准库产生一个带初始值的对象，使用这个对象进行值初始化。
三、vector对象最重要的几种操作
1. v.push_back(t)&&& 在容器的最后添加一个值为t的数据，容器的size变大。
&&&&&&&&&&&&&&&&&&&& 另外list有push_front()函数，在前端插入，后面的元素下标依次增大。
2. v.size()&&&&&&& 返回容器中数据的个数，size返回相应vector类定义的size_type的值。v.resize(2*v.size)或&&&&&&&&&&&&&&&&&&
v.resize(2*v.size, 99) 将v的容量翻倍(并把新元素的值初始化为99)
3. v.empty()&&&& 判断vector是否为空
4. v[n]&&&&&&&&&& 返回v中位置为n的元素
5. v.insert(pointer,number, content)&&& 向v中pointer指向的位置插入number个content的内容。
&&&&&&&&&&&&&&&&& 还有v. insert(pointer, content)，v.insert(pointer,a[2],a[4])将a[2]到a[4]三个元素插入。
6. v.pop_back()&&& 删除容器的末元素，并不返回该元素。
7.v.erase(pointer1,pointer2) 删除pointer1到pointer2中间（包括pointer1所指）的元素。
&&&&&&&&&&&&&&&&&& vector中删除一个元素后，此位置以后的元素都需要往前移动一个位置，虽然当前迭代器位置没有自动加1，
&&&&&&&&&&&&&&&&&& 但是由于后续元素的顺次前移，也就相当于迭代器的自动指向下一个位置一样。
8. v1==v2&&&&&&&&& 判断v1与v2是否相等。
9. ！=、&、&=、&、&=&&&&& 保持这些操作符惯有含义。
10. vector&typeName&::iterator p=v1.begin( ); p初始值指向v1的第一个元素。*p取所指向元素的值。
&&&&&&&&&&&&&&&&&&& 对于const vector&typeName&只能用vector&typeName&::const_iterator类型的指针访问。
11.&& p=v1.end( ); p指向v1的最后一个元素的下一位置。
12.v.clear()&&&&& 删除容器中的所有元素。12.v.clear()&&&&& 删除容器中的所有元素。
#include&algorithm&中的泛函算法
搜索算法：find() 、search() 、count() 、find_if() 、search_if() 、count_if()
分类排序：sort() 、merge()
删除算法：unique() 、remove()
生成和变异：generate() 、fill() 、transformation() 、copy()
关系算法：equal() 、min() 、max()
sort(v1.begin(),vi.begin()+v1.size/2）; 对v1的前半段元素排序
list&char&::iterator pMiddle =find(cList.begin(),cList.end(),'A');找到则返回被查内容第一次出现处指针，否则返回end()。
vector& typeName &::size_ vector& typeName &类型的计数，可用于循环如同for(int i)
初学C++的程序员可能会认为vector的下标操作可以添加元素，其实不然：
vector&int&&& // empty vector
for (vector&int&::size_type ix = 0; ix != 10; ++ix)
&&&& ivec[ix] = // disaster: ivec has no elements
上述程序试图在ivec中插入10个新元素，元素值依次为0到9的整数。但是，这里ivec是空的vector对象，而且下标只能用于获取已存在的元素。
这个循环的正确写法应该是：
for (vector&int&::size_type ix = 0; ix != 10; ++ix)
&&&& ivec.push_back(ix); // ok: adds new element with value ix
警告：必须是已存在的元素才能用下标操作符进行索引。通过下标操作进行赋值时，不会添加任何元素。仅能对确知已存在的元素进行下标操作&&
四、内存管理与效率
&&&&& 1.使用reserve()函数提前设定容量大小，避免多次容量扩充操作导致效率低下。
&&&&&&& 关于STL容器，最令人称赞的特性之一就是是只要不超过它们的最大大小，它们就可以自动增长到足以容纳你放进去的数据。（要知道这个最大值，只要调用名叫max_size的成员函数。）对于vector和string，如果需要更多空间，就以类似realloc的思想来增长大小。vector容器支持随机访问，因此为了提高效率，它内部使用动态数组的方式实现的。在通过 reserve() 来申请特定大小的时候总是按指数边界来增大其内部缓冲区。当进行insert或push_back等增加元素的操作时，如果此时动态数组的内存不够用，就要动态的重新分配当前大小的1.5~2倍的新内存区，再把原数组的内容复制过去。所以，在一般情况下，其访问速度同一般数组，只有在重新分配发生时，其性能才会下降。正如上面的代码告诉你的那样。而进行pop_back操作时，capacity并不会因为vector容器里的元素减少而有所下降，还会维持操作之前的大小。对于vector容器来说，如果有大量的数据需要进行push_back，应当使用reserve()函数提前设定其容量大小，否则会出现许多次容量扩充操作，导致效率低下。
&&&&& reserve成员函数允许你最小化必须进行的重新分配的次数，因而可以避免真分配的开销和迭代器/指针/引用失效。但在我解释reserve为什么可以那么做之前，让我简要介绍有时候令人困惑的四个相关成员函数。在标准容器中，只有vector和string提供了所有这些函数。
(1) size()告诉你容器中有多少元素。它没有告诉你容器为它容纳的元素分配了多少内存。
(2) capacity()告诉你容器在它已经分配的内存中可以容纳多少元素。那是容器在那块内存中总共可以容纳多少元素，而不是还可以容纳多少元素。如果你想知道一个vector或string中有多少没有被占用的内存，你必须从capacity()中减去size()。如果size和capacity返回同样的值，容器中就没有剩余空间了，而下一次插入（通过insert或push_back等）会引发上面的重新分配步骤。
(3) resize(Container::size_type n)强制把容器改为容纳n个元素。调用resize之后，size将会返回n。如果n小于当前大小，容器尾部的元素会被销毁。如果n大于当前大小，新默认构造的元素会添加到容器尾部。如果n大于当前容量，在元素加入之前会发生重新分配。
(4) reserve(Container::size_type n)强制容器把它的容量改为至少n，提供的n不小于当前大小。这一般强迫进行一次重新分配，因为容量需要增加。（如果n小于当前容量，vector忽略它，这个调用什么都不做，string可能把它的容量减少为size()和n中大的数，但string的大小没有改变。在我的经验中，使用reserve来从一个string中修整多余容量一般不如使用“交换技巧”，那是条款17的主题。）
&&&& 这个简介表示了只要有元素需要插入而且容器的容量不足时就会发生重新分配（包括它们维护的原始内存分配和回收，对象的拷贝和析构和迭代器、指针和引用的失效）。所以，避免重新分配的关键是使用reserve尽快把容器的容量设置为足够大，最好在容器被构造之后立刻进行。
例如，假定你想建立一个容纳1-1000值的vector&int&。没有使用reserve，你可以像这样来做：
vector&int&
for (int i = 1; i &= 1000; ++i) v.push_back(i);
在大多数STL实现中，这段代码在循环过程中将会导致2到10次重新分配。（10这个数没什么奇怪的。记住vector在重新分配发生时一般把容量翻倍，而1000约等于210。）
把代码改为使用reserve，我们得到这个：
vector&int&
v.reserve(1000);
for (int i = 1; i &= 1000; ++i) v.push_back(i);
这在循环中不会发生重新分配。
在大小和容量之间的关系让我们可以预言什么时候插入将引起vector或string执行重新分配，而且，可以预言什么时候插入会使指向容器中的迭代器、指针和引用失效。例如，给出这段代码，
if (s.size() & s.capacity()) {
s.push_back('x');
push_back的调用不会使指向这个string中的迭代器、指针或引用失效，因为string的容量保证大于它的大小。如果不是执行push_back，代码在string的任意位置进行一个insert，我们仍然可以保证在插入期间没有发生重新分配，但是，与伴随string插入时迭代器失效的一般规则一致，所有从插入位置到string结尾的迭代器/指针/引用将失效。
回到本条款的主旨，通常有两情况使用reserve来避免不必要的重新分配。第一个可用的情况是当你确切或者大约知道有多少元素将最后出现在容器中。那样的话，就像上面的vector代码，你只是提前reserve适当数量的空间。第二种情况是保留你可能需要的最大的空间，然后，一旦你添加完全部数据，修整掉任何多余的容量。
&&&&&& 2.使用“交换技巧”来修整vector过剩空间/内存
&&&&& 有一种方法来把它从曾经最大的容量减少到它现在需要的容量。这样减少容量的方法常常被称为“收缩到合适（shrink to fit）”。该方法只需一条语句：vector&int&(ivec).swap(ivec);
表达式vector&int&(ivec)建立一个临时vector，它是ivec的一份拷贝：vector的拷贝构造函数做了这个工作。但是，vector的拷贝构造函数只分配拷贝的元素需要的内存，所以这个临时vector没有多余的容量。然后我们让临时vector和ivec交换数据，这时我们完成了，ivec只有临时变量的修整过的容量，而这个临时变量则持有了曾经在ivec中的没用到的过剩容量。在这里（这个语句结尾），临时vector被销毁，因此释放了以前ivec使用的内存，收缩到合适。
&&&& 3.用swap方法强行释放STL Vector所占内存
template & class T& void ClearVector( vector&T&& v )
&&& vector&T&vtT
&&& vtTemp.swap( v );
&&& vector&int&
&&& nums.push_back(1);
&&& nums.push_back(3);
&&& nums.push_back(2);
&&& nums.push_back(4);
&&& vector&int&().swap(v);
/* 或者v.swap(vector&int&()); */
/*或者{ std::vector&int& tmp =&& v.swap(tmp);&& }; //加大括号{ }是让tmp退出{ }时自动析构*/
五、Vector 内存管理成员函数的行为测试
C++ STL的vector使用非常广泛，但是对其内存的管理模型一直有多种猜测，下面用实例代码测试来了解其内存管理方式，测试代码如下：
#include &iostream&
#include &vector&
int main()
vector&int& iV
cout && "容器 大小为: " && iVec.size() &&
cout && "容器 容量为: " && iVec.capacity() && //1个元素， 容器容量为1
iVec.push_back(1);
cout && "容器 大小为: " && iVec.size() &&
cout && "容器 容量为: " && iVec.capacity() && //2个元素， 容器容量为2
iVec.push_back(2);
cout && "容器 大小为: " && iVec.size() &&
cout && "容器 容量为: " && iVec.capacity() && //3个元素， 容器容量为4
iVec.push_back(3);
cout && "容器 大小为: " && iVec.size() &&
cout && "容器 容量为: " && iVec.capacity() && //4个元素， 容器容量为4
iVec.push_back(4);
iVec.push_back(5);
cout && "容器 大小为: " && iVec.size() &&
cout && "容器 容量为: " && iVec.capacity() && //5个元素， 容器容量为8
iVec.push_back(6);
cout && "容器 大小为: " && iVec.size() &&
cout && "容器 容量为: " && iVec.capacity() && //6个元素， 容器容量为8
iVec.push_back(7);
cout && "容器 大小为: " && iVec.size() &&
cout && "容器 容量为: " && iVec.capacity() && //7个元素， 容器容量为8
iVec.push_back(8);
cout && "容器 大小为: " && iVec.size() &&
cout && "容器 容量为: " && iVec.capacity() && //8个元素， 容器容量为8
iVec.push_back(9);
cout && "容器 大小为: " && iVec.size() &&
cout && "容器 容量为: " && iVec.capacity() && //9个元素， 容器容量为16
/* vs2005/8 容量增长不是翻倍的，如
&&& 9个元素&& 容量9
&&& 10个元素 容量13 */
/* 测试effective stl中的特殊的交换 swap() */
cout && "当前vector 的大小为: " && iVec.size() &&
cout && "当前vector 的容量为: " && iVec.capacity() &&
vector&int&(iVec).swap(iVec);
cout && "临时的vector&int&对象 的大小为: " && (vector&int&(iVec)).size() &&
cout && "临时的vector&int&对象 的容量为: " && (vector&int&(iVec)).capacity() &&
cout && "交换后，当前vector 的大小为: " && iVec.size() &&
cout && "交换后，当前vector 的容量为: " && iVec.capacity() &&
六、vector的其他成员函数
c.assign(beg,end)
将[ end)区间中的数据赋值给c。
c.assign(n,elem)
将n个elem的拷贝赋值给c。
传回索引idx所指的数据，如果idx越界，抛出out_of_range。
传回最后一个数据，不检查这个数据是否存在。
传回地一个数据。
get_allocator
使用构造函数返回一个拷贝。
c.rbegin()
传回一个逆向队列的第一个数据。
传回一个逆向队列的最后一个数据的下一个位置。
c.~ vector &Elem&()
销毁所有数据，释放内存。&&
以下是其它网友的补充：
1 、基本操作
(1)头文件#include&vector&.
(2)创建vector对象，vector&int&
(3)尾部插入数字：vec.push_back(a);
(4)使用下标访问元素，cout&&vec[0]&&记住下标是从0开始的。
(5)使用迭代器访问元素.
vector&int&::
for(it=vec.begin();it!=vec.end();it++)
&&& cout&&*it&&
(6)插入元素：&&& vec.insert(vec.begin()+i,a);在第i+1个元素前面插入a;
(7)删除元素：&&& vec.erase(vec.begin()+2);删除第3个元素
vec.erase(vec.begin()+i,vec.end()+j);删除区间[i,j-1];区间从0开始
(8)向量大小:vec.size();
(9)清空:vec.clear();
2、vector的元素不仅仅可以使int,double,string,还可以是结构体，但是要注意：结构体要定义为全局的，否则会出错。下面是一段简短的程序代码：
#include&stdio.h&
#include&algorithm&
#include&vector&
#include&iostream&
typedef struct rect
　　//对于向量元素是结构体的，可在结构体内部定义比较函数，下面按照id,length,width升序排序。
　　bool operator& (const rect &a)& const
&&&&&&& if(id!=a.id)
&&&&&&&&&&& return id&a.
&&&&&&& else
&&&&&&&&&&& if(length!=a.length)
&&&&&&&&&&&&&&& return length&a.
&&&&&&&&&&& else
&&&&&&&&&&&&&&& return width&a.
int main()
&&& vector&Rect&
&&& rect.id=1;
&&& rect.length=2;
&&& rect.width=3;
&&& vec.push_back(rect);
&&& vector&Rect&::iterator it=vec.begin();
&&& cout&&(*it).id&&' '&&(*it).length&&' '&&(*it).width&&&&&
(1) 使用reverse将元素翻转：需要头文件#include&algorithm&
reverse(vec.begin(),vec.end());将元素翻转(在vector中，如果一个函数中需要两个迭代器，
一般后一个都不包含.)
(2)使用sort排序：需要头文件#include&algorithm&，
sort(vec.begin(),vec.end());(默认是按升序排列,即从小到大).
可以通过重写排序比较函数按照降序比较，如下：
定义排序比较函数：
bool Comp(const int &a,const int &b)
&&& return a&b;
调用时:sort(vec.begin(),vec.end(),Comp)，这样就降序排序。
您可能感兴趣的文章:
大家感兴趣的内容
12345678910
最近更新的内容
常用在线小工具〇、序言创新对于学术研究或产业应用都具有不言而喻的重要作用，现在国家也提出了要建立创新型国家的发展战略。如果回到我们所探讨的图像处理或数据挖掘研究，细细品读其中的某些点滴，你是否能窥探出些许启迪？首先，创新可以分成两种，一种是原始创新，另外一种就是所谓的二次创新。如果一个东西过去完全不存在，你鬼使神差的就想出来，那就是原始创新。比如图灵当初石破天惊地构想出图灵机就是原始创新。到现在也没有任何迹象表明，他受到了什么事或什么人的启发。事实上，现在人们（包括我学习图灵机的时候）也非常惊讶，图灵是如何提出这种前无古人的奇思妙想的！二次创新也有很多种形式。比如逆向创新。据说人们在发明吸尘器之前最先发明的是吹尘器。一吸一吹，看似简单的一个颠倒，结果却如此神奇。现在同学们学习模式匹配算法时，必然是言必称KMP算法。的确，就原有的思路来说，KMP算法已经是做到极致了。但如果你还想有所突破呢？那就得首先打破旧有的条条框框。所以Boyer和Moore逆其道而行之，便提出了BM算法。KMP是从前向后做比较，而BM则是从后向前做比较。BM算法不仅提供了效率，更重要的是，由他们所提出的新思路为发端，后续产生了一个庞大的算法族。像BMH，BMHS等等又接踵而至。现在实际中基于BM算法的改进算法（相比于KMP）应用得其实更为广泛！但是今天要谈的还不是逆序创新的话题。我们要谈的是二次创新中另外一种方法，暂且称之为“推衍创新”。这个思路在现代科学中可谓随处可见，如果你还没有抓住他的名门，那么说明就研究工作来说，你还没入门。举一个简单的例子作为序言的结尾。最初，“伟哥”是作为治疗心绞痛的药物而研发的。但是，后来在临床试验中发现对治疗男性勃起功能障碍更加有效。所以现在它主要被应用于这方面的疾病。所以我们所说的推衍的大概意思就是，把一个领域的成果平行地转移到另外一个领域，说不定就能发挥起效！希望本文在这方面能够给大家一些启示。一、平均值与中位数：一对死缠烂打的概念平均数是统计学中用来衡量总体水平的一个统计量。但是，显然它并不“完美”。举个例子，现在房间里有6个人，他们的不尽相同，但又相差无几，这时我们可以说他们的平均身价是100万元。这个平均数基本上是有意义的，因为在假设前提下，我们知道他们6个人的财富或多或少都在100万元上下。现在马云突然来了，然后房间里变成7个人了。同样的问题，房间里所有的人平均身价可能已经突破100亿，但是这个平均数就没有什么意义了。现在房间里没有谁的身价在100亿上下。这时就引出了中位数的概念！把一组数从小到大排列，取中间位置的那个数来作为衡量该组总体水平的一个统计量。如果取包含马云在内的7个人之财富的中位数，我们知道应该还是100万左右，那么它显然是有意义的，它至少代表了这个总体中绝大多少人的情况。你看出中位数的意义和作用了吗？现在当数据点分布比较均匀的时候，平均值是有意义的。但是一旦数据中存在异常值时，平均数就有可能失灵，这时就要用中位数来排除掉异常值的影响。但是平均数仍然有存在的价值，（只是某些时候我们要对其进行修正）。例如比赛时的打分机制，通常是“去掉一个最高分，去掉一个最低分，然后去平均值”。显然在体育比赛打分中，用中位数就不合适。所以我们说平均数和中位数就是一对死缠烂打的狐朋狗友！后面的内容会讨论这对概念在图像处理和数据挖掘中的重要应用。这涉及到简单平滑、中值滤波、K-means算法、k-Median算法等。你应该注意体会前面谈到的推衍创新思维。这能很好地帮助你举一反三。二、简单平滑与中值滤波：同时联系到LeetCode上一道Hard级别的题目现实中图像因为受到环境的影响，很容易被噪声所污染。如下图中的左上所示，这是一幅被椒盐噪声污染的图像。噪声体现为原本过渡平滑的（自然图像）区域中一个突兀的像素值。处理它最简单的策略是用一个低通滤波器对信号进行过滤。比如可以采用简单平滑算法。说白了，就是针对某个像素点，在其领域的一个小窗口内（例如3×3），对所有像素值取平均，然后用这个平均值来代替窗口中心位置的像素值。这样就能缩小噪声和非噪声像素之间的差距。也就是让原本高的值变低一点，而让原本低的值变高一点。结果如左下图所示。易见，简单平滑有一定效果，但是并不“完美”。举个例子，现在有一杯碱性溶液（PH&7），我们不断向其中加入纯水来稀释，结果PH值会越来越小。但是无论我们放多少水，这个值也不可能小于7。就算用尽全世界的水，它的整体仍然呈现碱性！有没有更好的办法？如果你还没有想到用中位数来替代均值，那么我觉得你的头脑应该不用再继续读下去了！既然（椒盐）噪声是一个异常值，那么显然用中位数的方法来将其排掉是最好的选择了，这就是所谓的“中值”滤波的基本思想。上图右下就是采用中值滤波算法处理的图像，显然比简单平滑效果好。但是，问题还没完！你有没有想过中值滤波相对于简单平滑的一个不足或者劣势？是的，中值滤波的复杂度太高，计算起来那是相当的耗时。为什么我会想到这个话题。因为最近我在更新我的MagicHouse（一款小型的图像处理http://blog.csdn.net/baimafujinji/article/details/）。原来中值滤波算法是由我的刘师弟完成的。他曾经是腾讯管家研发的最初核心成员，现在已经自主创业变成刘总了~我也顺便遥祝他宏图大展：）。刘同学写的中值滤波没有采用进行任何优化措施（当然这也是为了算法演示之用，如果优化了别人比较难把握原始算法的核心思想），每次执行起来都跟感觉死机了一样。于是最近我决定重写这个算法。有兴趣的读者不妨搜一下关于中值滤波的加速算法，结论是这方面的paper很多，但我不得不告诉你大部分其实没啥创新。很多都是在串行转并行上下功夫，我真不认为这有啥意义。因为它们的基础仍然是下面我要谈的两个算法。首先来看Leetcode上一道评级为Hard级别的题目，如下。两个有序数组，求它们合并后的中位数。这当然没啥难的，你可能会想到合并后用一个quicksort()，然后取中间位置。结果上当然可以得到正确答案。但是一定要注意：题目要求算法时间复杂度是O(log(t))，t是合并后数组的长度。但是，quicksort()的复杂度应该是O(t·log(t))。显然这样做行不通。满足时间复杂度要求才是本题的难点！有没有什么好方法？题目给出的提示是要用“分治法”策略。而且你应该能想到是，我们要取中位数的两个子数组本来就是有序的，这个条件必须要好好利用。所以，本题的策略应该是：该方法的核心是将原问题转变成一个寻找第k小数的问题（假设两个原序列升序排列），这样中位数实际上是第(m+n)/2小的数。所以只要解决了第k小数的问题，原问题也得以解决。首先假设数组A和B的个数都大于k/2，我们比较A[k/2-1]和B[k/2-1]两个元素，这两个元素分别表示A的第k/2小的元素和B的第k/2小的元素。这两个元素比较共有三种情况：&、&和=。如果A[k/2-1]&B[k/2-1]，这表示A[0]到A[k/2-1]的元素都在A和B合并之后的前k小的元素中。换句话说，A[k/2-1]不可能大于两数组合并之后的第k小值，所以我们可以将其抛弃。反之亦然，所以当A[k/2-1]&B[k/2-1]时，我们将抛弃B[0]到B[k/2-1]的元素。当A[k/2-1]=B[k/2-1]时，则已经找到了第k小的数，也即这个相等的元素，将其记为m。由于在A和B中分别有k/2-1个元素小于m，所以m即是第k小的数。(这里可能有人会有疑问，如果k为奇数，则m不是中位数。当然这种情况我们后面给出的代码里已有做特殊考虑，但整个算法的大体思路并无不同)通过上面的分析，我们即可以采用递归的方式实现寻找第k小的数。此外还需要考虑几个边界条件：&&& 如果A或者B为空，则直接返回B[k-1]或者A[k-1]；&&& 如果k为1，我们只需要返回A[0]和B[0]中的较小值；&&& 如果A[k/2-1]=B[k/2-1]，返回其中一个；最终实现的代码为：double findKth(vector&int&& nums1, int size1, vector&int&::iterator it1,
vector&int&& nums2, int size2, vector&int&::iterator it2, int k)
//Always assume that size1 is equal or smaller than size2
if (size1 & size2)
return findKth(nums2, size2, it2, nums1, size1, it1, k);
if (size1 == 0)
return *(it2+k-1);
if (k == 1)
return min(*it1, *it2);
//Divide k into two parts
int offset1 = min(k / 2, size1);
int offset2 = k - offset1;
if (*(it1+offset1-1) &= *(it2+offset2-1))
return findKth(nums1, size1 - offset1 , it1+offset1, nums2, offset2, it2, k - offset1);
return findKth(nums1, offset1, it1, nums2, size2 - offset2, it2+offset2, k - offset2);
double findMedianSortedArrays(vector&int&& nums1, vector&int&& nums2) {
int m = nums1.size();
int n = nums2.size();
int total = m +
double result = findKth(nums1, m, nums1.begin(), nums2, n, nums2.begin(), (total + 1) / 2);
if ((total & 1) == 0)
result = (result +
findKth( nums1, m, nums1.begin(), nums2, n, nums2.begin(), total / 2 + 1)) / 2;
通过对上述LeetCode题目的讨论，其实已经可以给出我们一些优化的想法了。来看下面这个图，当我们最初计算红色像素的邻域中值时，其实已经得到了红框中像素值的一个有序排列。然后在计算绿色像素的邻域中值时，我们把滑块向后移动。这时为了避免重复计算，一定要充分利用之前的有序结果。剔除最左面三个像素后的红框中的6个像素仍然有序，这时只要把新加入的绿框中的三个元素也做排序，然后得到两个有序的序列，是不是就变成了上我们讨论的问题了？而且，这个算法面对更大的滑动窗口时，优势会更为明显。但是，如果我们只想计算3×3邻域内的中值，其实还有另外一个选择。例如下面的邻域0&& 1&& 23&& 4&& 56&& 7&& 8首先对窗口内的每一列分别计算最大值，中值和最小值，这样就得到了3组数据最大值组：Max0 = max[P0，P3，P6]，Max1 = max[P1，P4，P7]，Max2 = max[P2，P5，P8]中值组： Med0 = med[P0，P3，P6]，Med1 = med[P1，P4，P7]， Med2 = med[P2，P5，P8]最小值组：Min0 = Min[P0，P3，P6]，Min1 = Min[P1，P4，P7]，Min2 = max[P2，P5，P8]由此可以看到，最大值组中的最大值与最小值组中的最小值一定是9个元素中的最大值和最小值，不可能为中值，剩下7个；中值组中的最大值至少大于5个像素，中值组中的最小值至少小于5个像素，不可能为中值，剩下5个；最大值组中的中值至少大于5个元素，最小值组中的中值至少小于5个元素，不可能为中值，最后剩下3个要比较的元素，即最大值组中的最小值Maxmin，中值组中的中值Medmed，最小值组中的最大值MinMax；找出这三个值中的中值为9个元素的中值。采用上述方法，也会大大降低计算量。可见设计一个好算法永远是那么的重要！三、数据挖掘中的K-means和K-median聚类是将相似对象归到同一个簇中的方法，这有点像全自动分类。簇内的对象越相似，聚类的效果越好。支持向量机、神经所讨论的分类问题都是有监督的学习方式，现在我们所介绍的聚类则是无监督的。其中，K均值（K-means）是最基本、最简单的聚类算法。在K均值算法中，质心是定义聚类原型（也就是机器学习获得的结果）的核心。在介绍算法实施的具体过程中，我们将演示质心的计算方法。而且你将看到除了第一次的质心是被指定的以外，此后的质心都是经由计算均值而获得的。首先，选择K个初始质心（这K个质心并不要求来自于样本数据集），其中K是用户指定的参数，也就是所期望的簇的个数。每个数据点都被收归到距其最近之质心的分类中，而同一个质心所收归的点集为一个簇。然后，根据本次分类的结果，更新每个簇的质心。重复上述数据点分类与质心变更步骤，直到簇内数据点不再改变，或者等价地说，直到质心不再改变。基本的K均值算法描述如下：根据数据点到新质心的距离，再次对数据集中的数据进行分类，如图13-2(c)所示。然后，算法根据新的分类来计算新的质心，并再次根据数据点到新质心的距离，对数据集中的数据进行分类。结果发现簇内数据点不再改变，所以算法执行结束，最终的聚类结果如图13-2(d)所示。对于距离函数和质心类型的某些组合，算法总是收敛到一个解，即K均值到达一种状态，聚类结果和质心都不再改变。但为了避免过度迭代所导致的时间消耗，实践中，也常用一个较弱的条件替换掉“质心不再发生变化”这个条件。例如，使用“直到仅有1%的点改变簇”。尽管K均值聚类比较简单，但它也的确相当有效。它的某些变种甚至更有效， 并且不太受初始化问题的影响。但K均值并不适合所有的数据类型。它不能处理非球形簇、不同尺寸和不同密度的簇，尽管指定足够大的簇个数时它通常可以发现纯子簇。对包含离群点的数据进行聚类时，K均值也有问题。在这种情况下，离群点检测和删除大有帮助。K均值的另一个问题是，它对初值的选择是敏感的，这说明不同初值的选择所导致的迭代次数可能相差很大。此外，K值的选择也是一个问题。显然，算法本身并不能自适应地判定数据集应该被划分成几个簇。最后，K均值仅限于具有质心（均值）概念的数据。一种相关的K中心点聚类没有这种限制。在K中心点聚类中，我们每次选择的不再是均值，而是中位数。这种算法实现的其他细节与K均值相差不大，我们不再赘述。最后我们给出一个实际应用的例子。（代码采用我最喜欢用做数据挖掘的R语言来实现）一组来自世界银行的数据统计了30个国家的两项指标，我们用如下代码读入文件并显示其中最开始的几行数据。可见，数据共分散列，其中第一列是国家的名字，该项与后面的聚类分析无关，我们更关心后面两列信息。第二列给出的该国第三产业增加值占GDP的比重，最后一列给出的是人口结构中年龄大于等于65岁的人口（也就是老龄人口）占总人口的比重。为了方便后续处理，下面对读入的进行一些必要的预处理，主要是调整列标签，以及用国名替换掉行标签（同时删除包含国名的列）。如果你绘制这些数据的散点图，不难发现这些数据大致可以分为两组。事实上，数据中有一半的国家是OECD成员国，而另外一半则属于发展中国家（包括一些东盟国家、南亚国家和拉家）。所以我们可以采用下面的代码来进行K均值聚类分析。对于聚类结果，限于篇幅我们仍然只列出了最开始的几条。但是如果用图形来显示的话，可能更易于接受。下面是示例代码。上述代码的执行结果如图13-3所示。现在如果我问能不能提出另外一种与k-means类似的算法，你会想到什么？如果你能从k-均值算法想到提出k-中值算法，那么你算是没白读这篇！触类旁通，举一反三这招你算真学会了。（我想我已经无需再详细介绍k-中值算法的细节了，基本上和k-means一样，只是把所有均值出现的地方换成中值而已）这个思想看起好像很不起眼，但是你还别说，k-median算法还真的存在，而且是k-means算法的一个重要补充和改进。你可能会说提出k-median算法的人绝对是捡了一个大便宜，这么轻轻松松地就提出了一个足以留名的算法。但其实我想说，真正想到这一点的人，功力也绝对不可小觑。冰冻三尺、非一日之寒。唯有基础扎实，内力深厚的大家才能拥有这般敏锐的创新嗅觉。-------------------------------------------------------------------------------------------------------------------------------------------------------又到了时间了，如果你对算法感兴趣，欢迎关注我的新书《算法之美》，或者关注本。详情请参见 http://blog.csdn.net/baimafujinji/article/details/}