Tuples and Pairs

Motivation

A number of places in the original 1998 standard libary call for a generic type to handle a pair of values. The template std::pair was born for this purpose.

The proposed library for C++0x includes a generic facility for containers of any fixed number of elements in std::tuple. In retrospect it would be most convenient to maintain a single facility. The addition of template aliases to the language makes that possible, although the semantics of a 2 element tuple are subtly different to std::pair.

Differences between pair and 2-element tuple

first and second

The most obvious difference is that pair elements are traditionally accessed as public data members with the names first and second, where tuple elements are accessed with a free function interface get<N>( tuple ). While the tuple-like free function API is overloaded for pair it is not specifically used in the library wording.

pair value-initializes both members

Another key difference is that where a tuple default-initializes its elements, pair value-initializes them. Therefore, a pair<double, double> will always zero initialize each double element, but a tuple<double, doube> will leave them un-initialized.

Emplace support facilities

pair has an additional variadic constructor template to support argument forwarding to constructors in the new emplace API supported by most containers.

pair is Swappable

This oversight for tuple is LWG issue #522.

Compressed-pair optimization

tuple permits an additional space-saving optimization, as exploited in the boost compressed_pair library.

Proposal

Redefine std::pair as a template alias

Add the following template alias to header <utility>:
template< typename T1, typename T2> using pair = tuple<T1,T2>;

Move whole of <tuple> header into <utility>

It is simpler if the template alias and the template is aliases live in the same header.

Provide a 2 element specialization for tuple

This specialization has the identical specification as std::pair today.

tuple to value-initialize each element

It is not clear that the current tuple interface is completely thought out on this point. One benefit of not mandating value-initialization is that a tuple might be a trivial class or POD, which is never the case for pair. However, if this is the intent then additional wording would be required mandating the new = default syntax for the default constructor, at least in the case that all elements are trivial.

A more subtle problem with the current specification for the tuple default constructor is that it is not possible to safely zero-initialize the elements, unlike with a simple struct. An example to illustrate:

struct pod { double x; double y; };
typedef tuple<double, double > problem;

struct dangerous {
  pod a;
  problem b;

  dangerous() {};
};

struct safe {
  pod a;
  problem b;

  safe()
    : a()
    , b() // no effect
  {
    get<0>(b) = 0.0;
    get<1>(b) = 0.0;
  };

};

Here we use a couple of double elements to show the dangers of default-initialization. As seen in the dangerous constructor a double (or any other trivial type) is not initialized by value-initialization - it could contain any valid state including a signalling NAN. Technically any attempt to access the value of an uninitialized object is undefined behaviour, although this rarely bites in practice.

However, as demonstrated by the safe constructor, the simple struct will safely zero-initialize its elements when explicitly value-intialized because it is a trivial type. This is not the case with the tuple, requiring the suprising additional member-by-member initialization in the constructor body to guarantee safely initialized values.

Remove redundant code

Remove the pair constructor/assignment operator overloads from tuple as they become illegal duplicate definitions.

Remove the overloads for tuple query API on pair as they become illegal partial specializations of a function template, and are no longer necessary.

Define swap for tuple

Resolve LWG issue 522 as indicated below.

Replace all references to pair with tuple

The following library facilities depend on std::pair and should be expressed using tuple instead.

• 20.6.3 get_temporary_buffer
• 23 Associative Container requirements - Emplace/insert/equal_range
• 23.3 map
• 23.3 multimap
• 23.3 unordered_map
• 23.3 unordered_multimap
• 25.1.7 mismatch result
• 25.3.3.3 equal_range result
• 25.3.7 minmax result
• 25.3.7 minmax_element result
• 28.9 regex sub_match

Implications

pair is automatically compatible with the tie and tuple_cat APIs.

Due to recursive definition, all tuples with 2 or more elements will have members first and second, but no higher named members such as third or fourth. Optionally, it might be worthwhile to add the named element first to tuples with a single element.

As all tuple elements are value-initialized, tuples will never be trivial types. There may be an efficiency penalty for code preferring the non-initialization of TR1 tuples, but there is a corresponding pay-off in safety. Traditionally the library prefers efficiency over safety where the latter can be supplied by the diligent developer. However, it is not clear in this case that the diligence required is reasonable.

