C++ 的容器通过迭代器访问和通过下标访问有效率差别吗？
在C++中使用容器时迭代器的速度为什么比使用下标的速度慢很多，在做leetcode4sum时，使用同样的方法迭代器超时，下标Acceptd
按投票排序
你应该把代码贴出来，以及编译的选项，然后做Profile后再做定论。如果要我回答，这两个应该不会有差别，比如你试试 -O2优化选项。如我简单的测试：#include &vector&
#include &cstddef&
int main()
std::vector& int & vec ();
int value = 0;
for(int idx =0; idx & 100 ; ++idx)
// -std=c++11 -O2 ~0.250 secs
for (auto I = vec.cbegin(), E = vec.cend(); I != E; ++I)
value = *I;
// -std=c++11 -O2 ~0.250 secs
for(unsigned i = 0, length = vec.size(); i != length; ++i)
value = vec[i];
在我这里的表现几乎是一致的。
debug build得到的代码在加入了很多检测，如迭代器越位、有效性、是否指向同一容器等等，另外很多层小函数调用，导致严重变慢。但是，所有这些变慢在release build都会消除，对vector的迭代器来说，并不比下标慢。而且，由于下标到迭代器的代码风格转换，使用迭代器的代码实测甚至往往比下标还快。我曾经在vc11上得到过迭代器更快的测试结果。
leetcode没开编译优化
可能是因为对容器的改动 使得之前保存的迭代器失效了
有区别比如你开了一个vector容器，然后你要把从1～100加起来的话迭代器就是从一访问到一百一共100次。因为vector动态分配内存是链表实现，所以访问第n个数必须从1for到n。所以实际访问数组下表访问次数是5050次。所以要速度慢1520人阅读
共通操作：
返回迭代器 iter 所指向的元素的引用
对 iter 进行解引用，获取指定元素中名为 mem 的成员。等效于 (*iter).mem
++iter iter++
给 iter 加 1，使其指向容器里的下一个元素
--iter iter--
给 iter 减 1，使其指向容器里的前一个元素
iter1 == iter2 iter1 != iter2
比较两个迭代器是否相等（或不等）。当两个迭代器指向同一个容器中的同一个元素，或者当它们都指向同一个容器的超出末端的下一位置时，两个迭代器相等
只有vector 和 deque 类型迭代器支持的操作：
iter + n iter - n
在迭代器上加（减）整数值 n，将产生指向容器中前面（后面）第 n 个元素的迭代器。新计算出来的迭代器必须指向容器中的元素或超出容器末端的下一位置
iter1 += iter2 iter1 -= iter2
这里迭代器加减法的复合赋值运算：将 iter1 加上或减去 iter2 的运算结果赋给 iter1
iter1 - iter2
两个迭代器的减法，其运算结果加上右边的迭代器即得左边的迭代器。这两个迭代器必须指向同一个容器中的元素或超出容器末端的下一位置
&, &=, &, &=
迭代器的关系操作符。当一个迭代器指向的元素在容器中位于另一个迭代器指向的元素之前，则前一个迭代器小于后一个迭代器。关系操作符的两个迭代器必须指向同一个容器中的元素或超出容器末端的下一位置
版权声明：本文为博主原创文章，未经博主允许不得转载。
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：33216次
排名：千里之外
原创：58篇
(1)(1)(1)(1)(1)(1)(2)(2)(5)(4)(1)(23)(20)C++笔记：迭代器 | 宁心勉学，慎思笃行
C++笔记：迭代器 ceeji
C++语言学习, CPlusPlus目录迭代器的概念迭代器的基本使用获取迭代器迭代器的运算C++ Primer 3.4 习题 3.17 答案代码（Ceeji 原创，装载请注明作者和出处）除了在其它语言中司空见惯的下标法访问容器元素之外，C++ 语言提供了一种全新的方法——迭代器（iterator）来访问容器的元素。迭代器其实类似于引用，指向容器中某一元素。我个人认为，迭代器的产生，主要是为了统一各类容器的穷举接口，因为各类容器中，只有 vectoer 等少量容器模板支持通过下标访问。使用迭代器则不存在这个问题。C++ 标准库为每一种标准库类型提供了配套的迭代器类型。例如，std::vector::iterator 就是一种迭代器类型。迭代器分为普通迭代器和常量迭代器（const_iterator）。两者的区别是，常量迭代器在使用时，不能修改其指向的元素，在这一点上，类似于 const 指针。下面的代码例子使用迭代器穷举 vector 对象。 std::vector&int&::iterator iter;
for (iter = list.begin(); iter != list.end(); ++iter)
std::cout && *iter;
}标准库类型一般都提供了 begin(), end() 成员函数来获取指向第 0 个元素和最后一个元素的后继元素位置的迭代器。注意：end() 本身并不指向任何已存在的元素，而是指向最后一个元素的后继位置。上面的代码例子可以清晰的看出这一点。以下的代码获取 const 迭代器。vector&int& list;
vector&int&::const_iterator iter = list.begin(); 解引用操作符：所有迭代器都提供了解引用操作符（*），可作为左值，用于获取迭代器所指向的元素。以下代码都是合法的。std::cout && *iter;
*iter = 5;
*iter = *iter + 5;取后继元素操作符：所有迭代器都可以通过 iter++、++iter 操作符获取其后继元素的迭代器。其它运算符：相等、不等操作符等，这些不用多说。一些顺序容器（如 vector）的迭代器提供了更多的运算，例如+=，-=等，使用 iter +=3 可以让 iter 指向三个元素之后。这些迭代器还可以互相减。例如，list.end() – list.begin() 获取的其实是list的size。/* C++ Primer 3.4 習題 3.17
* 題目: 讀一組整數到 vector 對象，計算每隊相鄰元素的和，頭尾元素兩兩配對求和，並輸出。若元素為奇數，提示最後一個元素未求和。（使用迭代器）
* 使用 文件結束符結束輸入。參見 http://ceeji.net/blog/cpp-learn-io/。
#include &iostream&
#include &vector&
using std::cin;
using std::cout;
using std::endl;
using std::vector;
int main()
vector&int& list;
while (cin && tmp)
list.push_back(tmp);
vector&int&::iterator iter;
for (iter =
list.begin(); iter + 1 & list.end(); iter += 2)
cout && &Sum: & && (*iter + *(iter + 1)) && endl;
if (iter & list.end())
cout && &The last value is not sumed.& && endl;
vector&int&::iterator last;
for (iter = list.begin(), last = list.end() - 1; last & iter; ++iter, --last)
cout && &Sum: & && (*iter + *last) && endl;
}大家都在看我的保送生考试啊 - 49,350 次浏览我的庚寅年计划亚克西！ - 40,313 次浏览我最喜歡的《詩經&國風&周南》詩句 - 28,041 次浏览RealChinese : Simplified to Traditional Converter (Extension) Chrome 簡轉繁擴展 - 27,684 次浏览河南省2010年信息学奥林匹克竞赛试题（HAOI2010） - 24,152 次浏览实数范围内的求模（求余）运算：负数求余究竟怎么求 - 21,464 次浏览【成绩】百度NOIP吧编程挑战赛成绩公布 - 21,206 次浏览链表结构原理 与 数组模拟链表 的应用 - 20,281 次浏览std::vector : 用法与技巧 - 19,496 次浏览百度NOIP吧编程挑战赛作弊嫌疑人名单 - 17,234 次浏览Enjoy English : My expectation of learning English in the new term - 16,807 次浏览&一家人杯&程序设计大赛 标准程序 - 16,533 次浏览首次南下旅遊遊記（四）無錫 - 16,107 次浏览HAOI 聪明的猴子 解题报告 - 15,556 次浏览比赛环境测试赛 成绩 数据 题解 - 15,495 次浏览这是一段故事的开端 - 15,266 次浏览2010年河南高考分数线 - 15,231 次浏览收到了武漢大學錄取通知書及其附件 - 14,074 次浏览光阴荏苒&恍若隔世 - 13,905 次浏览分别的时刻 - 13,773 次浏览该使用 SSH 还是该使用 VPN？ - 13,193 次浏览如何开始学习繁体字？ - 13,131 次浏览让你的 QQ 拼音输入法输入更精准的繁体中文 - 12,390 次浏览百度NOIP吧编程挑战赛 解题报告 - 12,364 次浏览徹底解決 Ubuntu 10.04 對部分聲卡不支持或耳機無聲的問題 - 11,618 次浏览《仙剑奇侠传五》音乐资源提取器 - 11,234 次浏览文件同步利器 Dropbox 试用感受 - 10,607 次浏览&一家人&杯程序设计竞赛 文字版题目 - 10,360 次浏览C++笔记：迭代器 - 10,298 次浏览Sun VirtualBox 主机与虚拟机组建局域网 - 10,180 次浏览分类导航C#CPlusPlusC++语言学习Linux中華文化互联网技术信息学竞赛信息学竞赛学习笔记SSD1化学笔记心情随记思考数据结构文学与情感未分类杂文讽趣算法精品转载新近发表 Javascript 中的 undefined 与 未定义（not defined） 加入我们，一起边做边学！ iPhone 手机QQ 4.7.2 版本网络状态泄露用户隐私 宋卿体育馆与六一惨案 Nginx 无法处理软链接作为网站主目录的情况友情链接Boolean93Ceeji: 笃志者CockRoachErLiuyue乐乐嘎嘎乐客V8优哉·幽斋南极游者盛光帮助积微细著，自就鸿文笔记第二仙境落月潇湘边做边学醉鄉酒壚饭盒迭代器除了在STL中遍历序列对象外，还有其他更多的迭代器被iterator所定义。iterator头文件定义迭代器的几个模板将数据从源传到目的地。流迭代器（stream iterator）作为指向输入或输出流的指针，它们可以用来在流和任何使用迭代器的源或目的地之间传输数据，如算法。插入迭代器（inserter iterator）可以将数据传输给一个基本的序列容器。Iterator头文件定义了两个流迭代器模板，其中istream_iterator&T&用于输入流，ostream_iterator&T&用于输出流，T是要从流中提取的或者写入流中的对象类型。头文件还定义了三个插入模板：inserter&T&、back_inserter&T&和front_inserter&T&，其中T是在其中插入数据的序列容器的类型。
输入流迭代器
创建输入流迭代器：
istream_iterator&int& input(cin);
此代码创建了一个istream_iterator&int&类型的迭代器 input，可以指向流中int类型的对象。这个构造函数的实指定与迭代器相关的实际流，因此它是一个可以从标准输入流cin中读取整数的迭代器。默认的istream_iterator&T&构造函数创建一个end-of-stream迭代器。它等价于通过调用容器的end()函数获得容器的end迭代器。下面代码说明了如何创建cin的end-of-stream迭代器来补充input迭代器：
istream_iterator&int& inputE
现在有了一对迭代器，定义cin中一个int类型的值的序列，可以用这些迭代器将cin中的值加载到vector&int&中。
vector&int&
cout&&&input numbers , end by zero&&&
istream_iterator&int& input(cin),inputE
while(input != inputEnd)
numbers.push_back(*input++);
可以看出，只要不是cin的end-of-stream，就会继续执行while输入数据，那么怎样才会产生end-of-stream的条件了，可以输入Ctrl+Z或输入一个无效的字符（如字母），就会产生end-of-stream条件。
当然，不只限于只能使用输入流迭代器作为循环的控制变量。它们可以向算法传递数据，如numeric头文件中的accumulate()。
cout&&&input numbers separated by spaces and a letter to end&&&
istream_iterator&int& input(cin),inputE
cout&&&the sum of you inputed numbers is &
&&accumulate(input,inputEnd,0)&&
sstream头文件定义basic_istringstream&T&类型，这个类型定义可以访问流缓冲区中的数据的对象类型，如string对象。这个头文件还将类型istringstream定义为basic_istringstream&char&，它将是char类型的字符流。可以从string对象中构造一个istringstream对象，这意味着从string对象中读取数据，就像从cin中读取数据一样。因为istringstream对象是一个流，所以可将它传递给一个输入迭代器构造函数，并用该迭代器访问底层流缓冲区中的数据。如：
string data[] = {&1.2 12.6 3.6 98 5.3 7.1&};
Istringstream input(data);
Istream_iterator&double& begin(input),
cout&&&the sum of you inputed numbers is &
&&accumulate(begin,end,0.0)&&
由于从string对象data中创建istringstream对象，因此可以像流一样从data中读取数据。此处accumulate()的第三个参数应为0.0，因为第三个参数确定结果的类型，此处保证返回double类型的值。
#include &iostream&
#include &iomanip&
#include &string&
#include &map&
#include &iterator&
using std::
using std::
using std::
using std::string;
int main()
std::map&string, int&
// Map to store words and word counts
cout && "Enter some text and press Enter followed by Ctrl+Z then Enter to end:"
&& endl &&
std::istream_iterator&string& begin(cin); // Stream iterator
std::istream_iterator&string&
// End stream iterator
while(begin != end )
// Iterate over words in the stream
words[*begin++]++;
// Increment and store a word count
// Output the words and their counts
cout && endl && "Here are the word counts for the text you entered:" &&
for(auto iter = words.begin() ; iter != words.end() ; ++iter)
cout && std::setw(5) && iter-&second && " " && iter-&first &&
插入迭代器
插入迭代器(inserter iterator)是一个可以访问序列容器vector&T&、deque&T&和list&T&添加新元素的迭代器。有3个创建插入迭代器的模板：
Back_insert_iterator&T&在类型T的容器末尾插入元素。容器必须提供push_back()函数。
Front_insert_iterator&T&在类型T的容器开头插入元素。同样push_front()对容易可用。
Insert_iterator&T&在类型T的容器内从指定位置开始插入元素。这要求容器有一个insert()函数，此函数接受两个参数，迭代器作为第一个实参，要插入的项作为第二个实参。
前两个插入迭代器类型的构造函数接受一个指定要在其中插入元素的容器的实参。如：
front_insert_iterator&list&int& & iter(numbers);
向容器中插入值：
*iter = 99;
也可以将front_inserter()函数用于numbers容器：
front_inserter(numbers) = 99;
这几行代码为numbers列表创建了一个前段插入器，并用它在开头插入99。front_inserter()函数的实参是运用迭代器的容器。
insert_iterator&T&迭代器的构造函数需要两个实参：
insert_iterator&vector&int& & iter(numbers,numbers.begin());
该构造函数的第二个实参是一个指定在何处插入数据的迭代器。向此容器赋值：
for (int i = 0; i & 100; i++)
*iter = i + 1;
代码执行后，前100个元素的值依次为100，99，&，1。
输出流迭代器
为了补充输入流迭代器模板，ostream_iterator&T&模板提供了向输出流写类型T的对象的输出流迭代器。
ostream_iterator&int& out(cout);
该模板的实参int指定要处理的数据类型，构造函数实参cout指定将作为数据的目的地的流，以便cout迭代器能将int类型的值写到标准输出流中。如：
int data [] = {1,2,3,4,5,6,7,8,9};
vector&int& numbers(data,data+9);
copy(numbers.begin(),numbers.end(),out);
在algorithm头文件中定义的copy()算法将由前两个迭代器实参指定的对象序列复制到第三个实参指定的输出迭代器。此代码执行结果为：.
但现在写到标准输出流中的值没有空格。第二个输出流迭代器构造函数能解决这一点：
ostream_iterator&int& out(cout,& &);
现在将输出1 2 3 4 5 6 7 8 9
#include &iostream&
#include &numeric&
#include &vector&
#include &iterator&
using std::
using std::
using std::
using std::
using std::istream_
using std::ostream_
using std::back_
using std::
int main()
vector&int&
cout && "Enter a series of integers separated by spaces"
&& " followed by Ctrl+Z or a letter:" &&
istream_iterator&int& input(cin), input_
ostream_iterator&int& out(cout, " ");
copy(input, input_end, back_inserter&vector&int&&(numbers));
cout && "You entered the following values:" &&
copy(numbers.begin(), numbers.end(), out);
cout && endl && "The sum of these values is "
&& accumulate(numbers.begin(), numbers.end(), 0) &&
阅读(...) 评论()1163人阅读
0 关于计算机语言中的命名
在计算机语言中，一个对象不管它被取为什么名字，只要知道它是用来干什么的即可。不必太纠结于它的名字，它没有行不改名坐不改姓的江湖气息，自己如果觉得有一个更适合的名字可以在自己私人空间里给它再取一个小名供自己使用。但是一般来说，它之所以会被取为这个名字是有道理且合适的，只不过对于新手来说这些名字听起来过于“高级”就形成陌生感，咱可以从它的用途出发，为自己的理解再为其命一次名。
1 容器（container）
在生活中，容器从玻璃容器、布料容器等可以具体化到生活中具体的存储物体。当我们需要喝水时可能就需要“水杯”这个容器来容水；当我们马上要去逛街时可能需要“钱包”这个容器来存储钱。在生活中，容器不具体指明它就是“水杯”、“钱包”，但它在具体需要的时候容器就可以具体的指“水杯”、“钱包”及其它的容器对象。
在C++中，容器从vector容器[ vector只是一个似乎符合它的名字而已]、map容器等容器可以具体化到容纳C++具体的内建数据类型或者自定class类型。当C++需要用一片连续内存存储整型数据时我们可能需要vector&int&[
&&内的数据类型用来表示此vector对象所要存储内容的数据类型 ]容器来存储它们；当C++需要在一个节点存储两个数据类型分别为string、int时且每个节点以关联方式存储时我们可能需要map&string,
int&类型容器来存储它们。C++ STL中的每一类型容器vector，map（跟生活中容器玻璃类、布料类对应）之所以能够进一步标识为C++的内建数据类型或自建Class类型，是因为STL中的容器是采用类模板方式来实现的。
（2）构造容器
容器的构造形式如下：
container&type1, type2&& container_
container表示STL中具体的容器类，如vector、map。
type表示要用此容器来存储的具体数据类型，C++内建或者自定义class。”&&”内能定义的数据类型个数视具体的container类而定。
container_object为具体的被声明的容器对象
一种容器作为一个类，它其中必定包含自己的成员函数，这些成员函数就是用来执行一些对存入数据的操作（如在某位置插入/删除元素）或作为迭代器及算法的联系点（使用这些函数成员就能够和迭代器或者算法对应起来）。
首先根据当前需求决定要使用的数据类型，然后根据这种数据类型的特点来匹配STL中每种容器的特点，然后选择一种您觉得最佳的容器来定义容器对象。
1.如现在需要在程序中声明一组按顺序存储在一起的具有相同数据类型的数据类型，咱打算怎么做呢？
方式1：根据这个所需存储数据类型特点咱可以使用数组嘛。
如果这些数据是int那就定义一个整型数组int in_data[SIZE];如果这些所需存储的数据是……依次类推似的定义。
方式2：使用vector容器来具体的存储这类数据嘛。
如果这些数据是整型的，那就将vector具体的定义为存储整型数据的容器vector&int&& v_in_如果这些所需存储的数据是……依次类推似的定义。
2.如现在需要在程序中定义一组…….
类似1的做法……
方式1：使用对应的简单数据类型或者定义结构体来存储数据
方式2：使用容器
那么在每一种数据类型的需求下我们首先都可以通过结构体来完成对数据的存储，也可以通过C++中STL中的容器来存储。那么咱们要使用哪一种呢。其实这个没什么具体的标准来规定应该使用哪一种。只是STL中已经将容器、迭代器及算法集成了一套，更加可能的为用户带来更高校的编码方式而已。所以，在C++中，推荐直接用STL容器来解决数据问题的情况要多一些，但如果您对结构体及对应的算法已经炉火纯青…使用什么都是一样。
2 迭代器（iterator）
迭代器这个名字取的有点怪兮兮的。书中所述迭代器类似于指针用来帮助用户更加便利的遍历容器。而且迭代器也是采用类模板的思想来设计的，它可以根据具体容器的具体数据类型来定义得到此容器对应的迭代器。如vector&int&::iterator v_in_语句表示v_in_it为容器vector&int&对象下的迭代器。容器、迭代器及算法被成套的集在C++
STL中，它们之间定有来供用户使用它们三个。
vector&int& v_
vector&int&::iterator v_in_it_1 =& v_in.begin();
vector&int&::iterator v_in_it_2=& v_in.end();
第一语句表示声明了一个空的vector&int&对象。第二语句v_in对象使用begin()函数返回v_in容器的首地址（第一个元素）并赋值给对应的迭代器对象v_in_it_1。第三语句是返回了v_in容器最后一个元素的地址。此后，就可以通过对迭代器对象v_in_it_1、v_in_it_2的运算来访问容器对象v_in中的元素。
在C/C++中，数组元素可以通过下标或者地址的形式被访问到。vector也可以通过下标的方式访问其中的元素。但是为什么要专门设计一个基于类模板的iterator来供STL容器遍历元素使用呢？
我想迭代器具有类模板的性质导致它能够适用于任意一种容器对象具有通用性是一个原因。
另外用指针来间接的遍历元素似乎已成为一种习惯与爱好（常数地址本身不可改变），每遇到数组时，我们就会定义与此数组类型匹配的指针来遍历此数组元素。
用下标访问元素和用指针访问元素内部过程的区别。
这就是迭代器（iterator），容器利用成员函数（begin等）将容器的某处地址返回并赋值给迭代器，然后迭代器就可以通过运算在容器元素地址之间来回穿梭，为遍历容器元素提供了地址。
3算法（algorithm）
忘记了说重要的一点。容器和算法之间的对应不再需要用成员函数来提供联系，因为这些对容器元素的算法（遍历、排序、索引、删除等）就存在于容器的成员函数之中。这算法只是需要容器中具体元素的下标（通过下标来访问元素），而这个下标就可以通过迭代器（iterator）来提供。
4容器 迭代器 算法 一个语句的关系
其实C++ STL中的这三者的关系没有想象中的那么复杂。就一个语句就能表示这三者的关系：
图1 容器 迭代器 算法的关系
只是不要忘记了这三者都是类，其中都再次包含了自己的数据成员和函数成员。这些成员是为了能够更高效的操作。
此次笔记记录完毕。
版权声明：本文为博主原创文章，未经博主允许不得转载。
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：499446次
积分：8449
积分：8449
排名：第964名
原创：315篇
译文：15篇
评论：239条
(4)(1)(23)(2)(2)(10)(12)(17)(9)(9)(12)(7)(7)(2)(5)(11)(8)(16)(12)(6)(15)(21)(11)(9)(16)(15)(10)(3)(12)(1)(16)(14)(12)
--------老师--------