我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:六合公式 > 仿函数 >

C++中 std::sort 时间复杂度是多少? 是用来sort vect的

归档日期:05-24       文本归类:仿函数      文章编辑:爱尚语录

  可选中1个或多个下面的关键词,搜索相关资料。也可直接点“搜索资料”搜索整个问题。

  一般用的都是快速排序,最好、正常和平均时间复杂度都为O(nlog2n),2为底的对数,最坏情况就是数据已经或者近乎有序,当然就是O(n^2)了

  展开全部STL中为我们提供的最重要的两个内容是容器(vector,list等)和一系列的算法。在这些算法中有许多需要遍历容器中的所有元素,如search,sort等算法。STL的设计者希望将算法和容器分离开来,一个算法可以帮不同的容器实现功能。为此目的,STL应用到了《设计模式》中提到的迭代器模式。

  《设计模式》中将迭代器模式定义为:提供一种方法,使之能依序遍历容器中的每个元素,而不需要暴露容器内部的信息。在面向对象的设计里,实现迭代器,我们会为所有的迭代器提供一个统一的接口,然后更个容器的迭代器继承这个接口,然后在使用处通过接口来实现对不同迭代器的调用。但STL是采用泛型思维,利用摸版来实现的类库,所以它的迭代器的实现和面向对象稍有不同,但原理类似。在此将通过例子来具体看看STL中迭代器的实现。

  find()函数的功能是在一个容器中查找一个元素,需要遍历两个迭代器对象_first和_last所在的区间。在此我们看到它对区间的遍历是通过++__first来实现的。也就是说迭代器需要重载++运算符来实现对容器的遍历。来具体看看vector和list中的迭代器实现。

  我们知道vector中的元素是连续存放的,类似于数组,在数组中可以通过指针很容易的实现对数组的遍历,在vector中也一样,并不需要提供给它专门的迭代器类,通过指针就可以实现迭代器的功能。看看例子:

  例子中,我对find做了改动,改成了myfind,这是因为3.3.1的源代码中加入了traits技巧(在VC中我们是可以直接用find的),稍后我们将讲到该问题。但这里可以看到,通过指针就可以实现对vector的遍历。一般我们对迭代器的使用是如下的方式:

  这里需要借助vector来定义迭代器,这里主要是为容器的使用提供一种统一的方式。因为list容器不能通过指针来实现遍历,它们需要实现自己的迭代器。我们来看看在vector中对于iterator的实现:

  在此可以看到iterator在vector中也只是简单的被定义成了我们传入的类型参数T的指针(在3.3.1的代码中与这里的代码并不一样,还是traits的原因)。我们使用迭代器的一般方式是如下:

  这里可以看到,只是为vector设置一个头指针和尾指针,然后通过begin和end来得到这两个指针。

  list就不可以直接通过指针来实现迭代器了,因为它里面的元素是不连续的。需要我们自己去实现,我们先把list的定义抽出来看看。

  为了便于理解,我将代码进行了简单的修改,事实上3.3.1里的代码要比这个要复杂一些。一般来说设计一个链表,我们会把它分成两部分:_List_node用来存放数据,list用来操作链表。这样,迭代器实际传回的应该是_List_node,当它向前遍历的时候,传回的应该是它的下一个结点。按着这个结构,为链表来设计一个迭代器,如下:

  我们可以看到,迭代器中重载了==,!=,*,++等操作符,这是因为这些操作是在算法中经常要用到的操作符。看看myfind中实现,就可以明白:

  这里要用到两个迭代器的比较(__first != __last),所以我们需要重载等于运算符;迭代器中值的比较(*__first == __val),这时候比较的不再是迭代器,而是迭代器所包含的内容(这里是_List_node的对象),所以我们需要重载*来得到它;最重要的就是遍历的实现,需要重载++运算符,这里是通过node = (_List_nodeT*)((*node)._M_next);将迭代器中的_List_node对象改为它的下一个对象来实现的。这样我们就完成了迭代器的设计。再来看看它的用法:

  实际的迭代器的设计中,还会重载--和-运算符,感兴趣的可以自己看看源代码。还是和vector一样,STL会把迭代器的定义绑定到list类中去,我们来看看它的具体做法:

  从此可以看到迭代器就是为各个容器生成一个可以迭代自身的类,而再通过typedef来把该迭代类绑定到容器类中,这样就给了外部一个形式统一的使用方法。

  除了遍历,迭代器中还用到了一个重要的技巧——traits。我们先来看看traits的用处。

  该方法是用来实现两个迭代器中内容的交换,我们可以看到此处需要一个临时变量tmp,而tmp所对应的类型是它所包含的对象的类型。这样我们就需要传入一个类型参数T*进去,如果我们不想传这个参数进去可不可以呢?这时候就需要用到traits技巧了。事实上traits并没有什么太难理解的部分,还是看看例子:

  事实上,在迭代器中还会包括指针,引用,还有就是两个迭代器之间距离的类型。所以迭代器的中的实际代码应该如下:

  这样具体的算法中就可以根据这些内容来定义自己所需要的类型了(STL的实际定义中和这里有些不同,在容器类(vector,list)中已经定义了这些类型,迭代器是再通过容器类定义,不过原理是一致的)。另外,STL中还提供了一个自己的萃取机,如下:

  似乎这段代码并没有使代码变的方便?想想,我们的vector中并没有定义迭代器类,只是直接把指针当作了迭代器。如果直接用以上的代码明显是会出问题的,因为指针根本没有value_type这些信息。为了这种情况,STL中提供了萃取机中针对指针的偏特化版本:

  这样vector对象就可以使用myiter_swap了,不然肯定编译不过去。还有一些针对其它类型(如常量指针)的偏特化版本,可以自己看看源码。

  1, Input Iterator 这种类型的迭代器不允许外界改变,是唯读的。

  5, Random Access Iterator 可以读写,前后移动,并且支持p+n型的操作,也就是说可以前后移动多位,而不是一个一个的移动。

  可以看到它们并没有实际的代码,只是作为一个标记来用的。具体作用的话,还是通过函数来看看。STL的算法中提供了这样一个函数distance,它的作用是求出两个迭代器之间的距离,为了统一,函数可能写成这样:

  这样的话,vector和list都可以使用这个函数,但这样一来,vector也需要遍历两个迭代器之间的所有内容了。但事实上,我们知道vector是连续的区间,完全可以通过两个迭代器之间的相减操作来完成这个计算。如果采用以上的操作,会降低它的效率。有什么办法来区分这两种操作呢?通过迭代器类型就可以完成,还是看看代码:

  可以看到,STL提供了__distance的两个重载函数:一个针对input_iterator_tag,使用的我们上面提到的遍历的方法;一个针对random_access_iterator_tag,采用的直接相减的方法。并提供了distance函数,在该函数里通过

  展开全部ctor,list等)和一系列的算法。在这些算法中有许多需要遍历容器中的所有元素,如search,sort等算法。STL的设计者希望将算法和容器分离开来,一个算法可以帮不同的容器实现功能。为此目的,STL应用到了《设计模式》中提到的迭代器模式。

  《设计模式》中将迭代器模式定义为:提供一种方法,使之能依序遍历容器中的每个元素,而不需要暴露容器内部的信息。在面向对象的设计里,实现迭代器,我们会为所有的迭代器提供一个统一的接口,然后更个容器的迭代器继承这个接口,然后在使用处通过接口来实现对不同迭代器的调用。但STL是采用泛型思维,利用摸版来实现的类库,所以它的迭代器的实现和面向对象稍有不同,但原理类似。在此将通过例子来具体看看STL中迭代器的实现。

  find()函数的功能是在一个容器中查找一个元素,需要遍历两个迭代器对象_first和_last所在的区间。在此我们看到它对区间的遍历是通过++__first来实现的。也就是说迭代器需要重载++运算符来实现对容器的遍历。来具体看看vector和list中的迭代器实现。

  我们知道vector中的元素是连续存放的,类似于数组,在数组中可以通过指针很容易的实现对数组的遍历,在vector中也一样,并不需要提供给它专门的迭代器类,通过指针就可以实现迭代器的功能。看看例子:

  例子中,我对find做了改动,改成了myfind,这是因为3.3.1的源代码中加入了traits技巧(在VC中我们是可以直接用find的),稍后我们将讲到该问题。但这里可以看到,通过指针就可以实现对vector的遍历。一般我们对迭代器的使用是如下的方式:

  这里需要借助vector来定义迭代器,这里主要是为容器的使用提供一种统一的方式。因为list容器不能通过指针来实现遍历,它们需要实现自己的迭代器。我们来看看在vector中对于iterator的实现:

  在此可以看到iterator在vector中也只是简单的被定义成了我们传入的类型参数T的指针(在3.3.1的代码中与这里的代码并不一样,还是traits的原因)。我们使用迭代器的一般方式是如下:

  这里可以看到,只是为vector设置一个头指针和尾指针,然后通过begin和end来得到这两个指针。

  list就不可以直接通过指针来实现迭代器了,因为它里面的元素是不连续的。需要我们自己去实现,我们先把list的定义抽出来看看。

  为了便于理解,我将代码进行了简单的修改,事实上3.3.1里的代码要比这个要复杂一些。一般来说设计一个链表,我们会把它分成两部分:_List_node用来存放数据,list用来操作链表。这样,迭代器实际传回的应该是_List_node,当它向前遍历的时候,传回的应该是它的下一个结点。按着这个结构,为链表来设计一个迭代器,如下:

  我们可以看到,迭代器中重载了==,!=,*,++等操作符,这是因为这些操作是在算法中经常要用到的操作符。看看myfind中实现,就可以明白:

  这里要用到两个迭代器的比较(__first != __last),所以我们需要重载等于运算符;迭代器中值的比较(*__first == __val),这时候比较的不再是迭代器,而是迭代器所包含的内容(这里是_List_node的对象),所以我们需要重载*来得到它;最重要的就是遍历的实现,需要重载++运算符,这里是通过node = (_List_nodeT*)((*node)._M_next);将迭代器中的_List_node对象改为它的下一个对象来实现的。这样我们就完成了迭代器的设计。再来看看它的用法:

  实际的迭代器的设计中,还会重载--和-运算符,感兴趣的可以自己看看源代码。还是和vector一样,STL会把迭代器的定义绑定到list类中去,我们来看看它的具体做法:

  从此可以看到迭代器就是为各个容器生成一个可以迭代自身的类,而再通过typedef来把该迭代类绑定到容器类中,这样就给了外部一个形式统一的使用方法。

  除了遍历,迭代器中还用到了一个重要的技巧——traits。我们先来看看traits的用处。

  该方法是用来实现两个迭代器中内容的交换,我们可以看到此处需要一个临时变量tmp,而tmp所对应的类型是它所包含的对象的类型。这样我们就需要传入一个类型参数T*进去,如果我们不想传这个参数进去可不可以呢?这时候就需要用到traits技巧了。事实上traits并没有什么太难理解的部分,还是看看例子:

  事实上,在迭代器中还会包括指针,引用,还有就是两个迭代器之间距离的类型。所以迭代器的中的实际代码应该如下:

  这样具体的算法中就可以根据这些内容来定义自己所需要的类型了(STL的实际定义中和这里有些不同,在容器类(vector,list)中已经定义了这些类型,迭代器是再通过容器类定义,不过原理是一致的)。另外,STL中还提供了一个自己的萃取机,如下:

  似乎这段代码并没有使代码变的方便?想想,我们的vector中并没有定义迭代器类,只是直接把指针当作了迭代器。如果直接用以上的代码明显是会出问题的,因为指针根本没有value_type这些信息。为了这种情况,STL中提供了萃取机中针对指针的偏特化版本:

  这样vector对象就可以使用myiter_swap了,不然肯定编译不过去。还有一些针对其它类型(如常量指针)的偏特化版本,可以自己看看源码。

  1, Input Iterator 这种类型的迭代器不允许外界改变,是唯读的。

  5, Random Access Iterator 可以读写,前后移动,并且支持p+n型的操作,也就是说可以前后移动多位,而不是一个一个的移动。

  可以看到它们并没有实际的代码,只是作为一个标记来用的。具体作用的话,还是通过函数来看看。STL的算法中提供了这样一个函数distance,它的作用是求出两个迭代器之间的距离,为了统一,函数可能写成这样:

  这样的话,vector和list都可以使用这个函数,但这样一来,vector也需要遍历两个迭代器之间的所有内容了。但事实上,我们知道vector是连续的区间,完全可以通过两个迭代器之间的相减操作来完成这个计算。如果采用以上的操作,会降低它的效率。有什么办法来区分这两种操作呢?通过迭代器类型就可以完成,还是看看代码:

  可以看到,STL提供了__distance的两个重载函数:一个针对input_iterator_tag,使用的我们上面提到的遍历的方法;一个针对random_access_iterator_tag,采用的直接相减的方法。并提供了distance函数,在该函数里通过

本文链接:http://renfriends.com/fanghanshu/439.html