ite = vec.begin(); 3、迭代器相应类别 既然迭代器要把两个独立的部件算法和容器撮合在一起,那么相应的类别必须得一样;当然,编译器是自带参数推导的,就比如函数模板,它是会自己推导出传递的是什么类型...typename I::value_type //这一行都是func的返回类型(因为I是一个template参数,在编译器具现之前,编译器对I一无所知,使用typename可以告诉编译器这是一个类型...func(I ite){ return *ite; } 但是指针不能内嵌类型,如果迭代器是一个原生指针不就无法内嵌吗?... class Demo {}//这就是类型上的特化,只接受原生指针; 回到之前的问题;算法和容器两个独立的部件靠迭代器撮合一起的,那必须对应的类型要一样,就好比是这样一个场景...你知道吗? 迭代器如果说不知道,,那就类型不对就无法进行下去了,如果说知道,那算法就直接说,那好,我要对你指向的容器进行操作了,这样操作自然而然的就通顺了,,那迭代器是怎么回答算法这个问题的呢?
C++ STL 源码剖析之 Traits 编程技法 0.导语 在 STL 编程中,容器和算法是独立设计的,即数据结构和算法是独立设计的,连接容器和算法的桥梁就是迭代器了,迭代器使其独立设计成为可能。...而在算法中我们可能会定义简单的中间变量或者设定算法的返回变量类型,这时候需要知道迭代器所指元素的类型是什么,但是由于没有 typeof 这类判断类型的函数,我们无法直接获取,那该如何是好?...参数推导 首先,在算法中运用迭代器时,很可能会用到其相应型别(associated type)(迭代器所指之物的型别)。...假设算法中有必要声明一个变量,以"迭代器所指对象的型别"为型别,该怎么办呢? 解决方法是:利用 function template 的参数推导机制。...只要做一个 iterator,然后在定义的时候为其指向的对象类型制定一个别名,就好了,像下面这样: template struct MyIter { typedef T value_type
std::vector 是一个类模板,它的定义如下: template > class vector; 模板参数...对于涉及在末尾以外的位置插入或删除元素的操作,它们的性能比其他操作差,并且迭代器和引用的一致性低于列表和forward_lists。...是输入迭代器类型,可以是指向数组的指针、其他容器的迭代器等。...非 const 版本: iterator begin(); 返回类型: iterator,这是一个指向容器第一个元素的迭代器。 用途: 可以用于遍历和修改容器中的元素。...需要注意的是,在调用 insert 函数时,如果 vector 的大小需要扩张以容纳新的元素,则会自动分配新的内存空间。这可能会导致迭代器、指针和引用失效,因此在使用这些元素时需要格外小心。
---- 0x1 C++ STL C++ STL(标准模板库)是一套功能强大的 C++ 模板类,提供了通用的模板类和函数,这些模板类和函数可以实现多种流行和常用的算法和数据结构,如向量、链表、队列...每一种容器都有其优点和缺点,所以为了应付程序中的不同需求,STL 准备了七种基本容器类型。 迭代器(Iterators):用来在一个对象集合的元素上进行遍历动作。...(优点) 总结:相当于可拓展的数组(动态数组),随机访问快,在头部和中间插入或删除效率低,但在尾部插入或删除效率高,适用于对象简单,变化较小,并且频繁随机访问的场景。...val = value_type(), const allocator_type& alloc = allocator_type()) template list...(优点) 总结:由红黑树实现,其内部元素依据其值自动排序,每个元素值只能出现一次,不允许重复,且插入和删除效率比用其他序列容器高,适用于经常查找一个元素是否在某集合中且需要排序的场景。
不要被事务的表面现象锁迷惑,你看它是分段连续线性空间,就以为它是vector和list的结合体,取长补短?其实不然。 为了维持整体连续的假象,数据结构的设计及迭代器前进后退等操作都颇为繁琐。...---- deque的中控器 deque采用一块所谓的map映射,来看吧: template class...此外,deque还维护start、finish两个迭代器,分别指向第一缓冲区的第一个元素和最后缓冲区的最后一个元素(的下一个位置)。...原先我也疑惑于为何同一级中左边的节点会比右边节点大,后来我想明白了。 在插入过程中,这个顺序被打乱是难以避免的,况且这个排序于取出数据并无影响,所以没必要在做额外工作对树的底层做那么精细的排序。...下面来看一下算法的实现细节: //该函数接受两个迭代器,用来表现一个heap底部容器的头尾,并且新元素已经插入到底部容器的最尾端。
5.1 迭代器的advance函数 STL中的advance函数,可用于将迭代器向前(后)推进N步。...同时,我们可以以迭代器类别作为Advance函数的第三参数,从而重载出多个不同版本的Advance函数。...此时,只要我们使用迭代器类别(作为第三参数)去调用__Advance函数,编译器就将根据重载确定规则,选择适用于当前迭代器类别的__Advance函数进行调用了。...但最后,我们还有一个重要问题需要解决:指针也是迭代器,那么指针的迭代器类型(当然是随机访问迭代器)怎么获取? 也许不用我说,你就已经知道答案了,解决方案就是“加中间层可解决一切问题”定理。...7.6 让标量也加入进来 在数学中,一个向量不仅可以和另一个向量相加,还可以和一个标量(即一个T类型的值)相加。本节我们就来实现这一功能。
一、迭代器 迭代器是泛型指针 普通指针可以指向内存中的一个地址 迭代器可以指向容器中的一个位置 STL的每一个容器类模版中,都定义了一组对应的迭代器类。...与前向迭代器相似,但是在两个方向上都可以对数据遍历 随机访问迭代器 也是双向迭代器,但能够在序列中的任意两个位置之间进行跳转 下图是不同类型的迭代器能够实现的操作: ?...map, set, list类型提供双向迭代器,而string, vector和deque容器上定义的迭代器都是随机访问迭代器,用作访问内置数组元素的指针也是随机访问迭代器。...2、在其首部或尾部删除元素则只会使指向被删除元素的迭代器失效。 3、在deque容器的任何其他位置的插入和删除操作将使指向该容器元素的所有迭代器失效。 ...众所周之当使用一个容器的insert或者erase函数通过迭代器插入或删除元素"可能"会导致迭代器失效,因此建议我们获取insert或者erase返回的迭代器,以便用重新获取新的有效的迭代器进行正确的操作
heap,可能听过的人不多,这篇主要留给我和有缘人看吧。 1、heap是什么 heap并不属于STL容器组件,它是个“幕后白手”,扮演priority queue的助手。...原先我也疑惑于为何同一级中左边的节点会比右边节点大,后来我想明白了。 在插入过程中,这个顺序被打乱是难以避免的,况且这个排序于取出数据并无影响,所以没必要在做额外工作对树的底层做那么精细的排序。...下面来看一下算法的实现细节: //该函数接受两个迭代器,用来表现一个heap底部容器的头尾,并且新元素已经插入到底部容器的最尾端。...接下来将尾节点和原根节点的两个子节点比较大小,将大的那个推上根节点。见上图步骤三。同样留下一个洞洞。 循环这个“向下流放”的过程,直到原尾结点插入树中或者到了最底层。见上图步骤四。...2.4 heap迭代器 嘿嘿,那当然是没有迭代器了,所有元素都必须遵循特别的排列规则,又不提供遍历功能,要什么迭代器。
在模板定义语法中关键字class与typename的作用完全一样。 typename难道仅仅在模板定义中起作用吗?...在声明一个 template type parameter(模板类型参数)的时候,class 和 typename 意味着完全相同的东西。...它是一个用糊涂的方法实现的糊涂的函数,而且就像我下面写的,它甚至不能编译,但是请将这些事先放在一边——有一种方法能发现我的愚蠢: template // print 2nd...例如,这是一个取得一个 container(容器)和这个 container(容器)中的一个 iterator(迭代器)的 function template(函数模板): template<typename...假设我们在写一个取得一个 iterator(迭代器)的 function template(函数模板),而且我们要做一个 iterator(迭代器)指向的 object(对象)的局部拷贝 temp,我们可以这样做
sort函数的应用场景 SGI STL中的sort的参数是两个随机存取迭代器RandomAccessIterator,sort的模板也是基于此种迭代器的,因此如果容器不是随机存取迭代器,那么可能无法使用通用的...关联容器 map和set底层是基于RB-Tree,本身就已经自带顺序了,因此不需要使用sort算法 序列容器 list是双向迭代器并不是随机存取迭代器,vector和deque是随机存取迭代器适用于sort...快速排序和堆排序的配合 __introsort_loop函数中主要封装了快速排序和堆排序,来看看这个函数的实现细节: //sort函数的入口 template <class RandomAccessIterator...堆排序的细节 //注:这个是带自定义比较函数的堆排序版本 //堆化和堆顶操作 template ...= last; ++i) __linear_insert(first, i, value_type(first)); } 在插入函数中同样出现了__unguarded_xxx这种形式的函数
模版元程序由元数据和元函数组成,元数据就是元编程可以操作的数据,即C++编译器在编译期可以操作的数据。...元函数是模板元编程中用于操作处理元数据的“构件”,可以在编译期被“调用”,因为它的功能和形式和运行时的函数类似,而被称为元函数,它是元编程中最重要的构件。...4.模板元编程的控制逻辑 第一个 C++ 模板元程序由Erwin Unruh 在 1994 年编写,这个程序计算小于给定数 N 的全部素数(又叫质数),程序并不运行(都不能通过编译),而是让编译器在错误信息中显示结果...我们想让 mysum() 对指针参数也能工作,毕竟迭代器就是模拟指针,但指针没有嵌套类型 value_type,可以定义 mysum() 对指针类型的特例,但更好的办法是在函数参数和 value_type...有了这样的判断,还可以根据判断结果做更复杂的元编程逻辑(如一个算法以迭代器为参数,根据迭代器标签进行特例化以对某种迭代器特殊处理)。标签还可以用来分辨函数重载。
iterator_traits 被称为特性萃取机,能够方面的让外界获取以下5中型别: value_type:迭代器所指对象的型别 difference_type:两个迭代器之间的距离 pointer:迭代器所指向的型别...连续存储结构:vector是可以实现动态增长的对象数组,支持对数组高效率的访问和在数组尾端的删除和插入操作,在中间和头部删除和插入相对不易,需要挪动大量的数据。...vector中的迭代器在使用后就失效了,而list的迭代器在使用之后还可以继续使用。...list与vector的另一个区别是,在插入和接合操作之后,都不会造成原迭代器失效,而vector可能因为空间重新配置导致迭代器失效。...deque和vector的最大差异一个是deque运行在常数时间内对头端进行元素操作,二是deque没有容量的概念,它是动态地以分段连续空间组合而成,可以随时增加一段新的空间并链接起来 deque虽然也提供随机访问的迭代器
explicit 关键字仅在只提供了 n 参数的情况下有作用,当同时提供 n 和 val 时,可以使用复制初始化 Range constructor (range (3)): template 中的 这个函数是非成员函数,被用来在一个序列中查找一个特定的值。...:vector 的 insert 方法用于在向量中的指定位置插入元素。...如果 position 是向量的 end() 迭代器,则新元素被添加到向量的末尾。
是运行修改的,所以 map 的普通迭代器封装红黑树的普通迭代器即可,而不用将其封装为红黑树的 const 迭代器; 同时,我们也不用担心 map 的 key 被修改的问题,因为 map 在定义红黑树的成员变量时传递给红黑树的...– 在前面map 和 set 的使用那一节中我们知道 map 支持 [] 访问,并且 map 的 operator[] 其实同时具备插入、查找和修改 (修改 value) 的功能,下面我将之前博客中的图放出来便于大家回忆...insert 函数的返回值进行返回,而是先将它的返回值赋值给一个键值对,该键值对由红黑树的普通迭代器和一个布尔值构成,然后再用该键值对构造一个由红黑树的 const 迭代器 (set 的普通迭代器)...答案在红黑树的迭代器中 – 可以看到红黑树的迭代器中貌似实现了一个拷贝构造函数,但奇怪的地方在于该函数的参数是一个普通迭代器,而不是 Self,而这就是关键所在: 当模板实例化为 ...现在我们参照 stl 源码的思路来改造我们的迭代器和 set insert 函数: __RBTreeIterator: template struct
,这正是适配器的核心思想 ---- ️正文 反向迭代器适用于所有的容器,因此它是作为一个单独的 .h 文件出现的,别的容器如果想使用,直接包含就行了 1、反向迭代器设计 反向迭代器 reverse_iterator...可以用来反向遍历容器,在某些场景下很实用 反向迭代器类中需要有:正向迭代器对象、构造函数 template struct __reverse_iterator {...结果:1 2 3 4 5 反向迭代器:反向遍历 结果:5 4 3 2 1 注:库中的反向迭代器在设计时,为了最求极致的对称,rbegin() 指向最后一个有效元素的下一个位置,rend() 指向第一个有效元素...Ref;同理,在涉及 operator->() 时,需要返回目标对象指针,使用 Ptr 具体返回对象(引用 / 指针)是否为 const 修饰,取决于调用方 1.3、极致对称 在反向迭代器类中,有一个十分奇怪的函数...vector 和 list 进行了测试,成功实现了反向遍历 如果你觉得本文写的还不错的话,可以留下一个小小的赞,你的支持是我分享的最大动力!
说明一下,我用的是gcc7.1.0编译器,标准库源代码也是这个版本的。 本篇文章讲述STL中array的使用及原理。...{ ... }; 有些书上说array也是一个class,但是我这个版本看到的是struct,不过没有关系,除了一些细微的方面,struct和class并无太大的区别,这里可以看到array...迭代器函数 //这里value_type就是定义一个array时指定的元素类型,比如在上面的例子中,它就是int类型 typedef value_type*...: 一是同样的函数可以返回可读可写和只读两种,比如begin,同样的函数名和参数,只是返回类型和const属性不一样; 二是反转迭代器反转一下其实是指向当前位置的前一个元素的迭代器,也就是说除了位置反转了...operator[]和at函数都实现了两个,与上面的迭代器一样,根据左值判断具体调用哪一个函数。
STL(Standard Template Library)标准模板库提供了模板适配器和迭代器等重要概念,为开发者提供了高效、灵活和方便的编程工具。...模板适配器是指一组模板类或函数,它们提供一种适配机制,使得现有的模板能够适应新的需求。而迭代器则是STL中的令一种重要的概念,它是一个抽象化的数据访问机制,通过迭代器可以遍历STL容器中的元素。...适配器与迭代器两者的紧密配合,使得开发者能够高效地处理容器中的元素,提高了代码的复用性和可维护性。10.1 函数对象适配器Bind2nd 是一个函数适配器,可以用来将一个双参函数转换成一个单参函数。...;其中Predicate是一个一元谓词,而返回值是一个封装了谓词的std::unary_negate对象,它是一个可调用的函数对象,并可以在STL的算法函数中使用。...是STL提供的两种迭代器适配器,它们分别用于将输入流和输出流封装成迭代器的形式,以便于使用STL提供的算法函数处理输入和输出流。
STL(Standard Template Library)标准模板库提供了模板适配器和迭代器等重要概念,为开发者提供了高效、灵活和方便的编程工具。...模板适配器是指一组模板类或函数,它们提供一种适配机制,使得现有的模板能够适应新的需求。而迭代器则是STL中的令一种重要的概念,它是一个抽象化的数据访问机制,通过迭代器可以遍历STL容器中的元素。...适配器与迭代器两者的紧密配合,使得开发者能够高效地处理容器中的元素,提高了代码的复用性和可维护性。...); 其中Predicate是一个一元谓词,而返回值是一个封装了谓词的std::unary_negate对象,它是一个可调用的函数对象,并可以在STL的算法函数中使用。...这两种适配器都是在使用中间层的帮助下实现容器的插入操作,其主要作用是在输出迭代器(通常是一个容器)的末尾自动添加新的元素。
---- 前言 vector 是 STL 中的容器之一,其使用方法类似于数据结构中的 顺序表,得益于范型编程和 C++ 特性的加持,vector 更强大、更全能;在模拟实现 vector 时,还需要注意许多细枝末节...2、迭代器相关 vector 中的迭代器就是原生指针,如 begin() == _start、end() == _finish typedef T value_type; typedef value_type...,即 const 对象的 const 迭代器 反向迭代器在后续文章中进行专门讲解 利用前面的函数构造对象,在通过迭代器遍历对象,结果如下 ---- 3、容量相关 3.1、查看容量 直接通过迭代器获取值...返回值,更新迭代器 } 注意: erase 后,也会出现迭代器失效情况,在 PJ 版本中,对 erase 迭代器失效情况零容忍,只要是删除后没有即使更新迭代器,就会直接报错;而在 SGI 版中,...vector 模拟实现的全部内容了,感兴趣的同学可以自己试着写一下,不过需要特别注意 深度拷贝 和 迭代器失效 问题 如果你觉得本文写的还不错的话,可以留下一个小小的赞,你的支持是我分享的最大动力!
map篇 放码过来 map的迭代器 自定义排序 [] 运算符重载函数 C++map迭代器的++操作是如何实现的?...value_type; //key_compare 和 value_compare 也用到了同一个比較函数 typedef Compare key_compare; typedef Compare...找到则返回元素位置的迭代器,不然返回end()。 这个我熟,就不多说了。...,并返回指向该元素的迭代器 s.upper_bound(x)表示查找>x的元素中最小的一个,并返回指向该元素的迭代器 举个例子: 在set{3,5,7,8,13,16}中 对于在set中存在的元素,比如...8 s.lower_bound(8)返回8所在位置的迭代器 s.upper_bound(8)返回13所在位置的迭代器 对于在set中不存在的元素,比如12 两个函数返回的则都是13所在位置的迭代器 特殊地
领取专属 10元无门槛券
手把手带您无忧上云