3 of the least crazy ideas for the standard library in C++0x

Author: Thorsten Ottosen
Contact: tottosen@dezide.com
organizations:Dezide Aps
Date: 2006-09-08
Number:WG21/N2099 and J16/06-0169 (revision of n1870)
Working Group:Evolution

Abstract

This paper provides wording for 3 of the least controversial of the 14 crazy ideas for enhancing the standard library.

Table of Contents

Introduction

The motivation for these additions is discussed in n1870.

Each numbered section below describes a new section for the standard or modifications to an existing section. Comments are written in bold and are not part of the wording. Footnotes are not part of the wording.

Addition to <iterator>

Extend the synopsis after distance() of 23.2 to include:

template<class ForwardIterator>
ForwardIterator next(ForwardIterator x, typename std::iterator_traits<ForwardIterator>::difference_type n = 1);

template< class ForwardIterator >
ForwardIterator prior(ForwardIterator x, typename std::iterator_traits<ForwardIterator>::difference_type n = 1);

Extend 24.3.4 to include:

template<class ForwardIterator> ForwardIterator next(ForwardIterator x, typename std::iterator_traits<ForwardIterator>::difference_type n = 1);

template<class ForwardIterator> ForwardIterator prior(ForwardIterator x, typename std::iterator_traits<ForwardIterator>::difference_type n = 1);

Additions to <algorithm>

Add the following as paragraphs:

25.3.1.4 is_sorted

template<class ForwardIterator> RandomAccessIterator is_sorted_until(ForwardIterator first, ForwardIterator last);

template<class ForwardIterator, class Compare> RandomAccessIterator is_sorted_until(ForwardIterator first, ForwardIterator last, Compare comp );

  • Effects: Returns the last iterator ì in [first,last] for which the range [first,i) is sorted or first if no such iterator exists.
  • Complexity: Linear

template<class ForwardIterator> bool is_sorted(ForwardIterator first, ForwardIterator last);

  • Returns: is_sorted_until(first,last)==last

template<class ForwardIterator, class Compare> bool is_sorted(ForwardIterator first, ForwardIterator last, Compare comp );

  • Returns: is_sorted_until(first,last,comp)==last

25.3.6.5 is_heap

template <class RandomAccessIterator> bool is_heap(RandomAccessIterator first, RandomAccessIterator last);

template <class RandomAccessIterator, class Compare> bool is_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp)

  • Returns: whether the range [first,last) is a heap [1].

Additions to <numeric>

Extend the synopsis after adjacent_difference() of 26.6 to include:

template< class T, class InputIterator >
T mean( InputIterator first, InputIterator last );

template< class T, class ForwardIterator >
T variance( ForwardIterator first, ForwardIterator last );

Add the following as paragraphs:

26.6.5 mean

template< class T, class InputIterator > T mean( InputIterator first, InputIterator last );

  • Effects: Let N be std::distance(first,last). Then the result is 0 if N is 0 and otherwise the result is equivalent to std::accumulate(first,last,T(0))/N.
  • Complexity: Linear

26.6.5 variance

template< class T, class ForwardIterator > T variance( ForwardIterator first, ForwardIterator last );

  • Effects: Returns the unbiased statistical variance using operator+() to calculate sums.
  • Complexity: Linear
  • Remarks: The algorithm is not a single-pass algorithm [2].

Footnotes

[1]At the Berlin meeting we discussed that I could choose to provide wording for is_heap_until() just like we have wording for is_sorted_until(). However, I have no idea of how to use, implement nor specify the requirement of such a beast. Is it even possible?
[2]A single pass algorithm is prone to floating point inaccuracies.