As the template type name has changed from pair to tuple, it is almost certain to break ABI compatibility, even if the presence of the template alias guaranatees source compatibility.

As the basic template is now std::tuple, and std::pair is merely an alias, it is no longer possible for users to create specializations of pair with their own types.

Discounted options

Use default-initialization for pair members

This was discounted as it is reasonable to assume a large body of existing code relying on the value-initialization of pair's elements.

Mandate trivial type for tuple

Rather than forcing value-intializaiton for each member, mandate that tuple be trivial if all its elements are trivial. This would solve the example given above, but the problem returns when only some of the elements are trivial. For example:

struct mixed { double x; string y; };
typedef tuple<double, string > problem;

struct safe {
  mixed a;
  problem b;

  safe()
    : a()
    , b() // no effect
  {
    get<0>(b) = 0.0;
    // no neeed to initialize get<1>(b)
  };

};

Proposed Wording

Note that this wording also applies an alternative solution to LWG issue 706, currently in Ready status, by explicitly deferring to make_tuple. This new resolution relies on the proposed new function declaration syntax.

Move the whole of 20.2.3 [pairs] to 20.3.2[tuple.pairs].
Remove the <tuple> header synopsis (20.3p2).
Ammend as follows:

namespace std {
  // 20.2.1, operators:
  namespace rel_ops {
    template<class T> bool operator!=(const T&, const T&);
    template<class T> bool operator> (const T&, const T&);
    template<class T> bool operator<=(const T&, const T&);
    template<class T> bool operator>=(const T&, const T&);
  }
  
  // 20.2.2, forward/move:
  template <class T> struct identity;
  template <class T> T&& forward(typename identity<T>::type&&);
  template <class T> typename remove_reference<T>::type&& move(T&&);

  // 20.2.3, pairs:
  template <class T1, class T2> struct pair;
  template <class T1, class T2>
  bool operator==(const pair<T1,T2>&, const pair<T1,T2>&);
  template <class T1, class T2>
  bool operator< (const pair<T1,T2>&, const pair<T1,T2>&);
  template <class T1, class T2>
  bool operator!=(const pair<T1,T2>&, const pair<T1,T2>&);
  template <class T1, class T2>
  bool operator> (const pair<T1,T2>&, const pair<T1,T2>&);
  template <class T1, class T2>
  bool operator>=(const pair<T1,T2>&, const pair<T1,T2>&);
  template <class T1, class T2>
  bool operator<=(const pair<T1,T2>&, const pair<T1,T2>&);
  template <class T1, class T2>
  void swap(pair<T1,T2>&, pair<T1,T2>&);
  template <class T1, class T2>
  void swap(pair<T1,T2>&&, pair<T1,T2>&);
  template <class T1, class T2>
  void swap(pair<T1,T2>&, pair<T1,T2>&&);
  template <class T1, class T2>
  pair<typename decay<T1>::type, typename decay<T2>::type> make_pair(T1&&, T2&&);

  // 20.2.3, tuple-like access to pair:
  template <class T> class tuple_size;
  template <int I, class T> class tuple_element;

  template <class T1, class T2> struct tuple_size<std::pair<T1, T2> >;
  template <class T1, class T2> struct tuple_element<0, std::pair<T1, T2> >;
  template <class T1, class T2> struct tuple_element<1, std::pair<T1, T2> >;

  template<int I, class T1, class T2> P& get(std::pair<T1, T2>&);
  template<int I, class T1, class T2> const P& get(const std::pair<T1, T2>&);
  
  // 20.3.1, class template tuple:
  template <class... Types> class tuple;

  // 20.3.1.2, tuple creation functions:
  const unspecified ignore;

  template <class... Types>
  tuple<VTypes...> make_tuple(Types&&...);

  template<class... Types>
  tuple<Types&...> tie(Types&...);

  template <class... TTypes, class... UTypes>
  tuple<TTypes..., UTypes...> tuple_cat(const tuple<TTypes...>&, const tuple<UTypes...>&);
  template <class... TTypes, class... UTypes>
  tuple<TTypes..., UTypes...> tuple_cat(tuple<TTypes...>&&, const tuple<UTypes...>&);
  template <class... TTypes, class... UTypes>
  tuple<TTypes..., UTypes...> tuple_cat(const tuple<TTypes...>&, tuple<UTypes...>&&);
  template <class... TTypes, class... UTypes>
  tuple<TTypes..., UTypes...> tuple_cat(tuple<TTypes...>&&, tuple<UTypes...>&&);

