std::distance

From cppreference.com

Compiler support
Freestanding and hosted
Language
Standard library
Standard library headers
Named requirements
Feature test macros(C++20)
Language support library
Concepts library(C++20)
Diagnostics library
Memory management library
Metaprogramming library(C++11)
General utilities library
Containers library
Iterators library
Ranges library(C++20)
Algorithms library
Strings library
Text processing library
Numerics library
Date and time library
Input/output library
Filesystem library(C++17)
Concurrency support library(C++11)
Execution control library(C++26)
Technical specifications
Symbols index
External libraries

[edit]

Iterator library

Iterator concepts

indirectly_readable (C++20)
indirectly_writable (C++20)
weakly_incrementable (C++20)
incrementable (C++20)
is-integer-like is-signed-integer-like (C++20)(C++20)

sentinel_for (C++20)
sized_sentinel_for (C++20)
input_iterator (C++20)
output_iterator (C++20)
input_or_output_iterator (C++20)

forward_iterator (C++20)
bidirectional_iterator (C++20)
random_access_iterator (C++20)
contiguous_iterator (C++20)

Iterator primitives

input_iterator_tagoutput_iterator_tagforward_iterator_tagbidirectional_iterator_tagrandom_access_iterator_tagcontiguous_iterator_tag

(C++20)

iter_value_titer_difference_titer_reference_titer_const_reference_titer_rvalue_reference_titer_common_reference_t

(C++20)(C++20)(C++20)(C++23)(C++20)(C++20)

iterator (deprecated in C++17)
iterator_traits
incrementable_traits (C++20)
indirectly_readable_traits (C++20)

Algorithm concepts and utilities

Indirect callable concepts

indirectly_unary_invocableindirectly_regular_unary_invocable

(C++20)(C++20)

indirect_unary_predicate (C++20)
indirect_binary_predicate (C++20)

indirect_equivalence_relation (C++20)
indirect_strict_weak_order (C++20)

Common algorithm requirements

indirectly_movable (C++20)
indirectly_movable_storable (C++20)
indirectly_copyable (C++20)

indirectly_copyable_storable (C++20)
indirectly_swappable (C++20)
indirectly_comparable (C++20)

permutable (C++20)
mergeable (C++20)
sortable (C++20)

(C++20)

(C++20)

(C++26)

reverse_iterator
make_reverse_iterator (C++14)
move_iterator (C++11)
make_move_iterator (C++11)
default_sentinel_tdefault_sentinel (C++20)(C++20)
unreachable_sentinel_tunreachable_sentinel (C++20)(C++20)

front_insert_iterator
back_insert_iterator
inserter
insert_iterator
front_inserter
back_inserter
move_sentinel (C++20)

common_iterator (C++20)
counted_iterator (C++20)
basic_const_iterator (C++23)
const_iterator (C++23)
const_sentinel (C++23)
make_const_iterator (C++23)
make_const_sentinel (C++23)

Stream iterators

istream_iterator
ostream_iterator

istreambuf_iterator
ostreambuf_iterator

Iterator customization points
ranges::iter_move (C++20)
ranges::iter_swap (C++20)

Iterator operations

advance
distance
prev (C++11)
next (C++11)

ranges::advance (C++20)
ranges::distance (C++20)
ranges::prev (C++20)
ranges::next (C++20)

Range access

begincbegin (C++11)(C++14)
rbegincrbegin (C++14)(C++14)

endcend (C++11)(C++14)
rendcrend (C++14)(C++14)

sizessize (C++17)(C++20)
empty (C++17)
data (C++17)

[edit]

Defined in header`<iterator>`
template<class InputIt> typenamestd::iterator_traits<InputIt>::difference_type distance( InputIt first, InputIt last);		(constexpr since C++17)

Returns the number of hops fromfirst tolast.

IfInputIt is notLegacyRandomAccessIterator, the behavior is undefined iflast is notreachable fromfirst.

IfInputIt isLegacyRandomAccessIterator, the behavior is undefined iffirst andlast are neither reachable from each other.

[edit]Parameters

