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

Author: Thorsten Ottosen
Contact: thorsten.ottosen@dezide.com
Organization: Dezide Aps
Date: 2007-04-16
Number:WG21/N2246 and J16/07-0106 (revision of n1870, n2099)
Working Group:Library

Abstract

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

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.

Addition to <iterator>

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

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

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

Extend 24.3.4 to include:

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

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

Additions to <algorithm>

Add the following as paragraphs:

25.3.1.5 is_sorted

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

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

  • Effects: Returns the last iterator i in [first,last] for which the range [first,i) is sorted. If std::distance(first,last) < 2, last is returned.
  • Complexity: Linear

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

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

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

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

25.3.6.5 is_heap

template <class RandomAccessIterator> RandomAccessIterator is_heap_until(RandomAccessIterator first, RandomAccessIterator last);

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

  • Effects: Returns the last iterator i in [first,last] for which the range [first,i) is a heap. If std::distance(first,last) < 2, last is returned.
  • Complexity: Linear

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: std::is_heap_until(first,last)==last