  // 20.3.1.3, tuple helper classes:
  template <class T> class tuple_size; // undefined
  template <class... Types> class tuple_size<tuple<Types...> >;
  template <int I, class T> class tuple_element; // undefined
  template <int I, class... Types> class tuple_element<I, tuple<Types...> >;

  // 20.3.1.4, element access:
  template <int I, class... Types>
  typename tuple_element<I, tuple<Types...> >::type& get(tuple<Types...>&);
  template <int I, class ... types>
  typename tuple_element<I, tuple<Types...> >::type const& get(const tuple<Types...>&);

  // 20.3.1.5, relational operators:
  template<class... TTypes, class... UTypes>
  bool operator==(const tuple<TTypes...>&, const tuple<UTypes...>&);
  template<class... TTypes, class... UTypes>
  bool operator<(const tuple<TTypes...>&, const tuple<UTypes...>&);
  template<class... TTypes, class... UTypes>
  bool operator!=(const tuple<TTypes...>&, const tuple<UTypes...>&);
  template<class... TTypes, class... UTypes>
  bool operator>(const tuple<TTypes...>&, const tuple<UTypes...>&);
  template<class... TTypes, class... UTypes>
  bool operator<=(const tuple<TTypes...>&, const tuple<UTypes...>&);
  template<class... TTypes, class... UTypes>
  bool operator>=(const tuple<TTypes...>&, const tuple<UTypes...>&);

  template <class... Types>
  void swap(tuple<Types...>&, tuple<Types...>&);
  template <class... Types>
  void swap(tuple<Types...>&&, tuple<Types...>&);
  template <class... Types>
  void swap(tuple<Types...>&, tuple<Types...>&&);

  // 20.3.2, specialization for pairs:
  template <class T1, class T2> using pair = tuple< T1, T2 >;

  template <class T1, class T2>
  auto make_pair(T1&& x, T2&& y) -> dectype(make_tuple(x,y));
}

20.3.1 Class template tuple [tuple.tuple]

template <class... Types>
class tuple
{
public:
  tuple();
  explicit tuple(const Types&...);
  template <class... UTypes>
    explicit tuple(UTypes&&...);
  
  tuple(const tuple&);
  tuple(tuple&&);
  
  template <class... UTypes>
    tuple(const tuple<UTypes...>&);
  template <class... UTypes>
    tuple(tuple<UTypes...>&&);
    
  template <class U1, class U2>
    tuple(const pair<U1, U2>&); // iff sizeof...(Types) == 2
  template <class U1, class U2>
    tuple(pair<U1, U2>&&); // iff sizeof...(Types) == 2
    
  tuple& operator=(const tuple&);
  tuple& operator=(tuple&&);
  
  template <class... UTypes>
    tuple& operator=(const tuple<UTypes...>&);
  template <class... UTypes>
    tuple& operator=(tuple<UTypes...>&&);
    
  template <class U1, class U2>
    tuple& operator=(const pair<U1, U2>&); // iff sizeof...(Types) == 2
  template <class U1, class U2>
    tuple& operator=(pair<U1, U2>&&); // iff sizeof...(Types) == 2
    
  void swap(tuple&&);
};

20.3.1.1 Construction [tuple.cnstr]

tuple();

1 Requires: Each type in Types shall be default constructible.

2 Effects: DefaultValue initializes each element.

20.3.2 Pairs [tuple.pairs]

1 The library provides a partial specialization of class template tuple for heterogeneous pairs of values. The library also provides a matching function template to simplify their construction and several templates that provide access to pair objects as if they were tuple objects (see 20.3.1.3 and 20.3.1.4).

template <class T1, class T2>
struct pairtuple< T1, T2 > {
  typedef T1 first_type;
  typedef T2 second_type;
  T1 first;
  T2 second;
  pairtuple();
  pairtuple(const T1& x, const T2& y);
  template<class U, class V> pairtuple(U&& x, V&& y);
  pairtuple(pairtuple&& p);
  template<class U, class V> pairtuple(const pairtuple<U, V>& p);
  template<class U, class V> pairtuple(pairtuple<U, V>&& p);
  template<class U, class... Args> pairtuple(U&& x, Args&&... args);
  pairtuple& operator=(pairtuple&& p);
  template<class U, class V> pairtuple& operator=(pairtuple<U, V>&& p);
  void swap(pairtuple&& p);
};