first	-	iterator pointing to the first element
last	-	iterator pointing to the end of the range
Type requirements
- `InputIt` must meet the requirements ofLegacyInputIterator. The operation is more efficient if`InputIt` additionally meets the requirements ofLegacyRandomAccessIterator.

[edit]Return value

The number of increments needed to go fromfirst tolast.

The value may be negative if random-access iterators are used andfirst is reachable fromlast.

(since C++11)

[edit]Complexity

Linear.

However, ifInputIt additionally meets the requirements ofLegacyRandomAccessIterator, complexity is constant.

[edit]Possible implementation

See also the implementations inlibstdc++ andlibc++.

C++98 implementation via tag dispatch, withconstexpr removed
namespace detail{template<class It>constexpr// required since C++17typenamestd::iterator_traits<It>::difference_type do_distance(It first, It last,std::input_iterator_tag){typenamestd::iterator_traits<It>::difference_type result=0;while(first!= last){++first;++result;}return result;} template<class It>constexpr// required since C++17typenamestd::iterator_traits<It>::difference_type do_distance(It first, It last,std::random_access_iterator_tag){return last- first;}}// namespace detail template<class It>constexpr// since C++17typenamestd::iterator_traits<It>::difference_type distance(It first, It last){return detail::do_distance(first, last,typenamestd::iterator_traits<It>::iterator_category());}
C++17 implementation viaifconstexpr
template<class It>constexprtypenamestd::iterator_traits<It>::difference_type distance(It first, It last){using category=typenamestd::iterator_traits<It>::iterator_category; static_assert(std::is_base_of_v<std::input_iterator_tag, category>); ifconstexpr(std::is_base_of_v<std::random_access_iterator_tag, category>)return last- first;else{typenamestd::iterator_traits<It>::difference_type result=0;while(first!= last){++first;++result;}return result;}}

C++98 implementation via tag dispatch, withconstexpr removed

namespace detail{template<class It>constexpr// required since C++17typenamestd::iterator_traits<It>::difference_type         do_distance(It first, It last,std::input_iterator_tag){typenamestd::iterator_traits<It>::difference_type result=0;while(first!= last){++first;++result;}return result;} template<class It>constexpr// required since C++17typenamestd::iterator_traits<It>::difference_type         do_distance(It first, It last,std::random_access_iterator_tag){return last- first;}}// namespace detail template<class It>constexpr// since C++17typenamestd::iterator_traits<It>::difference_type     distance(It first, It last){return detail::do_distance(first, last,typenamestd::iterator_traits<It>::iterator_category());}

C++17 implementation viaifconstexpr

template<class It>constexprtypenamestd::iterator_traits<It>::difference_type    distance(It first, It last){using category=typenamestd::iterator_traits<It>::iterator_category;    static_assert(std::is_base_of_v<std::input_iterator_tag, category>); ifconstexpr(std::is_base_of_v<std::random_access_iterator_tag, category>)return last- first;else{typenamestd::iterator_traits<It>::difference_type result=0;while(first!= last){++first;++result;}return result;}}

[edit]Example

Run this code

#include <iostream>#include <iterator>#include <vector> int main(){std::vector<int> v{3,1,4};std::cout<<"distance(first, last) = "<< std::distance(v.begin(), v.end())<<'\n'<<"distance(last, first) = "<< std::distance(v.end(), v.begin())<<'\n';// the behavior is undefined (until LWG940) staticconstexprauto il={3,1,4};// Since C++17 `distance` can be used in constexpr context.    static_assert(std::distance(il.begin(), il.end())==3);    static_assert(std::distance(il.end(), il.begin())==-3);}

Output:

distance(first, last) = 3distance(last, first) = -3

[edit]Defect reports

The following behavior-changing defect reports were applied retroactively to previously published C++ standards.

DR	Applied to	Behavior as published	Correct behavior
LWG 940	C++98	the wording was unclear for the case wherefirst is reachable fromlast	made clear

[edit]See also

advance	advances an iterator by given distance (function template)[edit]
countcount_if	returns the number of elements satisfying specific criteria (function template)[edit]
ranges::distance (C++20)	returns the distance between an iterator and a sentinel, or between the beginning and end of a range (algorithm function object)[edit]