Everything under [re.results]

llvm-svn: 111074

23 files changed, 1253 insertions, 12 deletions

diff --git a/libcxx/include/regex b/libcxx/include/regex
index 2e0e8e39486..032b4d0fa09 100644
--- a/libcxx/include/regex
+++ b/libcxx/include/regex
@@ -5222,14 +5222,27 @@ public:
     template <class _OutputIter, class _ST, class _SA>
         _OutputIter
         format(_OutputIter __out, const basic_string<char_type, _ST, _SA>& __fmt,
-               regex_constants::match_flag_type __flags = regex_constants::format_default) const;
+               regex_constants::match_flag_type __flags = regex_constants::format_default) const
+            {return format(__out, __fmt.data(), __fmt.data() + __fmt.size(), __flags);}
     template <class _ST, class _SA>
         basic_string<char_type, _ST, _SA>
         format(const basic_string<char_type, _ST, _SA>& __fmt,
-               regex_constants::match_flag_type __flags = regex_constants::format_default) const;
+               regex_constants::match_flag_type __flags = regex_constants::format_default) const
+        {
+            basic_string<char_type, _ST, _SA> __r;
+            format(back_inserter(__r), __fmt.data(), __fmt.data() + __fmt.size(),
+                   __flags);
+            return __r;
+        }
     string_type
         format(const char_type* __fmt,
-               regex_constants::match_flag_type __flags = regex_constants::format_default) const;
+               regex_constants::match_flag_type __flags = regex_constants::format_default) const
+        {
+            string_type __r;
+            format(back_inserter(__r), __fmt,
+                   __fmt + char_traits<char_type>::length(__fmt), __flags);
+            return __r;
+        }
 
     // allocator:
     allocator_type get_allocator() const {return __matches_.get_allocator();}
@@ -5272,6 +5285,11 @@ private:
     regex_match(_B, _B, match_results<_B, _A>&, const basic_regex<_C, _T>&,
                 regex_constants::match_flag_type);
 
+    template <class _B, class _A>
+    friend
+    bool
+    operator==(const match_results<_B, _A>&, const match_results<_B, _A>&);
+
     template <class, class> friend class __lookahead;
 };
 
@@ -5300,25 +5318,142 @@ match_results<_BidirectionalIterator, _Allocator>::__init(unsigned __s,
     __suffix_ = __unmatched_;
 }
 
+template <class _BidirectionalIterator, class _Allocator>
+template <class _OutputIter>
+_OutputIter
+match_results<_BidirectionalIterator, _Allocator>::format(_OutputIter __out,
+        const char_type* __fmt_first, const char_type* __fmt_last,
+        regex_constants::match_flag_type __flags) const
+{
+    if (__flags & regex_constants::format_sed)
+    {
+        for (; __fmt_first != __fmt_last; ++__fmt_first)
+        {
+            if (*__fmt_first == '&')
+                __out = _STD::copy(__matches_[0].first, __matches_[0].second,
+                                   __out);
+            else if (*__fmt_first == '\\' && __fmt_first + 1 != __fmt_last)
+            {
+                ++__fmt_first;
+                if ('0' <= *__fmt_first && *__fmt_first <= '9')
+                {
+                    size_t __i = *__fmt_first - '0';
+                    __out = _STD::copy(__matches_[__i].first,
+                                       __matches_[__i].second, __out);
+                }
+                else
+                {
+                    *__out = *__fmt_first;
+                    ++__out;
+                }
+            }
+            else
+            {
+                *__out = *__fmt_first;
+                ++__out;
+            }
+        }
+    }
+    else
+    {
+        for (; __fmt_first != __fmt_last; ++__fmt_first)
+        {
+            if (*__fmt_first == '$' && __fmt_first + 1 != __fmt_last)
+            {
+                switch (__fmt_first[1])
+                {
+                case '$':
+                    *__out = *++__fmt_first;
+                    ++__out;
+                    break;
+                case '&':
+                    ++__fmt_first;
+                    __out = _STD::copy(__matches_[0].first, __matches_[0].second,
+                                       __out);
+                    break;
+                case '`':
+                    ++__fmt_first;
+                    __out = _STD::copy(__prefix_.first, __prefix_.second, __out);
+                    break;
+                case '\'':
+                    ++__fmt_first;
+                    __out = _STD::copy(__suffix_.first, __suffix_.second, __out);
+                    break;
+                default:
+                    if ('0' <= __fmt_first[1] && __fmt_first[1] <= '9')
+                    {
+                        ++__fmt_first;
+                        size_t __i = *__fmt_first - '0';
+                        if (__fmt_first + 1 != __fmt_last &&
+                            '0' <= __fmt_first[1] && __fmt_first[1] <= '9')
+                        {
+                            ++__fmt_first;
+                            __i = 10 * __i + *__fmt_first - '0';
+                        }
+                        __out = _STD::copy(__matches_[__i].first,
+                                           __matches_[__i].second, __out);
+                    }
+                    else
+                    {
+                        *__out = *__fmt_first;
+                        ++__out;
+                    }
+                    break;
+                }
+            }
+            else
+            {
+                *__out = *__fmt_first;
+                ++__out;
+            }
+        }
+    }
+    return __out;
+}
+
+template <class _BidirectionalIterator, class _Allocator>
+void
+match_results<_BidirectionalIterator, _Allocator>::swap(match_results& __m)
+{
+    using _STD::swap;
+    swap(__matches_, __m.__matches_);
+    swap(__unmatched_, __m.__unmatched_);
+    swap(__prefix_, __m.__prefix_);
+    swap(__suffix_, __m.__suffix_);
+}
+
 typedef match_results<const char*>             cmatch;
 typedef match_results<const wchar_t*>          wcmatch;
 typedef match_results<string::const_iterator>  smatch;
 typedef match_results<wstring::const_iterator> wsmatch;
 
 template <class _BidirectionalIterator, class _Allocator>