template <class T1, class T2> using pair = tuple< T1, T2 >;

pairtuple();

2 Effects: Initializes its members as if implemented: pairtuple() : first(), second() {}

pairtuple(const T1& x, const T2& y);

3 Effects: The constructor initializes first with x and second with y.

template<class U, class V> pairtuple(U&& x, V&& y);

4 Effects: The constructor initializes first with std::forward<U>(x) and second with std::forward<T>(y).

template<class U, class... Args> pairtuple(U&& x, Args&&... args);

5 Effects: The constructor initializes first with std::forward<U>(x) and second with std::forward<Args>(args)...

pairtuple(pairtuple&& p);

6 Effects: The constructor initializes first with std::move(p.first) and second with std::move(p.second).

template<class U, class V> pairtuple(const pairtuple<U, V>& p);

7 Effects: Initializes members from the corresponding members of the argument, performing implicit conversions as needed.

template<class U, class V> pairtuple(pairtuple<U, V>&& p);

8 Effects: The constructor initializes first with std::move(p.first) and second with std::move(p.second).

pairtuple& operator=(pairtuple&& p);

9 Effects: Assigns to first with std::move(p.first) and to second with std::move(p.second).

10 Returns: *this.

template<class U, class V> pairtuple& operator=(pairtuple<U, V>&& p);

11 Effects: Assigns to first with std::move(p.first) and to second with std::move(p.second).

12 Returns: *this.

void swap(pairtuple&& p);

13 Effects: Swaps first with p.first and second with p.second.

14 Requires: first_type and second_type must be Swappable.

    return pair<int, double>(5, 3.1415926); // explicit types

    return make_pair(5, 3.1415926); // types are deduced

20.6.3 Temporary buffers [temporary.buffer]

template <class T>
pairtuple<T*, ptrdiff_t> get_temporary_buffer(ptrdiff_t n);

1 Effects: Obtains a pointer to storage sufficient to store up to n adjacent T objects. It is implementation-defined whether over-aligned types are supported (3.11).

2 Returns: A pairtuple containing the buffer’s address and capacity (in the units of sizeof(T)), or a pair of 0 values if no storage can be obtained or if n <= 0.

23.1.2 Associative containers [associative.reqmts]

23.1.3 Unordered associative containers [unord.req]

23.3 Associative containers [associative]

namespace std {
  template <class Key, class T, class Compare = less<Key>,
            class Allocator = allocator<pairtuple<const Key, T> > >
    class map;

...

  template <class Key, class T, class Compare = less<Key>,
            class Allocator = allocator<pairtuple<const Key, T> > >
    class multimap;

...

}

23.3.1 Class template map [map]

1 A map is an associative container that supports unique keys (contains at most one of each key value) and provides for fast retrieval of values of another type T based on the keys. The map class supports bidirectional iterators.

2 A map satisfies all of the requirements of a container and of a reversible container (23.1) and of an associative container (23.1.2). A map also provides most operations described in (23.1.2) for unique keys. This means that a map supports the a_uniq operations in (23.1.2) but not the a_eq operations. For a map<Key,T> the key_type is Key and the value_- type is pairtuple<const Key,T>. Descriptions are provided here only for operations on map that are not described in one of those tables or for operations where there is additional semantic information.

namespace std {
  template <class Key, class T, class Compare = less<Key>,
            class Allocator = allocator<pairtuple<const Key, T> > >
  class map {
  public:
    // types:
    typedef Key key_type;
    typedef T mapped_type;
    typedef pairtuple<const Key, T> value_type;
    typedef Compare key_compare;
    typedef Allocator allocator_type;
    typedef typename Allocator::reference reference;
    typedef typename Allocator::const_reference const_reference;
    typedef implementation-defined iterator; // See 23.1
    typedef implementation-defined const_iterator; // See 23.1
    typedef implementation-defined size_type; // See 23.1
    typedef implementation-defined difference_type;// See 23.1
    typedef typename Allocator::pointer pointer;
    typedef typename Allocator::const_pointer const_pointer;
    typedef std::reverse_iterator<iterator> reverse_iterator;
    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

