Difference between revisions of "cpp/named req/RandomAccessIterator"

Revision as of 14:28, 23 May 2012

A RandomAccessIterator is a Template:concept that can be moved to point to any element in constant time.

A standard pointer is an example of a type that satisfies this concept.

In addition to the above requirement, for a type It to be an RandomAccessIterator, instances a, b, i, and r of It must:

Expression	Return	Equivalent expression	Notes
r += n	It&	if(n>=0) while(n--) ++r; else while(n++) --r; return r;	`n` can be both positive or negative Constant complexity (that is, the equivalent expression cannot be used as implementation)
i + n	It	It temp = i; return i += n;
n + i	It	i + n
r -= n	It&	return r += -n;
i - n	It	It temp = i; return i -= n;
n - i	It	i - n
b - a	`difference`	`n`	returns `n` such that a+b==b
i[n]	convertible to `reference`	*(i + n)
a < b	contextually convertible to bool	b - a > 0	Strict total ordering relation: `!(a < a)` if `a < b` then `!(b < a)` if `a < b` and `b < c` then `a < c` `a < b` or `b < a` or `a == b` (exactly one of the expressions is true)
a > b	contextually convertible to bool	b < a	Total ordering relation opposite to a < b
a >= b	contextually convertible to bool	!(a < b)
a <= b	contextually convertible to bool	!(a > b)

The above rules imply that RandomAccessIterator also implements Template:concept.

@@ Line 8: / Line 8: @@
 ===Requirements===
-Satisfies {{concept|BidirectionalIterator}} and, additionally, the following requirements:
+* {{concept|BidirectionalIterator}}
+In addition to the above requirement, for a type {{tt|It}} to be an {{tt|RandomAccessIterator}}, instances {{tt|a}}, {{tt|b}}, {{tt|i}}, and {{tt|r}} of {{tt|It}} must:
 {|table class="wikitable"