-    bool
-    operator==(const match_results<_BidirectionalIterator, _Allocator>& __x,
-               const match_results<_BidirectionalIterator, _Allocator>& __y);
+bool
+operator==(const match_results<_BidirectionalIterator, _Allocator>& __x,
+           const match_results<_BidirectionalIterator, _Allocator>& __y)
+{
+    return __x.__matches_ == __y.__matches_ &&
+           __x.__prefix_ == __y.__prefix_ &&
+           __x.__suffix_ == __y.__suffix_;
+}
 
 template <class _BidirectionalIterator, class _Allocator>
-    bool
-    operator!=(const match_results<_BidirectionalIterator, _Allocator>& __x,
-               const match_results<_BidirectionalIterator, _Allocator>& __y);
+inline _LIBCPP_INLINE_VISIBILITY
+bool
+operator!=(const match_results<_BidirectionalIterator, _Allocator>& __x,
+           const match_results<_BidirectionalIterator, _Allocator>& __y)
+{
+    return !(__x == __y);
+}
 
 template <class _BidirectionalIterator, class _Allocator>
-    void
-    swap(match_results<_BidirectionalIterator, _Allocator>& __x,
-         match_results<_BidirectionalIterator, _Allocator>& __y);
+inline _LIBCPP_INLINE_VISIBILITY
+void
+swap(match_results<_BidirectionalIterator, _Allocator>& __x,
+     match_results<_BidirectionalIterator, _Allocator>& __y)
+{
+    __x.swap(__y);
+}
 
 // regex_search
 
diff --git a/libcxx/test/re/iterators.h b/libcxx/test/re/iterators.h
index 85332ac725d..8ca5e889ec8 100644
--- a/libcxx/test/re/iterators.h
+++ b/libcxx/test/re/iterators.h
@@ -4,6 +4,32 @@
 #include <iterator>
 
 template <class It>