    ...
    
    // modifiers:
    template <class... Args> pairtuple<iterator, bool> emplace(Args&&... args);
    template <class... Args> iterator emplace(const_iterator position, Args&&... args);
    pairtuple<iterator, bool> insert(const value_type& x);
    template <class P> pairtuple<iterator, bool> insert(P&& x);
    iterator insert(const_iterator position, const value_type& x);
    template <class P>
    iterator insert(const_iterator position, P&&);
    template <class InputIterator>
    void insert(InputIterator first, InputIterator last);

    ...
    
    // 23.3.1.4 map operations:
    
    pairtuple<iterator,iterator>
      equal_range(const key_type& x);
    pairtuple<const_iterator,const_iterator>
      equal_range(const key_type& x) const;
};

23.3.2 Class template multimap [multimap]

1. A multimap is an associative container that supports equivalent keys (possibly containing multiple copies of the same key value) and provides for fast retrieval of values of another type T based on the keys. The multimap class supports bidirectional iterators.

2. A multimap satisfies all of the requirements of a container and of a reversible container (23.1) and of an associative container (23.1.2). A multimap also provides most operations described in (23.1.2) for equal keys. This means that a multimap supports the a_eq operations in (23.1.2) but not the a_uniq operations. For a multimap<Key,T> the key_type is Key and the value_type is pair>tuple<const Key,T>. Descriptions are provided here only for operations on multimap that are not described in one of those tables or for operations where there is additional semantic information.

namespace std {
  template <class Key, class T, class Compare = less<Key>,
            class Allocator = allocator<pair>tuple<const Key, T> > >
  class multimap {
  public:
    // types:
    typedef Key key_type;
    typedef T mapped_type;
    typedef pair>tuple<const Key,T> value_type;
    typedef Compare key_compare;
    typedef Allocator allocator_type;
    typedef typename Allocator::reference reference;
    typedef typename Allocator::const_reference const_reference;
    typedef implementation-defined iterator; // See 23.1
    typedef implementation-defined const_iterator; // See 23.1
    typedef implementation-defined size_type; // See 23.1
    typedef implementation-defined difference_type;// See 23.1
    typedef typename Allocator::pointer pointer;
    typedef typename Allocator::const_pointer const_pointer;
    typedef std::reverse_iterator<iterator> reverse_iterator;
    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

    ...

    // map operations:
    iterator find(const key_type& x);
    const_iterator find(const key_type& x) const;
    size_type count(const key_type& x) const;
    iterator lower_bound(const key_type& x);
    const_iterator lower_bound(const key_type& x) const;
    iterator upper_bound(const key_type& x);
    const_iterator upper_bound(const key_type& x) const;

    pair>tuple<iterator,iterator>
equal_range(const key_type& x);
    pair>tuple<const_iterator,const_iterator>
equal_range(const key_type& x) const;
  };
}

23.3.3 Class template set [set]

namespace std {
  template <class Key, class Compare = less<Key>,
            class Allocator = allocator<Key> >
  class set {
  public:

    ....

    // modifiers:
    template <class... Args> pair>tuple<iterator, bool> emplace(Args&&... args);
    template <class... Args> iterator emplace(const_iterator position, Args&&... args);
    pair>tuple<iterator,bool> insert(const value_type& x);
    pair>tuple<iterator,bool> insert(value_type&& x);
    iterator insert(const_iterator position, const value_type& x);
    iterator insert(const_iterator position, value_type&& x);
    template <class InputIterator>
    void insert(InputIterator first, InputIterator last);
    iterator erase(const_iterator position);
    size_type erase(const key_type& x);
    iterator erase(const_iterator first, const_iterator last);
    void swap(set<Key,Compare,Allocator>&);
    void clear();

    // observers:
    key_compare key_comp() const;
    value_compare value_comp() const;

    // set operations:
    iterator find(const key_type& x);
    const_iterator find(const key_type& x) const;
    size_type count(const key_type& x) const;
    iterator lower_bound(const key_type& x);
    const_iterator lower_bound(const key_type& x) const;
    iterator upper_bound(const key_type& x);
    const_iterator upper_bound(const key_type& x) const;
    pair>tuple<iterator,iterator> equal_range(const key_type& x);
    pair>tuple<const_iterator,const_iterator>   equal_range(const key_type& x) const;
  };
}

23.3.4 Class template multiset [multiset]

namespace std {
  template <class Key, class Compare = less<Key>,
            class Allocator = allocator<Key> >
  class multiset {
  public:

