STL distance函数

STL distance函数教程

STL 中的 distance() 函数用于计算两个迭代器表示的范围内包含元素的个数。

STL distance函数头文件

语法

#include <iterator>
using namespace std;

说明

值得一提的是，distance() 函数定义在 <iterator> 头文件，并位于 std 命名空间中。

STL distance函数详解

语法

template<class InputIterator>
typename iterator_traits<InputIterator>::difference_type distance (InputIterator first, InputIterator last);

参数

参数	描述
first	迭代器。
last	迭代器。

说明

其中，first 和 last 都为迭代器，其类型可以是输入迭代器、前向迭代器、双向迭代器以及随机访问迭代器；该函数会返回 [first, last) 范围内包含的元素的个数。

技术细节

first 和 last 的迭代器类型，直接决定了 distance() 函数底层的实现机制：

当 first 和 last 为随机访问迭代器时，distance() 底层直接采用 last - first 求得 [first, last) 范围内包含元素的个数，其时间复杂度为O(1)常数阶；
当 first 和 last 为非随机访问迭代器时，distance() 底层通过不断执行 first（或者 first）直到 first==last，由此来获取 [first, last) 范围内包含元素的个数，其时间复杂度为O(n)线性阶。

案例

distance获取迭代器距离

使用 distance 获取迭代器距离

#include <iostream>
#include <iterator>
#include <list>
using namespace std;
int main()
{
	cout << "嗨客网(www.haicoder.net)\n" << endl;
    list<int> mylist;
    for (int i = 0; i < 10; i++) 
    {
        mylist.push_back(i);
    }
    list<int>::iterator first = mylist.begin();
    list<int>::iterator last = mylist.end();
    cout << "distance() = " << distance(first, last);
    cout << endl;
    return 0;
}

我们在 Linux 下使用 g++ 进行编译，具体命令如下：

g++ reverse_iterator.cpp -std=c++11

编译后，我们直接运行生成的二进制文件 a.out，如下图所示：

16_STL distance函数.png

我们使用了 distance 函数，获取了两个迭代器之间的距离。

STL distance函数总结

STL 中的 distance() 函数用于计算两个迭代器表示的范围内包含元素的个数。