+class output_iterator
+{
+    It it_;
+
+    template <class U> friend class output_iterator;
+public:
+    typedef          std::output_iterator_tag                  iterator_category;
+    typedef typename std::iterator_traits<It>::value_type      value_type;
+    typedef typename std::iterator_traits<It>::difference_type difference_type;
+    typedef It                                                 pointer;
+    typedef typename std::iterator_traits<It>::reference       reference;
+
+    It base() const {return it_;}
+
+    explicit output_iterator(It it) : it_(it) {}
+    template <class U>
+        output_iterator(const output_iterator<U>& u) :it_(u.it_) {}
+
+    reference operator*() const {return *it_;}
+
+    output_iterator& operator++() {++it_; return *this;}
+    output_iterator operator++(int)
+        {output_iterator tmp(*this); ++(*this); return tmp;}
+};
+
+template <class It>
 class input_iterator
 {
     It it_;
diff --git a/libcxx/test/re/re.results/re.results.acc/begin_end.pass.cpp b/libcxx/test/re/re.results/re.results.acc/begin_end.pass.cpp
new file mode 100644
index 00000000000..ab057cc682d
--- /dev/null
+++ b/libcxx/test/re/re.results/re.results.acc/begin_end.pass.cpp
@@ -0,0 +1,38 @@
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// <regex>
+
+// class match_results<BidirectionalIterator, Allocator>
+
+// const_iterator begin() const;
+// const_iterator end() const;
+
+#include <regex>
+#include <cassert>
+
+void
+test()
+{
+    std::match_results<const char*> m;
+    const char s[] = "abcdefghijk";
+    assert(std::regex_search(s, m, std::regex("cd((e)fg)hi")));
+
+    std::match_results<const char*>::const_iterator i = m.begin();
+    std::match_results<const char*>::const_iterator e = m.end();
+
+    assert(e - i == m.size() - 1);
+    for (int j = 1; i != e; ++i, ++j)
+        assert(*i == m[j]);
+}
+
+int main()
+{
+    test();
+}
diff --git a/libcxx/test/re/re.results/re.results.acc/cbegin_cend.pass.cpp b/libcxx/test/re/re.results/re.results.acc/cbegin_cend.pass.cpp
new file mode 100644
index 00000000000..f66a6847e20
--- /dev/null
+++ b/libcxx/test/re/re.results/re.results.acc/cbegin_cend.pass.cpp
@@ -0,0 +1,38 @@
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// <regex>
+
+// class match_results<BidirectionalIterator, Allocator>
+
+// const_iterator cbegin() const;
+// const_iterator cend() const;
+
+#include <regex>
+#include <cassert>
+
+void
+test()
+{
+    std::match_results<const char*> m;
+    const char s[] = "abcdefghijk";
+    assert(std::regex_search(s, m, std::regex("cd((e)fg)hi")));
+
+    std::match_results<const char*>::const_iterator i = m.cbegin();
+    std::match_results<const char*>::const_iterator e = m.cend();
+
+    assert(e - i == m.size() - 1);
+    for (int j = 1; i != e; ++i, ++j)
+        assert(*i == m[j]);
+}
+
+int main()
+{
+    test();
+}
diff --git a/libcxx/test/re/re.results/re.results.acc/index.pass.cpp b/libcxx/test/re/re.results/re.results.acc/index.pass.cpp
new file mode 100644
index 00000000000..1b8a4316c69
--- /dev/null
+++ b/libcxx/test/re/re.results/re.results.acc/index.pass.cpp
@@ -0,0 +1,50 @@
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// <regex>
+
+// class match_results<BidirectionalIterator, Allocator>
+
+// const_reference operator[](size_type n) const;
+
+#include <regex>
+#include <cassert>
+
+void
+test()
+{
+    std::match_results<const char*> m;
+    const char s[] = "abcdefghijk";
+    assert(std::regex_search(s, m, std::regex("cd((e)fg)hi")));
+
+    assert(m[0].first == s+2);
+    assert(m[0].second == s+9);
+    assert(m[0].matched == true);
+
+    assert(m[1].first == s+4);
+    assert(m[1].second == s+7);
+    assert(m[1].matched == true);
+
+    assert(m[2].first == s+4);
+    assert(m[2].second == s+5);
+    assert(m[2].matched == true);
+
+    assert(m[3].first == s+11);
+    assert(m[3].second == s+11);
+    assert(m[3].matched == false);
+
+    assert(m[4].first == s+11);
+    assert(m[4].second == s+11);
+    assert(m[4].matched == false);
+}
+
+int main()
+{
+    test();
+}
diff --git a/libcxx/test/re/re.results/re.results.acc/length.pass.cpp b/libcxx/test/re/re.results/re.results.acc/length.pass.cpp
new file mode 100644
index 00000000000..72f36f03f4e
--- /dev/null
+++ b/libcxx/test/re/re.results/re.results.acc/length.pass.cpp
@@ -0,0 +1,36 @@
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// <regex>
+
+// class match_results<BidirectionalIterator, Allocator>
+
+// difference_type length(size_type sub = 0) const;
+
+#include <regex>
+#include <cassert>
+
+void
+test()
+{
+    std::match_results<const char*> m;
+    const char s[] = "abcdefghijk";
+    assert(std::regex_search(s, m, std::regex("cd((e)fg)hi")));
+    assert(m.length() == m[0].length());
+    assert(m.length(0) == m[0].length());
+    assert(m.length(1) == m[1].length());
+    assert(m.length(2) == m[2].length());
+    assert(m.length(3) == m[3].length());
+    assert(m.length(4) == m[4].length());
+}
+
+int main()
+{
+    test();
+}
diff --git a/libcxx/test/re/re.results/re.results.acc/position.pass.cpp b/libcxx/test/re/re.results/re.results.acc/position.pass.cpp
new file mode 100644
index 00000000000..abad6830640
--- /dev/null
+++ b/libcxx/test/re/re.results/re.results.acc/position.pass.cpp
@@ -0,0 +1,36 @@
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// <regex>
+
+// class match_results<BidirectionalIterator, Allocator>
+
+// difference_type position(size_type sub = 0) const;
+
+#include <regex>
+#include <cassert>
+
+void
+test()
+{
+    std::match_results<const char*> m;
+    const char s[] = "abcdefghijk";
+    assert(std::regex_search(s, m, std::regex("cd((e)fg)hi")));
+    assert(m.position() == std::distance(s, m[0].first));
+    assert(m.position(0) == std::distance(s, m[0].first));
+    assert(m.position(1) == std::distance(s, m[1].first));
+    assert(m.position(2) == std::distance(s, m[2].first));
+    assert(m.position(3) == std::distance(s, m[3].first));
+    assert(m.position(4) == std::distance(s, m[4].first));
+}
+
+int main()
+{
+    test();
+}
diff --git a/libcxx/test/re/re.results/re.results.acc/prefix.pass.cpp b/libcxx/test/re/re.results/re.results.acc/prefix.pass.cpp
new file mode 100644
index 00000000000..e09028d4825
--- /dev/null
+++ b/libcxx/test/re/re.results/re.results.acc/prefix.pass.cpp
@@ -0,0 +1,34 @@
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// <regex>
+
+// class match_results<BidirectionalIterator, Allocator>
+
+// const_reference prefix() const;
+
+#include <regex>
+#include <cassert>
+
+void
+test()
+{
+    std::match_results<const char*> m;
+    const char s[] = "abcdefghijk";
+    assert(std::regex_search(s, m, std::regex("cd((e)fg)hi")));
+
+    assert(m.prefix().first == s);
+    assert(m.prefix().second == s+2);
+    assert(m.prefix().matched == true);
+}
+
+int main()
+{
+    test();
+}
diff --git a/libcxx/test/re/re.results/re.results.acc/str.pass.cpp b/libcxx/test/re/re.results/re.results.acc/str.pass.cpp
new file mode 100644
index 00000000000..a548c024002
--- /dev/null
+++ b/libcxx/test/re/re.results/re.results.acc/str.pass.cpp
@@ -0,0 +1,36 @@
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// <regex>
+
+// class match_results<BidirectionalIterator, Allocator>
+
+// string_type str(size_type sub = 0) const;
+
+#include <regex>
+#include <cassert>
+
+void
+test()
+{
+    std::match_results<const char*> m;
+    const char s[] = "abcdefghijk";
+    assert(std::regex_search(s, m, std::regex("cd((e)fg)hi")));
+    assert(m.str() == std::string(m[0]));
+    assert(m.str(0) == std::string(m[0]));
+    assert(m.str(1) == std::string(m[1]));
+    assert(m.str(2) == std::string(m[2]));
+    assert(m.str(3) == std::string(m[3]));
+    assert(m.str(4) == std::string(m[4]));
+}
+
+int main()
+{
+    test();
+}
diff --git a/libcxx/test/re/re.results/re.results.acc/suffix.pass.cpp b/libcxx/test/re/re.results/re.results.acc/suffix.pass.cpp
new file mode 100644
index 00000000000..b548d470739
--- /dev/null
+++ b/libcxx/test/re/re.results/re.results.acc/suffix.pass.cpp
@@ -0,0 +1,34 @@
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// <regex>
+
+// class match_results<BidirectionalIterator, Allocator>
+
+// const_reference suffix() const;
+
+#include <regex>
+#include <cassert>
+
+void
+test()
+{
+    std::match_results<const char*> m;
+    const char s[] = "abcdefghijk";
+    assert(std::regex_search(s, m, std::regex("cd((e)fg)hi")));
+
+    assert(m.suffix().first == s+9);
+    assert(m.suffix().second == s+11);
+    assert(m.suffix().matched == true);
+}
+
+int main()
+{
+    test();
+}
diff --git a/libcxx/test/re/re.results/re.results.all/get_allocator.pass.cpp b/libcxx/test/re/re.results/re.results.all/get_allocator.pass.cpp
new file mode 100644
index 00000000000..be559997ff5
--- /dev/null
+++ b/libcxx/test/re/re.results/re.results.all/get_allocator.pass.cpp
@@ -0,0 +1,35 @@
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// <regex>
+
+// class match_results<BidirectionalIterator, Allocator>
+
+// allocator_type get_allocator() const;
+
+#include <regex>
+#include <cassert>
+
+#include "../../test_allocator.h"
+
+template <class CharT, class Allocator>
+void
+test(const Allocator& a)
+{
+    std::match_results<const CharT*, Allocator> m(a);
+    assert(m.size() == 0);
+    assert(m.str() == std::basic_string<CharT>());
+    assert(m.get_allocator() == a);
+}
+
+int main()
+{
+    test<char>(test_allocator<std::sub_match<const char*> >(3));
+    test<wchar_t>(test_allocator<std::sub_match<const wchar_t*> >(3));
+}
diff --git a/libcxx/test/re/re.results/re.results.const/allocator.pass.cpp b/libcxx/test/re/re.results/re.results.const/allocator.pass.cpp
new file mode 100644
index 00000000000..d8b952bffc9
--- /dev/null
+++ b/libcxx/test/re/re.results/re.results.const/allocator.pass.cpp
@@ -0,0 +1,35 @@
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// <regex>
+
+// class match_results<BidirectionalIterator, Allocator>
+
+// match_results(const Allocator& a = Allocator());
+
+#include <regex>
+#include <cassert>
+
+#include "../../test_allocator.h"
+
+template <class CharT, class Allocator>
+void
+test(const Allocator& a)
+{
+    std::match_results<const CharT*, Allocator> m(a);
+    assert(m.size() == 0);
+    assert(m.str() == std::basic_string<CharT>());
+    assert(m.get_allocator() == a);
+}
+
+int main()
+{
+    test<char>(test_allocator<std::sub_match<const char*> >(3));
+    test<wchar_t>(test_allocator<std::sub_match<const wchar_t*> >(3));
+}
diff --git a/libcxx/test/re/re.results/re.results.const/default.pass.cpp b/libcxx/test/re/re.results/re.results.const/default.pass.cpp
new file mode 100644
index 00000000000..1956ee31ed8
--- /dev/null
+++ b/libcxx/test/re/re.results/re.results.const/default.pass.cpp
@@ -0,0 +1,33 @@
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// <regex>
+
+// class match_results<BidirectionalIterator, Allocator>
+
+// match_results(const Allocator& a = Allocator());
+
+#include <regex>
+#include <cassert>
+
+template <class CharT>
+void
+test()
+{
+    std::match_results<const CharT*> m;
+    assert(m.size() == 0);
+    assert(m.str() == std::basic_string<CharT>());
+    assert(m.get_allocator() == std::allocator<std::sub_match<const CharT*> >());
+}
+
+int main()
+{
+    test<char>();
+    test<wchar_t>();
+}
diff --git a/libcxx/test/re/re.results/re.results.form/form1.pass.cpp b/libcxx/test/re/re.results/re.results.form/form1.pass.cpp
new file mode 100644
index 00000000000..c7051b10b43
--- /dev/null
+++ b/libcxx/test/re/re.results/re.results.form/form1.pass.cpp
@@ -0,0 +1,103 @@
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// <regex>
+
+// class match_results<BidirectionalIterator, Allocator>
+
+// template <class OutputIter>
+//   OutputIter
+//   format(OutputIter out, const char_type* fmt_first, const char_type* fmt_last,
+//          regex_constants::match_flag_type flags = regex_constants::format_default) const;
+
+#include <regex>
+#include <cassert>
+
+#include "../../iterators.h"
+
+int main()
+{
+    {
+        std::match_results<const char*> m;
+        const char s[] = "abcdefghijk";
+        assert(std::regex_search(s, m, std::regex("cd((e)fg)hi")));
+
+        char out[100] = {0};
+        const char fmt[] = "prefix: $`, match: $&, suffix: $', m[1]: $1, m[2]: $2";
+        char* r = m.format(output_iterator<char*>(out),
+                    fmt, fmt + std::char_traits<char>::length(fmt)).base();
+        assert(r == out + 58);
+        assert(std::string(out) == "prefix: ab, match: cdefghi, suffix: jk, m[1]: efg, m[2]: e");
+    }
+    {
+        std::match_results<const char*> m;
+        const char s[] = "abcdefghijk";
+        assert(std::regex_search(s, m, std::regex("cd((e)fg)hi")));
+
+        char out[100] = {0};
+        const char fmt[] = "prefix: $`, match: $&, suffix: $', m[1]: $1, m[2]: $2";
+        char* r = m.format(output_iterator<char*>(out),
+                    fmt, fmt + std::char_traits<char>::length(fmt),
+                    std::regex_constants::format_sed).base();
+        assert(r == out + 59);
+        assert(std::string(out) == "prefix: $`, match: $cdefghi, suffix: $', m[1]: $1, m[2]: $2");
+    }
+    {
+        std::match_results<const char*> m;
+        const char s[] = "abcdefghijk";
+        assert(std::regex_search(s, m, std::regex("cd((e)fg)hi")));
+
+        char out[100] = {0};
+        const char fmt[] = "match: &, m[1]: \\1, m[2]: \\2";
+        char* r = m.format(output_iterator<char*>(out),
+                    fmt, fmt + std::char_traits<char>::length(fmt),
+                    std::regex_constants::format_sed).base();
+        assert(r == out + 34);
+        assert(std::string(out) == "match: cdefghi, m[1]: efg, m[2]: e");
+    }
+
+    {
+        std::match_results<const wchar_t*> m;
+        const wchar_t s[] = L"abcdefghijk";
+        assert(std::regex_search(s, m, std::wregex(L"cd((e)fg)hi")));
+
+        wchar_t out[100] = {0};
+        const wchar_t fmt[] = L"prefix: $`, match: $&, suffix: $', m[1]: $1, m[2]: $2";
+        wchar_t* r = m.format(output_iterator<wchar_t*>(out),
+                    fmt, fmt + std::char_traits<wchar_t>::length(fmt)).base();
+        assert(r == out + 58);
+        assert(std::wstring(out) == L"prefix: ab, match: cdefghi, suffix: jk, m[1]: efg, m[2]: e");
+    }
+    {
+        std::match_results<const wchar_t*> m;
+        const wchar_t s[] = L"abcdefghijk";
+        assert(std::regex_search(s, m, std::wregex(L"cd((e)fg)hi")));
+
+        wchar_t out[100] = {0};
+        const wchar_t fmt[] = L"prefix: $`, match: $&, suffix: $', m[1]: $1, m[2]: $2";
+        wchar_t* r = m.format(output_iterator<wchar_t*>(out),
+                    fmt, fmt + std::char_traits<wchar_t>::length(fmt),
+                    std::regex_constants::format_sed).base();
+        assert(r == out + 59);
+        assert(std::wstring(out) == L"prefix: $`, match: $cdefghi, suffix: $', m[1]: $1, m[2]: $2");
+    }
+    {
+        std::match_results<const wchar_t*> m;
+        const wchar_t s[] = L"abcdefghijk";
+        assert(std::regex_search(s, m, std::wregex(L"cd((e)fg)hi")));
+
+        wchar_t out[100] = {0};
+        const wchar_t fmt[] = L"match: &, m[1]: \\1, m[2]: \\2";
+        wchar_t* r = m.format(output_iterator<wchar_t*>(out),
+                    fmt, fmt + std::char_traits<wchar_t>::length(fmt),
+                    std::regex_constants::format_sed).base();
+        assert(r == out + 34);
+        assert(std::wstring(out) == L"match: cdefghi, m[1]: efg, m[2]: e");
+    }
+}
diff --git a/libcxx/test/re/re.results/re.results.form/form2.pass.cpp b/libcxx/test/re/re.results/re.results.form/form2.pass.cpp
new file mode 100644
index 00000000000..b143584a6cd
--- /dev/null
+++ b/libcxx/test/re/re.results/re.results.form/form2.pass.cpp
@@ -0,0 +1,102 @@
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// <regex>
+
+// class match_results<BidirectionalIterator, Allocator>
+
+// template <class OutputIter, class ST, class SA>
+//   OutputIter
+//   format(OutputIter out, const basic_string<char_type, ST, SA>& fmt,
+//          regex_constants::match_flag_type flags = regex_constants::format_default) const;
+
+#include <iostream>
+
+#include <regex>
+#include <cassert>
+
+#include "../../iterators.h"
+#include "../../test_allocator.h"
+
+int main()
+{
+    typedef std::basic_string<char, std::char_traits<char>, test_allocator<char> > nstr;
+    typedef std::basic_string<wchar_t, std::char_traits<wchar_t>, test_allocator<wchar_t> > wstr;
+    {
+        std::match_results<const char*> m;
+        const char s[] = "abcdefghijk";
+        assert(std::regex_search(s, m, std::regex("cd((e)fg)hi")));
+
+        char out[100] = {0};
+        nstr fmt("prefix: $`, match: $&, suffix: $', m[1]: $1, m[2]: $2");
+        char* r = m.format(output_iterator<char*>(out), fmt).base();
+        assert(r == out + 58);
+        assert(std::string(out) == "prefix: ab, match: cdefghi, suffix: jk, m[1]: efg, m[2]: e");
+    }
+    {
+        std::match_results<const char*> m;
+        const char s[] = "abcdefghijk";
+        assert(std::regex_search(s, m, std::regex("cd((e)fg)hi")));
+
+        char out[100] = {0};
+        nstr fmt("prefix: $`, match: $&, suffix: $', m[1]: $1, m[2]: $2");
+        char* r = m.format(output_iterator<char*>(out),
+                    fmt, std::regex_constants::format_sed).base();
+        assert(r == out + 59);
+        assert(std::string(out) == "prefix: $`, match: $cdefghi, suffix: $', m[1]: $1, m[2]: $2");
+    }
+    {
+        std::match_results<const char*> m;
+        const char s[] = "abcdefghijk";
+        assert(std::regex_search(s, m, std::regex("cd((e)fg)hi")));
+
+        char out[100] = {0};
+        nstr fmt("match: &, m[1]: \\1, m[2]: \\2");
+        char* r = m.format(output_iterator<char*>(out),
+                    fmt, std::regex_constants::format_sed).base();
+        assert(r == out + 34);
+        assert(std::string(out) == "match: cdefghi, m[1]: efg, m[2]: e");
+    }
+
+    {
+        std::match_results<const wchar_t*> m;
+        const wchar_t s[] = L"abcdefghijk";
+        assert(std::regex_search(s, m, std::wregex(L"cd((e)fg)hi")));
+
+        wchar_t out[100] = {0};
+        wstr fmt(L"prefix: $`, match: $&, suffix: $', m[1]: $1, m[2]: $2");
+        wchar_t* r = m.format(output_iterator<wchar_t*>(out), fmt).base();
+        assert(r == out + 58);
+        assert(std::wstring(out) == L"prefix: ab, match: cdefghi, suffix: jk, m[1]: efg, m[2]: e");
+    }
+    {
+        std::match_results<const wchar_t*> m;
+        const wchar_t s[] = L"abcdefghijk";
+        assert(std::regex_search(s, m, std::wregex(L"cd((e)fg)hi")));
+
+        wchar_t out[100] = {0};
+        wstr fmt(L"prefix: $`, match: $&, suffix: $', m[1]: $1, m[2]: $2");
+        wchar_t* r = m.format(output_iterator<wchar_t*>(out),
+                    fmt, std::regex_constants::format_sed).base();
+        assert(r == out + 59);
+        assert(std::wstring(out) == L"prefix: $`, match: $cdefghi, suffix: $', m[1]: $1, m[2]: $2");
+    }
+    {
+        std::match_results<const wchar_t*> m;
+        const wchar_t s[] = L"abcdefghijk";
+        assert(std::regex_search(s, m, std::wregex(L"cd((e)fg)hi")));
+
+        wchar_t out[100] = {0};
+        wstr fmt(L"match: &, m[1]: \\1, m[2]: \\2");
+        wchar_t* r = m.format(output_iterator<wchar_t*>(out),
+                    fmt, std::regex_constants::format_sed).base();
+        assert(r == out + 34);
+        assert(std::wstring(out) == L"match: cdefghi, m[1]: efg, m[2]: e");
+    }
+}
diff --git a/libcxx/test/re/re.results/re.results.form/form3.pass.cpp b/libcxx/test/re/re.results/re.results.form/form3.pass.cpp
new file mode 100644
index 00000000000..7f4d7fb9320
--- /dev/null
+++ b/libcxx/test/re/re.results/re.results.form/form3.pass.cpp
@@ -0,0 +1,85 @@
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// <regex>
+
+// class match_results<BidirectionalIterator, Allocator>
+
+// template <class ST, class SA>
+//   basic_string<char_type, ST, SA>
+//   format(const basic_string<char_type, ST, SA>& fmt,
+//          regex_constants::match_flag_type flags = regex_constants::format_default) const;
+
+#include <iostream>
+
+#include <regex>
+#include <cassert>
+
+#include "../../test_allocator.h"
+
+int main()
+{
+    typedef std::basic_string<char, std::char_traits<char>, test_allocator<char> > nstr;
+    typedef std::basic_string<wchar_t, std::char_traits<wchar_t>, test_allocator<wchar_t> > wstr;
+    {
+        std::match_results<const char*> m;
+        const char s[] = "abcdefghijk";
+        assert(std::regex_search(s, m, std::regex("cd((e)fg)hi")));
+
+        nstr fmt("prefix: $`, match: $&, suffix: $', m[1]: $1, m[2]: $2");
+        nstr out = m.format(fmt);
+        assert(out == "prefix: ab, match: cdefghi, suffix: jk, m[1]: efg, m[2]: e");
+    }
+    {
+        std::match_results<const char*> m;
+        const char s[] = "abcdefghijk";
+        assert(std::regex_search(s, m, std::regex("cd((e)fg)hi")));
+
+        nstr fmt("prefix: $`, match: $&, suffix: $', m[1]: $1, m[2]: $2");
+        nstr out = m.format(fmt, std::regex_constants::format_sed);
+        assert(out == "prefix: $`, match: $cdefghi, suffix: $', m[1]: $1, m[2]: $2");
+    }
+    {
+        std::match_results<const char*> m;
+        const char s[] = "abcdefghijk";
+        assert(std::regex_search(s, m, std::regex("cd((e)fg)hi")));
+
+        nstr fmt("match: &, m[1]: \\1, m[2]: \\2");
+        nstr out = m.format(fmt, std::regex_constants::format_sed);
+        assert(out == "match: cdefghi, m[1]: efg, m[2]: e");
+    }
+
+    {
+        std::match_results<const wchar_t*> m;
+        const wchar_t s[] = L"abcdefghijk";
+        assert(std::regex_search(s, m, std::wregex(L"cd((e)fg)hi")));
+
+        wstr fmt(L"prefix: $`, match: $&, suffix: $', m[1]: $1, m[2]: $2");
+        wstr out = m.format(fmt);
+        assert(out == L"prefix: ab, match: cdefghi, suffix: jk, m[1]: efg, m[2]: e");
+    }
+    {
+        std::match_results<const wchar_t*> m;
+        const wchar_t s[] = L"abcdefghijk";
+        assert(std::regex_search(s, m, std::wregex(L"cd((e)fg)hi")));
+
+        wstr fmt(L"prefix: $`, match: $&, suffix: $', m[1]: $1, m[2]: $2");
+        wstr out = m.format(fmt, std::regex_constants::format_sed);
+        assert(out == L"prefix: $`, match: $cdefghi, suffix: $', m[1]: $1, m[2]: $2");
+    }
+    {
+        std::match_results<const wchar_t*> m;
+        const wchar_t s[] = L"abcdefghijk";
+        assert(std::regex_search(s, m, std::wregex(L"cd((e)fg)hi")));
+
+        wstr fmt(L"match: &, m[1]: \\1, m[2]: \\2");
+        wstr out = m.format(fmt, std::regex_constants::format_sed);
+        assert(out == L"match: cdefghi, m[1]: efg, m[2]: e");
+    }
+}
diff --git a/libcxx/test/re/re.results/re.results.form/form4.pass.cpp b/libcxx/test/re/re.results/re.results.form/form4.pass.cpp
new file mode 100644
index 00000000000..1068c298657
--- /dev/null
+++ b/libcxx/test/re/re.results/re.results.form/form4.pass.cpp
@@ -0,0 +1,80 @@
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// <regex>
+
+// class match_results<BidirectionalIterator, Allocator>
+
+// string_type
+//   format(const char_type* fmt,
+//          regex_constants::match_flag_type flags = regex_constants::format_default) const;
+
+#include <iostream>
+
+#include <regex>
+#include <cassert>
+
+int main()
+{
+    {
+        std::match_results<const char*> m;
+        const char s[] = "abcdefghijk";
+        assert(std::regex_search(s, m, std::regex("cd((e)fg)hi")));
+
+        const char fmt[] = "prefix: $`, match: $&, suffix: $', m[1]: $1, m[2]: $2";
+        std::string out = m.format(fmt);
+        assert(out == "prefix: ab, match: cdefghi, suffix: jk, m[1]: efg, m[2]: e");
+    }
+    {
+        std::match_results<const char*> m;
+        const char s[] = "abcdefghijk";
+        assert(std::regex_search(s, m, std::regex("cd((e)fg)hi")));
+
+        const char fmt[] = "prefix: $`, match: $&, suffix: $', m[1]: $1, m[2]: $2";
+        std::string out = m.format(fmt, std::regex_constants::format_sed);
+        assert(out == "prefix: $`, match: $cdefghi, suffix: $', m[1]: $1, m[2]: $2");
+    }
+    {
+        std::match_results<const char*> m;
+        const char s[] = "abcdefghijk";
+        assert(std::regex_search(s, m, std::regex("cd((e)fg)hi")));
+
+        const char fmt[] = "match: &, m[1]: \\1, m[2]: \\2";
+        std::string out = m.format(fmt, std::regex_constants::format_sed);
+        assert(out == "match: cdefghi, m[1]: efg, m[2]: e");
+    }
+
+    {
+        std::match_results<const wchar_t*> m;
+        const wchar_t s[] = L"abcdefghijk";
+        assert(std::regex_search(s, m, std::wregex(L"cd((e)fg)hi")));
+
+        const wchar_t fmt[] = L"prefix: $`, match: $&, suffix: $', m[1]: $1, m[2]: $2";
+        std::wstring out = m.format(fmt);
+        assert(out == L"prefix: ab, match: cdefghi, suffix: jk, m[1]: efg, m[2]: e");
+    }
+    {
+        std::match_results<const wchar_t*> m;
+        const wchar_t s[] = L"abcdefghijk";
+        assert(std::regex_search(s, m, std::wregex(L"cd((e)fg)hi")));
+
+        const wchar_t fmt[] = L"prefix: $`, match: $&, suffix: $', m[1]: $1, m[2]: $2";
+        std::wstring out = m.format(fmt, std::regex_constants::format_sed);
+        assert(out == L"prefix: $`, match: $cdefghi, suffix: $', m[1]: $1, m[2]: $2");
+    }
+    {
+        std::match_results<const wchar_t*> m;
+        const wchar_t s[] = L"abcdefghijk";
+        assert(std::regex_search(s, m, std::wregex(L"cd((e)fg)hi")));
+
+        const wchar_t fmt[] = L"match: &, m[1]: \\1, m[2]: \\2";
+        std::wstring out = m.format(fmt, std::regex_constants::format_sed);
+        assert(out == L"match: cdefghi, m[1]: efg, m[2]: e");
+    }
+}
diff --git a/libcxx/test/re/re.results/re.results.nonmember/equal.pass.cpp b/libcxx/test/re/re.results/re.results.nonmember/equal.pass.cpp
new file mode 100644
index 00000000000..e3ae678022e
--- /dev/null
+++ b/libcxx/test/re/re.results/re.results.nonmember/equal.pass.cpp
@@ -0,0 +1,46 @@
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// <regex>
+
+// class match_results<BidirectionalIterator, Allocator>
+
+// template <class BidirectionalIterator, class Allocator>
+//    bool
+//    operator==(const match_results<BidirectionalIterator, Allocator>& m1,
+//               const match_results<BidirectionalIterator, Allocator>& m2);
+
+// template <class BidirectionalIterator, class Allocator>
+//    bool
+//    operator!=(const match_results<BidirectionalIterator, Allocator>& m1,
+//               const match_results<BidirectionalIterator, Allocator>& m2);
+
+#include <regex>
+#include <cassert>
+
+void
+test()
+{
+    std::match_results<const char*> m1;
+    const char s[] = "abcdefghijk";
+    assert(std::regex_search(s, m1, std::regex("cd((e)fg)hi")));
+    std::match_results<const char*> m2;
+
+    assert(m1 == m1);
+    assert(m1 != m2);
+
+    m2 = m1;
+
+    assert(m1 == m2);
+}
+
+int main()
+{
+    test();
+}
diff --git a/libcxx/test/re/re.results/re.results.size/empty.pass.cpp b/libcxx/test/re/re.results/re.results.size/empty.pass.cpp
new file mode 100644
index 00000000000..4064095ef61
--- /dev/null
+++ b/libcxx/test/re/re.results/re.results.size/empty.pass.cpp
@@ -0,0 +1,36 @@
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// <regex>
+
+// class match_results<BidirectionalIterator, Allocator>
+
+// size_type size() const;
+// bool empty() const;
+
+#include <regex>
+#include <cassert>
+
+template <class CharT>
+void
+test()
+{
+    std::match_results<const CharT*> m;
+    assert(m.empty());
+    assert(m.size() == 0);
+    const char s[] = "abcdefghijk";
+    assert(std::regex_search(s, m, std::regex("cd((e)fg)hi")));
+    assert(!m.empty());
+    assert(m.size() == 3);
+}
+
+int main()
+{
+    test<char>();
+}
diff --git a/libcxx/test/re/re.results/re.results.size/max_size.pass.cpp b/libcxx/test/re/re.results/re.results.size/max_size.pass.cpp
new file mode 100644
index 00000000000..7b9c4300ff6
--- /dev/null
+++ b/libcxx/test/re/re.results/re.results.size/max_size.pass.cpp
@@ -0,0 +1,31 @@
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// <regex>
+
+// class match_results<BidirectionalIterator, Allocator>
+
+// size_type max_size() const;
+
+#include <regex>
+#include <cassert>
+
+template <class CharT>
+void
+test()
+{
+    std::match_results<const CharT*> m;
+    assert(m.max_size() > 0);
+}
+
+int main()
+{
+    test<char>();
+    test<wchar_t>();
+}
diff --git a/libcxx/test/re/re.results/re.results.swap/member_swap.pass.cpp b/libcxx/test/re/re.results/re.results.swap/member_swap.pass.cpp
new file mode 100644
index 00000000000..63fd19db0e8
--- /dev/null
+++ b/libcxx/test/re/re.results/re.results.swap/member_swap.pass.cpp
@@ -0,0 +1,39 @@
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// <regex>
+
+// class match_results<BidirectionalIterator, Allocator>
+
+// void swap(match_results& that);
+
+#include <regex>
+#include <cassert>
+
+void
+test()
+{
+    std::match_results<const char*> m1;
+    const char s[] = "abcdefghijk";
+    assert(std::regex_search(s, m1, std::regex("cd((e)fg)hi")));
+    std::match_results<const char*> m2;
+
+    std::match_results<const char*> m1_save = m1;
+    std::match_results<const char*> m2_save = m2;
+
+    m1.swap(m2);
+
+    assert(m1 == m2_save);
+    assert(m2 == m1_save);
+}
+
+int main()
+{
+    test();
+}
diff --git a/libcxx/test/re/re.results/re.results.swap/non_member_swap.pass.cpp b/libcxx/test/re/re.results/re.results.swap/non_member_swap.pass.cpp
new file mode 100644
index 00000000000..607f41154ac
--- /dev/null
+++ b/libcxx/test/re/re.results/re.results.swap/non_member_swap.pass.cpp
@@ -0,0 +1,41 @@
+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// <regex>
+
+// class match_results<BidirectionalIterator, Allocator>
+
+// template <class BidirectionalIterator, class Allocator>
+//    void swap(match_results<BidirectionalIterator, Allocator>& m1,
+//              match_results<BidirectionalIterator, Allocator>& m2);
+
+#include <regex>
+#include <cassert>
+
+void
+test()
+{
+    std::match_results<const char*> m1;
+    const char s[] = "abcdefghijk";
+    assert(std::regex_search(s, m1, std::regex("cd((e)fg)hi")));
+    std::match_results<const char*> m2;
+
+    std::match_results<const char*> m1_save = m1;
+    std::match_results<const char*> m2_save = m2;
+
+    swap(m1, m2);
+
+    assert(m1 == m2_save);
+    assert(m2 == m1_save);
+}
+
+int main()
+{
+    test();
+}
diff --git a/libcxx/test/re/test_allocator.h b/libcxx/test/re/test_allocator.h
new file mode 100644
index 00000000000..898c0900d4e
--- /dev/null
+++ b/libcxx/test/re/test_allocator.h
@@ -0,0 +1,112 @@
+#ifndef TEST_ALLOCATOR_H
+#define TEST_ALLOCATOR_H
+
+#include <cstddef>
+#include <type_traits>
+#include <cstdlib>
+#include <new>
+#include <climits>
+
+class test_alloc_base
+{
+protected:
+    static int count;
+public:
+    static int throw_after;
+};
+
+int test_alloc_base::count = 0;
+int test_alloc_base::throw_after = INT_MAX;
+
+template <class T>
+class test_allocator
+    : public test_alloc_base
+{
+    int data_;
+
+    template <class U> friend class test_allocator;
+public:
+
+    typedef unsigned                                                   size_type;
+    typedef int                                                        difference_type;
+    typedef T                                                          value_type;
+    typedef value_type*                                                pointer;
+    typedef const value_type*                                          const_pointer;
+    typedef typename std::add_lvalue_reference<value_type>::type       reference;
+    typedef typename std::add_lvalue_reference<const value_type>::type const_reference;
+
+    template <class U> struct rebind {typedef test_allocator<U> other;};
+
+    test_allocator() throw() : data_(-1) {}
+    explicit test_allocator(int i) throw() : data_(i) {}
+    test_allocator(const test_allocator& a) throw()
+        : data_(a.data_) {}
+    template <class U> test_allocator(const test_allocator<U>& a) throw()
+        : data_(a.data_) {}
+    ~test_allocator() throw() {data_ = 0;}
+    pointer address(reference x) const {return &x;}
+    const_pointer address(const_reference x) const {return &x;}
+    pointer allocate(size_type n, const void* = 0)
+        {
+            if (count >= throw_after)
+                throw std::bad_alloc();
+            ++count;
+            return (pointer)std::malloc(n * sizeof(T));
+        }
+    void deallocate(pointer p, size_type n)
+        {std::free(p);}
+    size_type max_size() const throw()
+        {return UINT_MAX / sizeof(T);}
+    void construct(pointer p, const T& val)
+        {::new(p) T(val);}
+#ifdef _LIBCPP_MOVE
+    void construct(pointer p, T&& val)
+        {::new(p) T(std::move(val));}
+#endif
+    void destroy(pointer p) {p->~T();}
+
+    friend bool operator==(const test_allocator& x, const test_allocator& y)
+        {return x.data_ == y.data_;}
+    friend bool operator!=(const test_allocator& x, const test_allocator& y)
+        {return !(x == y);}
+};
+
+template <class T>
+class other_allocator
+{
+    int data_;
+
+    template <class U> friend class other_allocator;
+
+public:
+    typedef T value_type;
+
+    other_allocator() : data_(-1) {}
+    explicit other_allocator(int i) : data_(i) {}
+    template <class U> other_allocator(const other_allocator<U>& a)
+        : data_(a.data_) {}
+    T* allocate(std::size_t n)
+        {return (T*)std::malloc(n * sizeof(T));}
+    void deallocate(T* p, std::size_t n)
+        {std::free(p);}
+
+    other_allocator select_on_container_copy_construction() const
+        {return other_allocator(-2);}
+
+    friend bool operator==(const other_allocator& x, const other_allocator& y)
+        {return x.data_ == y.data_;}
+    friend bool operator!=(const other_allocator& x, const other_allocator& y)
+        {return !(x == y);}
+
+    typedef std::true_type propagate_on_container_copy_assignment;
+    typedef std::true_type propagate_on_container_move_assignment;
+    typedef std::true_type propagate_on_container_swap;
+
+#ifdef _LIBCPP_HAS_NO_ADVANCED_SFINAE
+    std::size_t max_size() const
+        {return UINT_MAX / sizeof(T);}
+#endif
+
+};
+
+#endif