    ....

    // set operations:
    iterator find(const key_type& x);
    const_iterator find(const key_type& x) const;
    size_type count(const key_type& x) const;
    iterator lower_bound(const key_type& x);
    const_iterator lower_bound(const key_type& x) const;
    iterator upper_bound(const key_type& x);
    const_iterator upper_bound(const key_type& x) const;
    pair>tuple<iterator,iterator> equal_range(const key_type& x);
    pair>tuple<const_iterator,const_iterator> equal_range(const key_type& x) const;
  };
}

25.1.7 Mismatch [mismatch]

template<class InputIterator1, class InputIterator2>
  pairtuple<InputIterator1, InputIterator2>
    mismatch(InputIterator1 first1, InputIterator1 last1,
             InputIterator2 first2);
             
template<class InputIterator1, class InputIterator2,
class BinaryPredicate>
  pairtuple<InputIterator1, InputIterator2>
    mismatch(InputIterator1 first1, InputIterator1 last1,
             InputIterator2 first2, BinaryPredicate pred);

1 Returns: A pair of iterators i and j such that j == first2 + (i - first1) and i is the first iterator in the range [first1,last1) for which the following corresponding conditions hold:

!(*i == *(first2 + (i - first1)))
pred(*i, *(first2 + (i - first1))) == false

2 Complexity: At most last1 - first1 applications of the corresponding predicate.

25.3.3.3 equal_range [equal.range]

template<class ForwardIterator, class T>
  pairtuple<ForwardIterator, ForwardIterator>
    equal_range(ForwardIterator first,
                ForwardIterator last, const T& value);
                
template<class ForwardIterator, class T, class Compare>
  pairtuple<ForwardIterator, ForwardIterator>
    equal_range(ForwardIterator first,
                ForwardIterator last, const T& value, Compare comp);

1 Requires: The elements e of [first,last) are partitioned with respect to the expressions e < value and !(value < e) or comp(e, value) and !comp(value, e). Also, for all elements e of [first, last), e < value implies !(value < e) or comp(e, value) implies !comp(value, e).

2 Returns:

    make_pairtuple(lower_bound(first, last, value),
               upper_bound(first, last, value))

    make_pairtuple(lower_bound(first, last, value, comp),
               upper_bound(first, last, value, comp))

3 Complexity: At most 2*log2(last − f irst)+O(1) comparisons.

template<class ForwardIterator>
  pairtuple<ForwardIterator, ForwardIterator>
    minmax_element(ForwardIterator first, ForwardIterator last);

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

15 Returns: make_pairtuple(m, M), where m is min_element(first, last) or min_element(first, last, comp) and M is max_element(first, last) or max_element(first, last, comp).

16 Complexity: At most max(2 * (last - first) - 2, 0) applications of the corresponding comparisons.

25.3.7 Minimum and maximum [alg.min.max]

template<class T> pairtuple<const T&, const T&> minmax(const T& a, const T& b);

template<class T, class Compare>
  pairtuple<const T&, const T&> minmax(const T& a, const T& b, Compare comp);

7 Requires: Type T shall be LessThanComparable (32).

8 Returns: pairtuple<const T&, const T&>(b, a) if b is smaller than a, and pairtuple<const T&, const T&>(a, b) otherwise.

9 Remarks: Returns pairtuple<const T&, const T&>(a, b) when the arguments are equivalent.

10 Complexity: Exactly one comparison.

28.9 Class template sub_match [re.submatch]

template <class BidirectionalIterator>
class sub_match : public std::pairtuple<BidirectionalIterator, BidirectionalIterator>
{
public:
  typedef typename iterator_traits<BidirectionalIterator>::
    value_type                       value_type;
  typedef typename iterator_traits<BidirectionalIterator>::
    difference_type                  difference_type;
  typedef BidirectionalIterator      iterator;
  
  bool matched;
  
  difference_type length() const;
  operator basic_string<value_type>() const;
  basic_string<value_type> str() const;
  
  int compare(const sub_match& s) const;
  int compare(const basic_string<value_type>& s) const;
  int compare(const value_type* s) const;
};