blob: 91d6d30dc938eb3525793920374a7b815abbebde [file] [log] [blame]
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001// -*- C++ -*-
2//===--------------------------- string -----------------------------------===//
3//
Howard Hinnantf5256e12010-05-11 21:36:01 +00004// The LLVM Compiler Infrastructure
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00005//
6// This file is distributed under the University of Illinois Open Source
7// License. See LICENSE.TXT for details.
8//
9//===----------------------------------------------------------------------===//
10
11#ifndef _LIBCPP_STRING
12#define _LIBCPP_STRING
13
14/*
15 string synopsis
16
17namespace std
18{
19
20template <class stateT>
21class fpos
22{
23private:
24 stateT st;
25public:
26 fpos(streamoff = streamoff());
27
28 operator streamoff() const;
29
30 stateT state() const;
31 void state(stateT);
32
33 fpos& operator+=(streamoff);
34 fpos operator+ (streamoff) const;
35 fpos& operator-=(streamoff);
36 fpos operator- (streamoff) const;
37};
38
39template <class stateT> streamoff operator-(const fpos<stateT>& x, const fpos<stateT>& y);
40
41template <class stateT> bool operator==(const fpos<stateT>& x, const fpos<stateT>& y);
42template <class stateT> bool operator!=(const fpos<stateT>& x, const fpos<stateT>& y);
43
44template <class charT>
45struct char_traits
46{
47 typedef charT char_type;
48 typedef ... int_type;
49 typedef streamoff off_type;
50 typedef streampos pos_type;
51 typedef mbstate_t state_type;
52
Howard Hinnanta6119a82011-05-29 19:57:12 +000053 static void assign(char_type& c1, const char_type& c2) noexcept;
54 static bool eq(char_type c1, char_type c2) noexcept;
55 static bool lt(char_type c1, char_type c2) noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000056
57 static int compare(const char_type* s1, const char_type* s2, size_t n);
58 static size_t length(const char_type* s);
59 static const char_type* find(const char_type* s, size_t n, const char_type& a);
60 static char_type* move(char_type* s1, const char_type* s2, size_t n);
61 static char_type* copy(char_type* s1, const char_type* s2, size_t n);
62 static char_type* assign(char_type* s, size_t n, char_type a);
63
Howard Hinnanta6119a82011-05-29 19:57:12 +000064 static int_type not_eof(int_type c) noexcept;
65 static char_type to_char_type(int_type c) noexcept;
66 static int_type to_int_type(char_type c) noexcept;
67 static bool eq_int_type(int_type c1, int_type c2) noexcept;
68 static int_type eof() noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000069};
70
71template <> struct char_traits<char>;
72template <> struct char_traits<wchar_t>;
73
Howard Hinnant324bb032010-08-22 00:02:43 +000074template<class charT, class traits = char_traits<charT>, class Allocator = allocator<charT> >
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000075class basic_string
76{
Howard Hinnant324bb032010-08-22 00:02:43 +000077public:
78// types:
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000079 typedef traits traits_type;
80 typedef typename traits_type::char_type value_type;
81 typedef Allocator allocator_type;
82 typedef typename allocator_type::size_type size_type;
83 typedef typename allocator_type::difference_type difference_type;
84 typedef typename allocator_type::reference reference;
85 typedef typename allocator_type::const_reference const_reference;
86 typedef typename allocator_type::pointer pointer;
87 typedef typename allocator_type::const_pointer const_pointer;
88 typedef implementation-defined iterator;
89 typedef implementation-defined const_iterator;
90 typedef std::reverse_iterator<iterator> reverse_iterator;
91 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
92
93 static const size_type npos = -1;
94
Howard Hinnant53f7d4c2011-06-03 18:40:47 +000095 basic_string()
96 noexcept(is_nothrow_default_constructible<allocator_type>::value);
97 explicit basic_string(const allocator_type& a);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +000098 basic_string(const basic_string& str);
Howard Hinnant53f7d4c2011-06-03 18:40:47 +000099 basic_string(basic_string&& str)
100 noexcept(is_nothrow_move_constructible<allocator_type>::value);
Howard Hinnanta6a062d2010-06-02 18:20:39 +0000101 basic_string(const basic_string& str, size_type pos, size_type n = npos,
102 const allocator_type& a = allocator_type());
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000103 basic_string(const_pointer s, const allocator_type& a = allocator_type());
104 basic_string(const_pointer s, size_type n, const allocator_type& a = allocator_type());
105 basic_string(size_type n, value_type c, const allocator_type& a = allocator_type());
106 template<class InputIterator>
Howard Hinnanta6a062d2010-06-02 18:20:39 +0000107 basic_string(InputIterator begin, InputIterator end,
108 const allocator_type& a = allocator_type());
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000109 basic_string(initializer_list<value_type>, const Allocator& = Allocator());
110 basic_string(const basic_string&, const Allocator&);
111 basic_string(basic_string&&, const Allocator&);
112
113 ~basic_string();
114
115 basic_string& operator=(const basic_string& str);
Howard Hinnant53f7d4c2011-06-03 18:40:47 +0000116 basic_string& operator=(basic_string&& str)
117 noexcept(
118 allocator_type::propagate_on_container_move_assignment::value &&
119 is_nothrow_move_assignable<allocator_type>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000120 basic_string& operator=(const_pointer s);
121 basic_string& operator=(value_type c);
122 basic_string& operator=(initializer_list<value_type>);
123
Howard Hinnanta6119a82011-05-29 19:57:12 +0000124 iterator begin() noexcept;
125 const_iterator begin() const noexcept;
126 iterator end() noexcept;
127 const_iterator end() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000128
Howard Hinnanta6119a82011-05-29 19:57:12 +0000129 reverse_iterator rbegin() noexcept;
130 const_reverse_iterator rbegin() const noexcept;
131 reverse_iterator rend() noexcept;
132 const_reverse_iterator rend() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000133
Howard Hinnanta6119a82011-05-29 19:57:12 +0000134 const_iterator cbegin() const noexcept;
135 const_iterator cend() const noexcept;
136 const_reverse_iterator crbegin() const noexcept;
137 const_reverse_iterator crend() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000138
Howard Hinnanta6119a82011-05-29 19:57:12 +0000139 size_type size() const noexcept;
140 size_type length() const noexcept;
141 size_type max_size() const noexcept;
142 size_type capacity() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000143
144 void resize(size_type n, value_type c);
145 void resize(size_type n);
146
147 void reserve(size_type res_arg = 0);
148 void shrink_to_fit();
Howard Hinnanta6119a82011-05-29 19:57:12 +0000149 void clear() noexcept;
150 bool empty() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000151
152 const_reference operator[](size_type pos) const;
153 reference operator[](size_type pos);
154
155 const_reference at(size_type n) const;
156 reference at(size_type n);
157
158 basic_string& operator+=(const basic_string& str);
159 basic_string& operator+=(const_pointer s);
160 basic_string& operator+=(value_type c);
161 basic_string& operator+=(initializer_list<value_type>);
162
163 basic_string& append(const basic_string& str);
164 basic_string& append(const basic_string& str, size_type pos, size_type n);
165 basic_string& append(const_pointer s, size_type n);
166 basic_string& append(const_pointer s);
167 basic_string& append(size_type n, value_type c);
Howard Hinnanta6a062d2010-06-02 18:20:39 +0000168 template<class InputIterator>
169 basic_string& append(InputIterator first, InputIterator last);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000170 basic_string& append(initializer_list<value_type>);
171
172 void push_back(value_type c);
173 void pop_back();
174 reference front();
175 const_reference front() const;
176 reference back();
177 const_reference back() const;
178
179 basic_string& assign(const basic_string& str);
Howard Hinnanta6119a82011-05-29 19:57:12 +0000180 basic_string& assign(basic_string&& str);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000181 basic_string& assign(const basic_string& str, size_type pos, size_type n);
182 basic_string& assign(const_pointer s, size_type n);
183 basic_string& assign(const_pointer s);
184 basic_string& assign(size_type n, value_type c);
Howard Hinnanta6a062d2010-06-02 18:20:39 +0000185 template<class InputIterator>
186 basic_string& assign(InputIterator first, InputIterator last);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000187 basic_string& assign(initializer_list<value_type>);
188
189 basic_string& insert(size_type pos1, const basic_string& str);
Howard Hinnanta6a062d2010-06-02 18:20:39 +0000190 basic_string& insert(size_type pos1, const basic_string& str,
191 size_type pos2, size_type n);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000192 basic_string& insert(size_type pos, const_pointer s, size_type n);
193 basic_string& insert(size_type pos, const_pointer s);
194 basic_string& insert(size_type pos, size_type n, value_type c);
195 iterator insert(const_iterator p, value_type c);
196 iterator insert(const_iterator p, size_type n, value_type c);
Howard Hinnanta6a062d2010-06-02 18:20:39 +0000197 template<class InputIterator>
198 iterator insert(const_iterator p, InputIterator first, InputIterator last);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000199 iterator insert(const_iterator p, initializer_list<value_type>);
200
201 basic_string& erase(size_type pos = 0, size_type n = npos);
202 iterator erase(const_iterator position);
203 iterator erase(const_iterator first, const_iterator last);
204
205 basic_string& replace(size_type pos1, size_type n1, const basic_string& str);
Howard Hinnanta6a062d2010-06-02 18:20:39 +0000206 basic_string& replace(size_type pos1, size_type n1, const basic_string& str,
207 size_type pos2, size_type n2);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000208 basic_string& replace(size_type pos, size_type n1, const_pointer s, size_type n2);
209 basic_string& replace(size_type pos, size_type n1, const_pointer s);
210 basic_string& replace(size_type pos, size_type n1, size_type n2, value_type c);
Howard Hinnant7b2cb482010-11-17 21:11:40 +0000211 basic_string& replace(const_iterator i1, const_iterator i2, const basic_string& str);
212 basic_string& replace(const_iterator i1, const_iterator i2, const_pointer s, size_type n);
213 basic_string& replace(const_iterator i1, const_iterator i2, const_pointer s);
214 basic_string& replace(const_iterator i1, const_iterator i2, size_type n, value_type c);
Howard Hinnanta6a062d2010-06-02 18:20:39 +0000215 template<class InputIterator>
Howard Hinnant7b2cb482010-11-17 21:11:40 +0000216 basic_string& replace(const_iterator i1, const_iterator i2, InputIterator j1, InputIterator j2);
217 basic_string& replace(const_iterator i1, const_iterator i2, initializer_list<value_type>);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000218
219 size_type copy(pointer s, size_type n, size_type pos = 0) const;
220 basic_string substr(size_type pos = 0, size_type n = npos) const;
221
Howard Hinnant53f7d4c2011-06-03 18:40:47 +0000222 void swap(basic_string& str)
223 noexcept(!allocator_type::propagate_on_container_swap::value ||
224 __is_nothrow_swappable<allocator_type>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000225
Howard Hinnanta6119a82011-05-29 19:57:12 +0000226 const_pointer c_str() const noexcept;
227 const_pointer data() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000228
Howard Hinnanta6119a82011-05-29 19:57:12 +0000229 allocator_type get_allocator() const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000230
Howard Hinnanta6119a82011-05-29 19:57:12 +0000231 size_type find(const basic_string& str, size_type pos = 0) const noexcept;
232 size_type find(const_pointer s, size_type pos, size_type n) const noexcept;
233 size_type find(const_pointer s, size_type pos = 0) const noexcept;
234 size_type find(value_type c, size_type pos = 0) const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000235
Howard Hinnanta6119a82011-05-29 19:57:12 +0000236 size_type rfind(const basic_string& str, size_type pos = npos) const noexcept;
237 size_type rfind(const_pointer s, size_type pos, size_type n) const noexcept;
238 size_type rfind(const_pointer s, size_type pos = npos) const noexcept;
239 size_type rfind(value_type c, size_type pos = npos) const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000240
Howard Hinnanta6119a82011-05-29 19:57:12 +0000241 size_type find_first_of(const basic_string& str, size_type pos = 0) const noexcept;
242 size_type find_first_of(const_pointer s, size_type pos, size_type n) const noexcept;
243 size_type find_first_of(const_pointer s, size_type pos = 0) const noexcept;
244 size_type find_first_of(value_type c, size_type pos = 0) const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000245
Howard Hinnanta6119a82011-05-29 19:57:12 +0000246 size_type find_last_of(const basic_string& str, size_type pos = npos) const noexcept;
247 size_type find_last_of(const_pointer s, size_type pos, size_type n) const noexcept;
248 size_type find_last_of(const_pointer s, size_type pos = npos) const noexcept;
249 size_type find_last_of(value_type c, size_type pos = npos) const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000250
Howard Hinnanta6119a82011-05-29 19:57:12 +0000251 size_type find_first_not_of(const basic_string& str, size_type pos = 0) const noexcept;
252 size_type find_first_not_of(const_pointer s, size_type pos, size_type n) const noexcept;
253 size_type find_first_not_of(const_pointer s, size_type pos = 0) const noexcept;
254 size_type find_first_not_of(value_type c, size_type pos = 0) const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000255
Howard Hinnanta6119a82011-05-29 19:57:12 +0000256 size_type find_last_not_of(const basic_string& str, size_type pos = npos) const noexcept;
257 size_type find_last_not_of(const_pointer s, size_type pos, size_type n) const noexcept;
258 size_type find_last_not_of(const_pointer s, size_type pos = npos) const noexcept;
259 size_type find_last_not_of(value_type c, size_type pos = npos) const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000260
Howard Hinnanta6119a82011-05-29 19:57:12 +0000261 int compare(const basic_string& str) const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000262 int compare(size_type pos1, size_type n1, const basic_string& str) const;
Howard Hinnanta6a062d2010-06-02 18:20:39 +0000263 int compare(size_type pos1, size_type n1, const basic_string& str,
264 size_type pos2, size_type n2) const;
Howard Hinnanta6119a82011-05-29 19:57:12 +0000265 int compare(const_pointer s) const noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000266 int compare(size_type pos1, size_type n1, const_pointer s) const;
267 int compare(size_type pos1, size_type n1, const_pointer s, size_type n2) const;
268
269 bool __invariants() const;
270};
271
272template<class charT, class traits, class Allocator>
273basic_string<charT, traits, Allocator>
Howard Hinnanta6a062d2010-06-02 18:20:39 +0000274operator+(const basic_string<charT, traits, Allocator>& lhs,
275 const basic_string<charT, traits, Allocator>& rhs);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000276
277template<class charT, class traits, class Allocator>
278basic_string<charT, traits, Allocator>
279operator+(const charT* lhs , const basic_string<charT,traits,Allocator>&rhs);
280
281template<class charT, class traits, class Allocator>
282basic_string<charT, traits, Allocator>
283operator+(charT lhs, const basic_string<charT,traits,Allocator>& rhs);
284
285template<class charT, class traits, class Allocator>
286basic_string<charT, traits, Allocator>
287operator+(const basic_string<charT, traits, Allocator>& lhs, const charT* rhs);
288
289template<class charT, class traits, class Allocator>
290basic_string<charT, traits, Allocator>
291operator+(const basic_string<charT, traits, Allocator>& lhs, charT rhs);
292
293template<class charT, class traits, class Allocator>
Howard Hinnanta6a062d2010-06-02 18:20:39 +0000294bool operator==(const basic_string<charT, traits, Allocator>& lhs,
Howard Hinnanta6119a82011-05-29 19:57:12 +0000295 const basic_string<charT, traits, Allocator>& rhs) noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000296
297template<class charT, class traits, class Allocator>
Howard Hinnanta6119a82011-05-29 19:57:12 +0000298bool operator==(const charT* lhs, const basic_string<charT, traits, Allocator>& rhs) noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000299
300template<class charT, class traits, class Allocator>
Howard Hinnanta6119a82011-05-29 19:57:12 +0000301bool operator==(const basic_string<charT,traits,Allocator>& lhs, const charT* rhs) noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000302
Howard Hinnant324bb032010-08-22 00:02:43 +0000303template<class charT, class traits, class Allocator>
Howard Hinnanta6a062d2010-06-02 18:20:39 +0000304bool operator!=(const basic_string<charT,traits,Allocator>& lhs,
Howard Hinnanta6119a82011-05-29 19:57:12 +0000305 const basic_string<charT, traits, Allocator>& rhs) noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000306
307template<class charT, class traits, class Allocator>
Howard Hinnanta6119a82011-05-29 19:57:12 +0000308bool operator!=(const charT* lhs, const basic_string<charT, traits, Allocator>& rhs) noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000309
310template<class charT, class traits, class Allocator>
Howard Hinnanta6119a82011-05-29 19:57:12 +0000311bool operator!=(const basic_string<charT, traits, Allocator>& lhs, const charT* rhs) noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000312
313template<class charT, class traits, class Allocator>
Howard Hinnanta6a062d2010-06-02 18:20:39 +0000314bool operator< (const basic_string<charT, traits, Allocator>& lhs,
Howard Hinnanta6119a82011-05-29 19:57:12 +0000315 const basic_string<charT, traits, Allocator>& rhs) noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000316
317template<class charT, class traits, class Allocator>
Howard Hinnanta6119a82011-05-29 19:57:12 +0000318bool operator< (const basic_string<charT, traits, Allocator>& lhs, const charT* rhs) noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000319
320template<class charT, class traits, class Allocator>
Howard Hinnanta6119a82011-05-29 19:57:12 +0000321bool operator< (const charT* lhs, const basic_string<charT, traits, Allocator>& rhs) noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000322
323template<class charT, class traits, class Allocator>
Howard Hinnanta6a062d2010-06-02 18:20:39 +0000324bool operator> (const basic_string<charT, traits, Allocator>& lhs,
Howard Hinnanta6119a82011-05-29 19:57:12 +0000325 const basic_string<charT, traits, Allocator>& rhs) noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000326
327template<class charT, class traits, class Allocator>
Howard Hinnanta6119a82011-05-29 19:57:12 +0000328bool operator> (const basic_string<charT, traits, Allocator>& lhs, const charT* rhs) noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000329
330template<class charT, class traits, class Allocator>
Howard Hinnanta6119a82011-05-29 19:57:12 +0000331bool operator> (const charT* lhs, const basic_string<charT, traits, Allocator>& rhs) noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000332
333template<class charT, class traits, class Allocator>
Howard Hinnanta6a062d2010-06-02 18:20:39 +0000334bool operator<=(const basic_string<charT, traits, Allocator>& lhs,
Howard Hinnanta6119a82011-05-29 19:57:12 +0000335 const basic_string<charT, traits, Allocator>& rhs) noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000336
337template<class charT, class traits, class Allocator>
Howard Hinnanta6119a82011-05-29 19:57:12 +0000338bool operator<=(const basic_string<charT, traits, Allocator>& lhs, const charT* rhs) noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000339
340template<class charT, class traits, class Allocator>
Howard Hinnanta6119a82011-05-29 19:57:12 +0000341bool operator<=(const charT* lhs, const basic_string<charT, traits, Allocator>& rhs) noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000342
343template<class charT, class traits, class Allocator>
Howard Hinnanta6a062d2010-06-02 18:20:39 +0000344bool operator>=(const basic_string<charT, traits, Allocator>& lhs,
Howard Hinnanta6119a82011-05-29 19:57:12 +0000345 const basic_string<charT, traits, Allocator>& rhs) noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000346
347template<class charT, class traits, class Allocator>
Howard Hinnanta6119a82011-05-29 19:57:12 +0000348bool operator>=(const basic_string<charT, traits, Allocator>& lhs, const charT* rhs) noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000349
350template<class charT, class traits, class Allocator>
Howard Hinnanta6119a82011-05-29 19:57:12 +0000351bool operator>=(const charT* lhs, const basic_string<charT, traits, Allocator>& rhs) noexcept;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000352
353template<class charT, class traits, class Allocator>
Howard Hinnanta6a062d2010-06-02 18:20:39 +0000354void swap(basic_string<charT, traits, Allocator>& lhs,
Howard Hinnant53f7d4c2011-06-03 18:40:47 +0000355 basic_string<charT, traits, Allocator>& rhs)
356 noexcept(noexcept(lhs.swap(rhs)));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000357
358template<class charT, class traits, class Allocator>
359basic_istream<charT, traits>&
360operator>>(basic_istream<charT, traits>& is, basic_string<charT, traits, Allocator>& str);
361
362template<class charT, class traits, class Allocator>
363basic_ostream<charT, traits>&
364operator<<(basic_ostream<charT, traits>& os, const basic_string<charT, traits, Allocator>& str);
365
366template<class charT, class traits, class Allocator>
Howard Hinnant324bb032010-08-22 00:02:43 +0000367basic_istream<charT, traits>&
Howard Hinnanta6a062d2010-06-02 18:20:39 +0000368getline(basic_istream<charT, traits>& is, basic_string<charT, traits, Allocator>& str,
369 charT delim);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000370
371template<class charT, class traits, class Allocator>
372basic_istream<charT, traits>&
373getline(basic_istream<charT, traits>& is, basic_string<charT, traits, Allocator>& str);
374
375typedef basic_string<char> string;
376typedef basic_string<wchar_t> wstring;
Howard Hinnanta6a062d2010-06-02 18:20:39 +0000377typedef basic_string<char16_t> u16string;
378typedef basic_string<char32_t> u32string;
379
380int stoi (const string& str, size_t* idx = 0, int base = 10);
381long stol (const string& str, size_t* idx = 0, int base = 10);
382unsigned long stoul (const string& str, size_t* idx = 0, int base = 10);
383long long stoll (const string& str, size_t* idx = 0, int base = 10);
384unsigned long long stoull(const string& str, size_t* idx = 0, int base = 10);
385
386float stof (const string& str, size_t* idx = 0);
387double stod (const string& str, size_t* idx = 0);
388long double stold(const string& str, size_t* idx = 0);
389
390string to_string(int val);
391string to_string(unsigned val);
392string to_string(long val);
393string to_string(unsigned long val);
394string to_string(long long val);
395string to_string(unsigned long long val);
396string to_string(float val);
397string to_string(double val);
398string to_string(long double val);
399
400int stoi (const wstring& str, size_t* idx = 0, int base = 10);
401long stol (const wstring& str, size_t* idx = 0, int base = 10);
402unsigned long stoul (const wstring& str, size_t* idx = 0, int base = 10);
403long long stoll (const wstring& str, size_t* idx = 0, int base = 10);
404unsigned long long stoull(const wstring& str, size_t* idx = 0, int base = 10);
405
406float stof (const wstring& str, size_t* idx = 0);
407double stod (const wstring& str, size_t* idx = 0);
408long double stold(const wstring& str, size_t* idx = 0);
409
410wstring to_wstring(int val);
411wstring to_wstring(unsigned val);
412wstring to_wstring(long val);
413wstring to_wstring(unsigned long val);
414wstring to_wstring(long long val);
415wstring to_wstring(unsigned long long val);
416wstring to_wstring(float val);
417wstring to_wstring(double val);
418wstring to_wstring(long double val);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000419
420template <> struct hash<string>;
421template <> struct hash<u16string>;
422template <> struct hash<u32string>;
423template <> struct hash<wstring>;
424
425} // std
426
427*/
428
429#include <__config>
430#include <iosfwd>
431#include <cstring>
Howard Hinnantadff4892010-05-24 17:49:41 +0000432#include <cstdio> // For EOF.
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000433#include <cwchar>
434#include <algorithm>
435#include <iterator>
436#include <utility>
437#include <memory>
438#include <stdexcept>
439#include <type_traits>
440#include <initializer_list>
441#include <__functional_base>
442#ifndef _LIBCPP_HAS_NO_UNICODE_CHARS
443#include <cstdint>
444#endif
445#if defined(_LIBCPP_NO_EXCEPTIONS) || defined(_LIBCPP_DEBUG)
446#include <cassert>
447#endif
448
449#pragma GCC system_header
450
451_LIBCPP_BEGIN_NAMESPACE_STD
452
453// fpos
454
455template <class _StateT>
Howard Hinnant8d7a9552010-09-23 17:31:07 +0000456class _LIBCPP_VISIBLE fpos
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000457{
458private:
459 _StateT __st_;
460 streamoff __off_;
461public:
462 _LIBCPP_INLINE_VISIBILITY fpos(streamoff __off = streamoff()) : __st_(), __off_(__off) {}
463
464 _LIBCPP_INLINE_VISIBILITY operator streamoff() const {return __off_;}
465
466 _LIBCPP_INLINE_VISIBILITY _StateT state() const {return __st_;}
467 _LIBCPP_INLINE_VISIBILITY void state(_StateT __st) {__st_ = __st;}
468
469 _LIBCPP_INLINE_VISIBILITY fpos& operator+=(streamoff __off) {__off_ += __off; return *this;}
470 _LIBCPP_INLINE_VISIBILITY fpos operator+ (streamoff __off) const {fpos __t(*this); __t += __off; return __t;}
471 _LIBCPP_INLINE_VISIBILITY fpos& operator-=(streamoff __off) {__off_ -= __off; return *this;}
472 _LIBCPP_INLINE_VISIBILITY fpos operator- (streamoff __off) const {fpos __t(*this); __t -= __off; return __t;}
473};
474
475template <class _StateT>
476inline _LIBCPP_INLINE_VISIBILITY
477streamoff operator-(const fpos<_StateT>& __x, const fpos<_StateT>& __y)
478 {return streamoff(__x) - streamoff(__y);}
479
480template <class _StateT>
481inline _LIBCPP_INLINE_VISIBILITY
482bool operator==(const fpos<_StateT>& __x, const fpos<_StateT>& __y)
483 {return streamoff(__x) == streamoff(__y);}
484
485template <class _StateT>
486inline _LIBCPP_INLINE_VISIBILITY
487bool operator!=(const fpos<_StateT>& __x, const fpos<_StateT>& __y)
488 {return streamoff(__x) != streamoff(__y);}
489
490// char_traits
491
492template <class _CharT>
Howard Hinnant36cdf022010-09-10 16:42:26 +0000493struct _LIBCPP_VISIBLE char_traits
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000494{
495 typedef _CharT char_type;
496 typedef int int_type;
497 typedef streamoff off_type;
498 typedef streampos pos_type;
499 typedef mbstate_t state_type;
500
Howard Hinnanta6119a82011-05-29 19:57:12 +0000501 _LIBCPP_INLINE_VISIBILITY
502 static void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT
503 {__c1 = __c2;}
504 _LIBCPP_INLINE_VISIBILITY
505 static bool eq(char_type __c1, char_type __c2) _NOEXCEPT
506 {return __c1 == __c2;}
507 _LIBCPP_INLINE_VISIBILITY
508 static bool lt(char_type __c1, char_type __c2) _NOEXCEPT
509 {return __c1 < __c2;}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000510
511 static int compare(const char_type* __s1, const char_type* __s2, size_t __n);
512 static size_t length(const char_type* __s);
513 static const char_type* find(const char_type* __s, size_t __n, const char_type& __a);
514 static char_type* move(char_type* __s1, const char_type* __s2, size_t __n);
515 static char_type* copy(char_type* __s1, const char_type* __s2, size_t __n);
516 static char_type* assign(char_type* __s, size_t __n, char_type __a);
517
Howard Hinnanta6119a82011-05-29 19:57:12 +0000518 _LIBCPP_INLINE_VISIBILITY static int_type not_eof(int_type __c) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000519 {return eq_int_type(__c, eof()) ? ~eof() : __c;}
Howard Hinnanta6119a82011-05-29 19:57:12 +0000520 _LIBCPP_INLINE_VISIBILITY
521 static char_type to_char_type(int_type __c) _NOEXCEPT
522 {return char_type(__c);}
523 _LIBCPP_INLINE_VISIBILITY
524 static int_type to_int_type(char_type __c) _NOEXCEPT
525 {return int_type(__c);}
526 _LIBCPP_INLINE_VISIBILITY
527 static bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000528 {return __c1 == __c2;}
Howard Hinnanta6119a82011-05-29 19:57:12 +0000529 _LIBCPP_INLINE_VISIBILITY
530 static int_type eof() _NOEXCEPT
531 {return int_type(EOF);}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000532};
533
534template <class _CharT>
535int
536char_traits<_CharT>::compare(const char_type* __s1, const char_type* __s2, size_t __n)
537{
538 for (; __n; --__n, ++__s1, ++__s2)
539 {
540 if (lt(*__s1, *__s2))
541 return -1;
542 if (lt(*__s2, *__s1))
543 return 1;
544 }
545 return 0;
546}
547
548template <class _CharT>
549inline _LIBCPP_INLINE_VISIBILITY
550size_t
551char_traits<_CharT>::length(const char_type* __s)
552{
553 size_t __len = 0;
554 for (; !eq(*__s, char_type(0)); ++__s)
555 ++__len;
556 return __len;
557}
558
559template <class _CharT>
560inline _LIBCPP_INLINE_VISIBILITY
561const _CharT*
562char_traits<_CharT>::find(const char_type* __s, size_t __n, const char_type& __a)
563{
564 for (; __n; --__n)
565 {
566 if (eq(*__s, __a))
567 return __s;
568 ++__s;
569 }
570 return 0;
571}
572
573template <class _CharT>
574_CharT*
575char_traits<_CharT>::move(char_type* __s1, const char_type* __s2, size_t __n)
576{
577 char_type* __r = __s1;
578 if (__s1 < __s2)
579 {
580 for (; __n; --__n, ++__s1, ++__s2)
581 assign(*__s1, *__s2);
582 }
583 else if (__s2 < __s1)
584 {
585 __s1 += __n;
586 __s2 += __n;
587 for (; __n; --__n)
588 assign(*--__s1, *--__s2);
589 }
590 return __r;
591}
592
593template <class _CharT>
594inline _LIBCPP_INLINE_VISIBILITY
595_CharT*
596char_traits<_CharT>::copy(char_type* __s1, const char_type* __s2, size_t __n)
597{
598 char_type* __r = __s1;
599 for (; __n; --__n, ++__s1, ++__s2)
600 assign(*__s1, *__s2);
601 return __r;
602}
603
604template <class _CharT>
605inline _LIBCPP_INLINE_VISIBILITY
606_CharT*
607char_traits<_CharT>::assign(char_type* __s, size_t __n, char_type __a)
608{
609 char_type* __r = __s;
610 for (; __n; --__n, ++__s)
611 assign(*__s, __a);
612 return __r;
613}
614
615// char_traits<char>
616
617template <>
Howard Hinnant36cdf022010-09-10 16:42:26 +0000618struct _LIBCPP_VISIBLE char_traits<char>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000619{
620 typedef char char_type;
621 typedef int int_type;
622 typedef streamoff off_type;
623 typedef streampos pos_type;
624 typedef mbstate_t state_type;
625
Howard Hinnanta6119a82011-05-29 19:57:12 +0000626 _LIBCPP_INLINE_VISIBILITY
627 static void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT
628 {__c1 = __c2;}
629 _LIBCPP_INLINE_VISIBILITY
630 static bool eq(char_type __c1, char_type __c2) _NOEXCEPT
631 {return __c1 == __c2;}
632 _LIBCPP_INLINE_VISIBILITY
633 static bool lt(char_type __c1, char_type __c2) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000634 {return (unsigned char)__c1 < (unsigned char)__c2;}
635
Howard Hinnanta6119a82011-05-29 19:57:12 +0000636 _LIBCPP_INLINE_VISIBILITY
637 static int compare(const char_type* __s1, const char_type* __s2, size_t __n)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000638 {return memcmp(__s1, __s2, __n);}
Howard Hinnanta6119a82011-05-29 19:57:12 +0000639 _LIBCPP_INLINE_VISIBILITY
640 static size_t length(const char_type* __s) {return strlen(__s);}
641 _LIBCPP_INLINE_VISIBILITY
642 static const char_type* find(const char_type* __s, size_t __n, const char_type& __a)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000643 {return (const char_type*)memchr(__s, to_int_type(__a), __n);}
Howard Hinnanta6119a82011-05-29 19:57:12 +0000644 _LIBCPP_INLINE_VISIBILITY
645 static char_type* move(char_type* __s1, const char_type* __s2, size_t __n)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000646 {return (char_type*)memmove(__s1, __s2, __n);}
Howard Hinnanta6119a82011-05-29 19:57:12 +0000647 _LIBCPP_INLINE_VISIBILITY
648 static char_type* copy(char_type* __s1, const char_type* __s2, size_t __n)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000649 {return (char_type*)memcpy(__s1, __s2, __n);}
Howard Hinnanta6119a82011-05-29 19:57:12 +0000650 _LIBCPP_INLINE_VISIBILITY
651 static char_type* assign(char_type* __s, size_t __n, char_type __a)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000652 {return (char_type*)memset(__s, to_int_type(__a), __n);}
653
Howard Hinnanta6119a82011-05-29 19:57:12 +0000654 _LIBCPP_INLINE_VISIBILITY static int_type not_eof(int_type __c) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000655 {return eq_int_type(__c, eof()) ? ~eof() : __c;}
Howard Hinnanta6119a82011-05-29 19:57:12 +0000656 _LIBCPP_INLINE_VISIBILITY
657 static char_type to_char_type(int_type __c) _NOEXCEPT
658 {return char_type(__c);}
659 _LIBCPP_INLINE_VISIBILITY
660 static int_type to_int_type(char_type __c) _NOEXCEPT
661 {return int_type((unsigned char)__c);}
662 _LIBCPP_INLINE_VISIBILITY
663 static bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000664 {return __c1 == __c2;}
Howard Hinnanta6119a82011-05-29 19:57:12 +0000665 _LIBCPP_INLINE_VISIBILITY
666 static int_type eof() _NOEXCEPT
667 {return int_type(EOF);}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000668};
669
670// char_traits<wchar_t>
671
672template <>
Howard Hinnant8d7a9552010-09-23 17:31:07 +0000673struct _LIBCPP_VISIBLE char_traits<wchar_t>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000674{
675 typedef wchar_t char_type;
676 typedef wint_t int_type;
677 typedef streamoff off_type;
678 typedef streampos pos_type;
679 typedef mbstate_t state_type;
680
Howard Hinnanta6119a82011-05-29 19:57:12 +0000681 _LIBCPP_INLINE_VISIBILITY
682 static void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT
683 {__c1 = __c2;}
684 _LIBCPP_INLINE_VISIBILITY
685 static bool eq(char_type __c1, char_type __c2) _NOEXCEPT
686 {return __c1 == __c2;}
687 _LIBCPP_INLINE_VISIBILITY
688 static bool lt(char_type __c1, char_type __c2) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000689 {return __c1 < __c2;}
690
Howard Hinnanta6119a82011-05-29 19:57:12 +0000691 _LIBCPP_INLINE_VISIBILITY
692 static int compare(const char_type* __s1, const char_type* __s2, size_t __n)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000693 {return wmemcmp(__s1, __s2, __n);}
Howard Hinnanta6119a82011-05-29 19:57:12 +0000694 _LIBCPP_INLINE_VISIBILITY
695 static size_t length(const char_type* __s)
696 {return wcslen(__s);}
697 _LIBCPP_INLINE_VISIBILITY
698 static const char_type* find(const char_type* __s, size_t __n, const char_type& __a)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000699 {return (const char_type*)wmemchr(__s, __a, __n);}
Howard Hinnanta6119a82011-05-29 19:57:12 +0000700 _LIBCPP_INLINE_VISIBILITY
701 static char_type* move(char_type* __s1, const char_type* __s2, size_t __n)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000702 {return (char_type*)wmemmove(__s1, __s2, __n);}
Howard Hinnanta6119a82011-05-29 19:57:12 +0000703 _LIBCPP_INLINE_VISIBILITY
704 static char_type* copy(char_type* __s1, const char_type* __s2, size_t __n)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000705 {return (char_type*)wmemcpy(__s1, __s2, __n);}
Howard Hinnanta6119a82011-05-29 19:57:12 +0000706 _LIBCPP_INLINE_VISIBILITY
707 static char_type* assign(char_type* __s, size_t __n, char_type __a)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000708 {return (char_type*)wmemset(__s, __a, __n);}
709
Howard Hinnanta6119a82011-05-29 19:57:12 +0000710 _LIBCPP_INLINE_VISIBILITY
711 static int_type not_eof(int_type __c) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000712 {return eq_int_type(__c, eof()) ? ~eof() : __c;}
Howard Hinnanta6119a82011-05-29 19:57:12 +0000713 _LIBCPP_INLINE_VISIBILITY
714 static char_type to_char_type(int_type __c) _NOEXCEPT
715 {return char_type(__c);}
716 _LIBCPP_INLINE_VISIBILITY
717 static int_type to_int_type(char_type __c) _NOEXCEPT
718 {return int_type(__c);}
719 _LIBCPP_INLINE_VISIBILITY
720 static bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000721 {return __c1 == __c2;}
Howard Hinnanta6119a82011-05-29 19:57:12 +0000722 _LIBCPP_INLINE_VISIBILITY
723 static int_type eof() _NOEXCEPT
724 {return int_type(WEOF);}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000725};
726
727#ifndef _LIBCPP_HAS_NO_UNICODE_CHARS
728
729template <>
Howard Hinnant8d7a9552010-09-23 17:31:07 +0000730struct _LIBCPP_VISIBLE char_traits<char16_t>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000731{
732 typedef char16_t char_type;
733 typedef uint_least16_t int_type;
734 typedef streamoff off_type;
735 typedef u16streampos pos_type;
736 typedef mbstate_t state_type;
737
Howard Hinnanta6119a82011-05-29 19:57:12 +0000738 _LIBCPP_INLINE_VISIBILITY
739 static void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT
740 {__c1 = __c2;}
741 _LIBCPP_INLINE_VISIBILITY
742 static bool eq(char_type __c1, char_type __c2) _NOEXCEPT
743 {return __c1 == __c2;}
744 _LIBCPP_INLINE_VISIBILITY
745 static bool lt(char_type __c1, char_type __c2) _NOEXCEPT
746 {return __c1 < __c2;}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000747
748 static int compare(const char_type* __s1, const char_type* __s2, size_t __n);
749 static size_t length(const char_type* __s);
750 static const char_type* find(const char_type* __s, size_t __n, const char_type& __a);
751 static char_type* move(char_type* __s1, const char_type* __s2, size_t __n);
752 static char_type* copy(char_type* __s1, const char_type* __s2, size_t __n);
753 static char_type* assign(char_type* __s, size_t __n, char_type __a);
754
Howard Hinnanta6119a82011-05-29 19:57:12 +0000755 _LIBCPP_INLINE_VISIBILITY
756 static int_type not_eof(int_type __c) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000757 {return eq_int_type(__c, eof()) ? ~eof() : __c;}
Howard Hinnanta6119a82011-05-29 19:57:12 +0000758 _LIBCPP_INLINE_VISIBILITY
759 static char_type to_char_type(int_type __c) _NOEXCEPT
760 {return char_type(__c);}
761 _LIBCPP_INLINE_VISIBILITY
762 static int_type to_int_type(char_type __c) _NOEXCEPT
763 {return int_type(__c);}
764 _LIBCPP_INLINE_VISIBILITY
765 static bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000766 {return __c1 == __c2;}
Howard Hinnanta6119a82011-05-29 19:57:12 +0000767 _LIBCPP_INLINE_VISIBILITY
768 static int_type eof() _NOEXCEPT
769 {return int_type(0xDFFF);}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000770};
771
772inline _LIBCPP_INLINE_VISIBILITY
773int
774char_traits<char16_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n)
775{
776 for (; __n; --__n, ++__s1, ++__s2)
777 {
778 if (lt(*__s1, *__s2))
779 return -1;
780 if (lt(*__s2, *__s1))
781 return 1;
782 }
783 return 0;
784}
785
786inline _LIBCPP_INLINE_VISIBILITY
787size_t
788char_traits<char16_t>::length(const char_type* __s)
789{
790 size_t __len = 0;
791 for (; !eq(*__s, char_type(0)); ++__s)
792 ++__len;
793 return __len;
794}
795
796inline _LIBCPP_INLINE_VISIBILITY
797const char16_t*
798char_traits<char16_t>::find(const char_type* __s, size_t __n, const char_type& __a)
799{
800 for (; __n; --__n)
801 {
802 if (eq(*__s, __a))
803 return __s;
804 ++__s;
805 }
806 return 0;
807}
808
809inline _LIBCPP_INLINE_VISIBILITY
810char16_t*
811char_traits<char16_t>::move(char_type* __s1, const char_type* __s2, size_t __n)
812{
813 char_type* __r = __s1;
814 if (__s1 < __s2)
815 {
816 for (; __n; --__n, ++__s1, ++__s2)
817 assign(*__s1, *__s2);
818 }
819 else if (__s2 < __s1)
820 {
821 __s1 += __n;
822 __s2 += __n;
823 for (; __n; --__n)
824 assign(*--__s1, *--__s2);
825 }
826 return __r;
827}
828
829inline _LIBCPP_INLINE_VISIBILITY
830char16_t*
831char_traits<char16_t>::copy(char_type* __s1, const char_type* __s2, size_t __n)
832{
833 char_type* __r = __s1;
834 for (; __n; --__n, ++__s1, ++__s2)
835 assign(*__s1, *__s2);
836 return __r;
837}
838
839inline _LIBCPP_INLINE_VISIBILITY
840char16_t*
841char_traits<char16_t>::assign(char_type* __s, size_t __n, char_type __a)
842{
843 char_type* __r = __s;
844 for (; __n; --__n, ++__s)
845 assign(*__s, __a);
846 return __r;
847}
848
849template <>
Howard Hinnant8d7a9552010-09-23 17:31:07 +0000850struct _LIBCPP_VISIBLE char_traits<char32_t>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000851{
852 typedef char32_t char_type;
853 typedef uint_least32_t int_type;
854 typedef streamoff off_type;
855 typedef u32streampos pos_type;
856 typedef mbstate_t state_type;
857
Howard Hinnanta6119a82011-05-29 19:57:12 +0000858 _LIBCPP_INLINE_VISIBILITY
859 static void assign(char_type& __c1, const char_type& __c2) _NOEXCEPT
860 {__c1 = __c2;}
861 _LIBCPP_INLINE_VISIBILITY
862 static bool eq(char_type __c1, char_type __c2) _NOEXCEPT
863 {return __c1 == __c2;}
864 _LIBCPP_INLINE_VISIBILITY
865 static bool lt(char_type __c1, char_type __c2) _NOEXCEPT
866 {return __c1 < __c2;}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000867
868 static int compare(const char_type* __s1, const char_type* __s2, size_t __n);
869 static size_t length(const char_type* __s);
870 static const char_type* find(const char_type* __s, size_t __n, const char_type& __a);
871 static char_type* move(char_type* __s1, const char_type* __s2, size_t __n);
872 static char_type* copy(char_type* __s1, const char_type* __s2, size_t __n);
873 static char_type* assign(char_type* __s, size_t __n, char_type __a);
874
Howard Hinnanta6119a82011-05-29 19:57:12 +0000875 _LIBCPP_INLINE_VISIBILITY
876 static int_type not_eof(int_type __c) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000877 {return eq_int_type(__c, eof()) ? ~eof() : __c;}
Howard Hinnanta6119a82011-05-29 19:57:12 +0000878 _LIBCPP_INLINE_VISIBILITY
879 static char_type to_char_type(int_type __c) _NOEXCEPT
880 {return char_type(__c);}
881 _LIBCPP_INLINE_VISIBILITY
882 static int_type to_int_type(char_type __c) _NOEXCEPT
883 {return int_type(__c);}
884 _LIBCPP_INLINE_VISIBILITY
885 static bool eq_int_type(int_type __c1, int_type __c2) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000886 {return __c1 == __c2;}
Howard Hinnanta6119a82011-05-29 19:57:12 +0000887 _LIBCPP_INLINE_VISIBILITY
888 static int_type eof() _NOEXCEPT
889 {return int_type(0xFFFFFFFF);}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000890};
891
892inline _LIBCPP_INLINE_VISIBILITY
893int
894char_traits<char32_t>::compare(const char_type* __s1, const char_type* __s2, size_t __n)
895{
896 for (; __n; --__n, ++__s1, ++__s2)
897 {
898 if (lt(*__s1, *__s2))
899 return -1;
900 if (lt(*__s2, *__s1))
901 return 1;
902 }
903 return 0;
904}
905
906inline _LIBCPP_INLINE_VISIBILITY
907size_t
908char_traits<char32_t>::length(const char_type* __s)
909{
910 size_t __len = 0;
911 for (; !eq(*__s, char_type(0)); ++__s)
912 ++__len;
913 return __len;
914}
915
916inline _LIBCPP_INLINE_VISIBILITY
917const char32_t*
918char_traits<char32_t>::find(const char_type* __s, size_t __n, const char_type& __a)
919{
920 for (; __n; --__n)
921 {
922 if (eq(*__s, __a))
923 return __s;
924 ++__s;
925 }
926 return 0;
927}
928
929inline _LIBCPP_INLINE_VISIBILITY
930char32_t*
931char_traits<char32_t>::move(char_type* __s1, const char_type* __s2, size_t __n)
932{
933 char_type* __r = __s1;
934 if (__s1 < __s2)
935 {
936 for (; __n; --__n, ++__s1, ++__s2)
937 assign(*__s1, *__s2);
938 }
939 else if (__s2 < __s1)
940 {
941 __s1 += __n;
942 __s2 += __n;
943 for (; __n; --__n)
944 assign(*--__s1, *--__s2);
945 }
946 return __r;
947}
948
949inline _LIBCPP_INLINE_VISIBILITY
950char32_t*
951char_traits<char32_t>::copy(char_type* __s1, const char_type* __s2, size_t __n)
952{
953 char_type* __r = __s1;
954 for (; __n; --__n, ++__s1, ++__s2)
955 assign(*__s1, *__s2);
956 return __r;
957}
958
959inline _LIBCPP_INLINE_VISIBILITY
960char32_t*
961char_traits<char32_t>::assign(char_type* __s, size_t __n, char_type __a)
962{
963 char_type* __r = __s;
964 for (; __n; --__n, ++__s)
965 assign(*__s, __a);
966 return __r;
967}
968
Howard Hinnant324bb032010-08-22 00:02:43 +0000969#endif // _LIBCPP_HAS_NO_UNICODE_CHARS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000970
971// basic_string
972
973template<class _CharT, class _Traits, class _Allocator>
974basic_string<_CharT, _Traits, _Allocator>
Howard Hinnant2b1b2d42011-06-14 19:58:17 +0000975operator+(const basic_string<_CharT, _Traits, _Allocator>& __x,
976 const basic_string<_CharT, _Traits, _Allocator>& __y);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000977
978template<class _CharT, class _Traits, class _Allocator>
979basic_string<_CharT, _Traits, _Allocator>
Howard Hinnant2b1b2d42011-06-14 19:58:17 +0000980operator+(const _CharT* __x, const basic_string<_CharT,_Traits,_Allocator>& __y);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000981
982template<class _CharT, class _Traits, class _Allocator>
983basic_string<_CharT, _Traits, _Allocator>
Howard Hinnant2b1b2d42011-06-14 19:58:17 +0000984operator+(_CharT __x, const basic_string<_CharT,_Traits,_Allocator>& __y);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000985
986template<class _CharT, class _Traits, class _Allocator>
987basic_string<_CharT, _Traits, _Allocator>
Howard Hinnant2b1b2d42011-06-14 19:58:17 +0000988operator+(const basic_string<_CharT, _Traits, _Allocator>& __x, const _CharT* __y);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000989
990template<class _CharT, class _Traits, class _Allocator>
991basic_string<_CharT, _Traits, _Allocator>
Howard Hinnant2b1b2d42011-06-14 19:58:17 +0000992operator+(const basic_string<_CharT, _Traits, _Allocator>& __x, _CharT __y);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +0000993
994template <bool>
995class __basic_string_common
996{
997protected:
998 void __throw_length_error() const;
999 void __throw_out_of_range() const;
1000};
1001
1002template <bool __b>
1003void
1004__basic_string_common<__b>::__throw_length_error() const
1005{
1006#ifndef _LIBCPP_NO_EXCEPTIONS
1007 throw length_error("basic_string");
1008#else
1009 assert(!"basic_string length_error");
1010#endif
1011}
1012
1013template <bool __b>
1014void
1015__basic_string_common<__b>::__throw_out_of_range() const
1016{
1017#ifndef _LIBCPP_NO_EXCEPTIONS
1018 throw out_of_range("basic_string");
1019#else
1020 assert(!"basic_string out_of_range");
1021#endif
1022}
1023
1024extern template class __basic_string_common<true>;
1025
Howard Hinnant324bb032010-08-22 00:02:43 +00001026template<class _CharT, class _Traits, class _Allocator>
Howard Hinnant36cdf022010-09-10 16:42:26 +00001027class _LIBCPP_VISIBLE basic_string
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001028 : private __basic_string_common<true>
1029{
1030public:
1031 typedef basic_string __self;
1032 typedef _Traits traits_type;
1033 typedef typename traits_type::char_type value_type;
1034 typedef _Allocator allocator_type;
Howard Hinnante32b5e22010-11-17 17:55:08 +00001035 typedef allocator_traits<allocator_type> __alloc_traits;
1036 typedef typename __alloc_traits::size_type size_type;
1037 typedef typename __alloc_traits::difference_type difference_type;
Howard Hinnant53f7d4c2011-06-03 18:40:47 +00001038 typedef value_type& reference;
1039 typedef const value_type& const_reference;
Howard Hinnante32b5e22010-11-17 17:55:08 +00001040 typedef typename __alloc_traits::pointer pointer;
1041 typedef typename __alloc_traits::const_pointer const_pointer;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001042#ifdef _LIBCPP_DEBUG
1043 typedef __debug_iter<basic_string, pointer> iterator;
1044 typedef __debug_iter<basic_string, const_pointer> const_iterator;
1045
1046 friend class __debug_iter<basic_string, pointer>;
1047 friend class __debug_iter<basic_string, const_pointer>;
1048#elif defined(_LIBCPP_RAW_ITERATORS)
1049 typedef pointer iterator;
1050 typedef const_pointer const_iterator;
Howard Hinnant324bb032010-08-22 00:02:43 +00001051#else // defined(_LIBCPP_RAW_ITERATORS)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001052 typedef __wrap_iter<pointer> iterator;
1053 typedef __wrap_iter<const_pointer> const_iterator;
Howard Hinnant324bb032010-08-22 00:02:43 +00001054#endif // defined(_LIBCPP_RAW_ITERATORS)
Howard Hinnant0949eed2011-06-30 21:18:19 +00001055 typedef _VSTD::reverse_iterator<iterator> reverse_iterator;
1056 typedef _VSTD::reverse_iterator<const_iterator> const_reverse_iterator;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001057
1058private:
1059 struct __long
1060 {
1061 size_type __cap_;
1062 size_type __size_;
1063 pointer __data_;
1064 };
1065
1066#if _LIBCPP_BIG_ENDIAN
1067 enum {__short_mask = 0x80};
1068 enum {__long_mask = ~(size_type(~0) >> 1)};
Howard Hinnant324bb032010-08-22 00:02:43 +00001069#else // _LIBCPP_BIG_ENDIAN
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001070 enum {__short_mask = 0x01};
1071 enum {__long_mask = 0x1};
Howard Hinnant324bb032010-08-22 00:02:43 +00001072#endif // _LIBCPP_BIG_ENDIAN
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001073
1074 enum {__mask = size_type(~0) >> 1};
1075
1076 enum {__min_cap = (sizeof(__long) - 1)/sizeof(value_type) > 2 ?
1077 (sizeof(__long) - 1)/sizeof(value_type) : 2};
1078
1079 struct __short
1080 {
1081 union
1082 {
1083 unsigned char __size_;
1084 value_type _;
1085 };
1086 value_type __data_[__min_cap];
1087 };
1088
1089 union _{__long _; __short __;};
1090
1091 enum {__n_words = sizeof(_) / sizeof(size_type)};
1092
1093 struct __raw
1094 {
1095 size_type __words[__n_words];
1096 };
1097
1098 struct __rep
1099 {
1100 union
1101 {
1102 __long __l;
1103 __short __s;
1104 __raw __r;
1105 };
1106 };
1107
1108 __compressed_pair<__rep, allocator_type> __r_;
1109
1110#ifdef _LIBCPP_DEBUG
1111
1112 pair<iterator*, const_iterator*> __iterator_list_;
1113
1114 _LIBCPP_INLINE_VISIBILITY iterator*& __get_iterator_list(iterator*) {return __iterator_list_.first;}
1115 _LIBCPP_INLINE_VISIBILITY const_iterator*& __get_iterator_list(const_iterator*) {return __iterator_list_.second;}
1116
1117#endif // _LIBCPP_DEBUG
1118
1119public:
1120 static const size_type npos = -1;
1121
Howard Hinnant53f7d4c2011-06-03 18:40:47 +00001122 _LIBCPP_INLINE_VISIBILITY basic_string()
1123 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value);
Howard Hinnant2d72b1e2010-12-17 14:46:43 +00001124 _LIBCPP_INLINE_VISIBILITY explicit basic_string(const allocator_type& __a);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001125 basic_string(const basic_string& __str);
1126 basic_string(const basic_string& __str, const allocator_type& __a);
Howard Hinnant73d21a42010-09-04 23:28:19 +00001127#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant9f193f22011-01-26 00:06:59 +00001128 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant53f7d4c2011-06-03 18:40:47 +00001129 basic_string(basic_string&& __str)
1130 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value);
Howard Hinnant9f193f22011-01-26 00:06:59 +00001131 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001132 basic_string(basic_string&& __str, const allocator_type& __a);
Howard Hinnant73d21a42010-09-04 23:28:19 +00001133#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant2d72b1e2010-12-17 14:46:43 +00001134 _LIBCPP_INLINE_VISIBILITY basic_string(const_pointer __s);
1135 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001136 basic_string(const_pointer __s, const allocator_type& __a);
Howard Hinnant2d72b1e2010-12-17 14:46:43 +00001137 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001138 basic_string(const_pointer __s, size_type __n);
Howard Hinnant2d72b1e2010-12-17 14:46:43 +00001139 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001140 basic_string(const_pointer __s, size_type __n, const allocator_type& __a);
Howard Hinnant2d72b1e2010-12-17 14:46:43 +00001141 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001142 basic_string(size_type __n, value_type __c);
Howard Hinnant2d72b1e2010-12-17 14:46:43 +00001143 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001144 basic_string(size_type __n, value_type __c, const allocator_type& __a);
1145 basic_string(const basic_string& __str, size_type __pos, size_type __n = npos,
1146 const allocator_type& __a = allocator_type());
1147 template<class _InputIterator>
Howard Hinnant2d72b1e2010-12-17 14:46:43 +00001148 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001149 basic_string(_InputIterator __first, _InputIterator __last);
1150 template<class _InputIterator>
Howard Hinnant2d72b1e2010-12-17 14:46:43 +00001151 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001152 basic_string(_InputIterator __first, _InputIterator __last, const allocator_type& __a);
Howard Hinnant2d72b1e2010-12-17 14:46:43 +00001153 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001154 basic_string(initializer_list<value_type> __il);
Howard Hinnant2d72b1e2010-12-17 14:46:43 +00001155 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001156 basic_string(initializer_list<value_type> __il, const allocator_type& __a);
1157
1158 ~basic_string();
1159
Howard Hinnante32b5e22010-11-17 17:55:08 +00001160 basic_string& operator=(const basic_string& __str);
Howard Hinnant73d21a42010-09-04 23:28:19 +00001161#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant2d72b1e2010-12-17 14:46:43 +00001162 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant53f7d4c2011-06-03 18:40:47 +00001163 basic_string& operator=(basic_string&& __str)
1164 _NOEXCEPT_(__alloc_traits::propagate_on_container_move_assignment::value &&
1165 is_nothrow_move_assignable<allocator_type>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001166#endif
Howard Hinnanta6119a82011-05-29 19:57:12 +00001167 _LIBCPP_INLINE_VISIBILITY basic_string& operator=(const_pointer __s) {return assign(__s);}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001168 basic_string& operator=(value_type __c);
Howard Hinnant8d7a9552010-09-23 17:31:07 +00001169 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001170 basic_string& operator=(initializer_list<value_type> __il) {return assign(__il.begin(), __il.size());}
1171
1172#ifndef _LIBCPP_DEBUG
Howard Hinnanta6119a82011-05-29 19:57:12 +00001173 _LIBCPP_INLINE_VISIBILITY
1174 iterator begin() _NOEXCEPT
1175 {return iterator(__get_pointer());}
1176 _LIBCPP_INLINE_VISIBILITY
1177 const_iterator begin() const _NOEXCEPT
1178 {return const_iterator(data());}
1179 _LIBCPP_INLINE_VISIBILITY
1180 iterator end() _NOEXCEPT
1181 {return iterator(__get_pointer() + size());}
1182 _LIBCPP_INLINE_VISIBILITY
1183 const_iterator end() const _NOEXCEPT
1184 {return const_iterator(data() + size());}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001185#else // _LIBCPP_DEBUG
1186 _LIBCPP_INLINE_VISIBILITY iterator begin() {return iterator(this, __get_pointer());}
1187 _LIBCPP_INLINE_VISIBILITY const_iterator begin() const {return const_iterator(this, data());}
1188 _LIBCPP_INLINE_VISIBILITY iterator end() {return iterator(this, __get_pointer() + size());}
1189 _LIBCPP_INLINE_VISIBILITY const_iterator end() const {return const_iterator(this, data() + size());}
1190#endif // _LIBCPP_DEBUG
Howard Hinnanta6119a82011-05-29 19:57:12 +00001191 _LIBCPP_INLINE_VISIBILITY
1192 reverse_iterator rbegin() _NOEXCEPT
1193 {return reverse_iterator(end());}
1194 _LIBCPP_INLINE_VISIBILITY
1195 const_reverse_iterator rbegin() const _NOEXCEPT
1196 {return const_reverse_iterator(end());}
1197 _LIBCPP_INLINE_VISIBILITY
1198 reverse_iterator rend() _NOEXCEPT
1199 {return reverse_iterator(begin());}
1200 _LIBCPP_INLINE_VISIBILITY
1201 const_reverse_iterator rend() const _NOEXCEPT
1202 {return const_reverse_iterator(begin());}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001203
Howard Hinnanta6119a82011-05-29 19:57:12 +00001204 _LIBCPP_INLINE_VISIBILITY
1205 const_iterator cbegin() const _NOEXCEPT
1206 {return begin();}
1207 _LIBCPP_INLINE_VISIBILITY
1208 const_iterator cend() const _NOEXCEPT
1209 {return end();}
1210 _LIBCPP_INLINE_VISIBILITY
1211 const_reverse_iterator crbegin() const _NOEXCEPT
1212 {return rbegin();}
1213 _LIBCPP_INLINE_VISIBILITY
1214 const_reverse_iterator crend() const _NOEXCEPT
1215 {return rend();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001216
Howard Hinnanta6119a82011-05-29 19:57:12 +00001217 _LIBCPP_INLINE_VISIBILITY size_type size() const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001218 {return __is_long() ? __get_long_size() : __get_short_size();}
Howard Hinnanta6119a82011-05-29 19:57:12 +00001219 _LIBCPP_INLINE_VISIBILITY size_type length() const _NOEXCEPT {return size();}
1220 _LIBCPP_INLINE_VISIBILITY size_type max_size() const _NOEXCEPT;
1221 _LIBCPP_INLINE_VISIBILITY size_type capacity() const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001222 {return (__is_long() ? __get_long_cap() : __min_cap) - 1;}
1223
1224 void resize(size_type __n, value_type __c);
1225 _LIBCPP_INLINE_VISIBILITY void resize(size_type __n) {resize(__n, value_type());}
1226
1227 void reserve(size_type res_arg = 0);
Howard Hinnant8d7a9552010-09-23 17:31:07 +00001228 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant53f7d4c2011-06-03 18:40:47 +00001229 void shrink_to_fit() _NOEXCEPT {reserve();}
Howard Hinnant2d72b1e2010-12-17 14:46:43 +00001230 _LIBCPP_INLINE_VISIBILITY
Howard Hinnanta6119a82011-05-29 19:57:12 +00001231 void clear() _NOEXCEPT;
1232 _LIBCPP_INLINE_VISIBILITY bool empty() const _NOEXCEPT {return size() == 0;}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001233
1234 _LIBCPP_INLINE_VISIBILITY const_reference operator[](size_type __pos) const;
1235 _LIBCPP_INLINE_VISIBILITY reference operator[](size_type __pos);
1236
1237 const_reference at(size_type __n) const;
1238 reference at(size_type __n);
1239
1240 _LIBCPP_INLINE_VISIBILITY basic_string& operator+=(const basic_string& __str) {return append(__str);}
1241 _LIBCPP_INLINE_VISIBILITY basic_string& operator+=(const_pointer __s) {return append(__s);}
1242 _LIBCPP_INLINE_VISIBILITY basic_string& operator+=(value_type __c) {push_back(__c); return *this;}
1243 _LIBCPP_INLINE_VISIBILITY basic_string& operator+=(initializer_list<value_type> __il) {return append(__il);}
1244
Howard Hinnant2d72b1e2010-12-17 14:46:43 +00001245 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001246 basic_string& append(const basic_string& __str);
1247 basic_string& append(const basic_string& __str, size_type __pos, size_type __n);
1248 basic_string& append(const_pointer __s, size_type __n);
1249 basic_string& append(const_pointer __s);
1250 basic_string& append(size_type __n, value_type __c);
1251 template<class _InputIterator>
1252 typename enable_if
1253 <
1254 __is_input_iterator <_InputIterator>::value &&
1255 !__is_forward_iterator<_InputIterator>::value,
1256 basic_string&
1257 >::type
1258 append(_InputIterator __first, _InputIterator __last);
1259 template<class _ForwardIterator>
1260 typename enable_if
1261 <
1262 __is_forward_iterator<_ForwardIterator>::value,
1263 basic_string&
1264 >::type
1265 append(_ForwardIterator __first, _ForwardIterator __last);
Howard Hinnant8d7a9552010-09-23 17:31:07 +00001266 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001267 basic_string& append(initializer_list<value_type> __il) {return append(__il.begin(), __il.size());}
1268
1269 void push_back(value_type __c);
Howard Hinnant2d72b1e2010-12-17 14:46:43 +00001270 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001271 void pop_back();
Howard Hinnant2d72b1e2010-12-17 14:46:43 +00001272 _LIBCPP_INLINE_VISIBILITY reference front();
1273 _LIBCPP_INLINE_VISIBILITY const_reference front() const;
1274 _LIBCPP_INLINE_VISIBILITY reference back();
1275 _LIBCPP_INLINE_VISIBILITY const_reference back() const;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001276
Howard Hinnant2d72b1e2010-12-17 14:46:43 +00001277 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001278 basic_string& assign(const basic_string& __str);
Howard Hinnanta6119a82011-05-29 19:57:12 +00001279#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
1280 _LIBCPP_INLINE_VISIBILITY
1281 basic_string& assign(basic_string&& str)
Howard Hinnant0949eed2011-06-30 21:18:19 +00001282 {*this = _VSTD::move(str); return *this;}
Howard Hinnanta6119a82011-05-29 19:57:12 +00001283#endif
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001284 basic_string& assign(const basic_string& __str, size_type __pos, size_type __n);
1285 basic_string& assign(const_pointer __s, size_type __n);
1286 basic_string& assign(const_pointer __s);
1287 basic_string& assign(size_type __n, value_type __c);
1288 template<class _InputIterator>
1289 typename enable_if
1290 <
1291 __is_input_iterator <_InputIterator>::value &&
1292 !__is_forward_iterator<_InputIterator>::value,
1293 basic_string&
1294 >::type
1295 assign(_InputIterator __first, _InputIterator __last);
1296 template<class _ForwardIterator>
1297 typename enable_if
1298 <
1299 __is_forward_iterator<_ForwardIterator>::value,
1300 basic_string&
1301 >::type
1302 assign(_ForwardIterator __first, _ForwardIterator __last);
Howard Hinnant8d7a9552010-09-23 17:31:07 +00001303 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001304 basic_string& assign(initializer_list<value_type> __il) {return assign(__il.begin(), __il.size());}
1305
Howard Hinnant2d72b1e2010-12-17 14:46:43 +00001306 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001307 basic_string& insert(size_type __pos1, const basic_string& __str);
1308 basic_string& insert(size_type __pos1, const basic_string& __str, size_type __pos2, size_type __n);
1309 basic_string& insert(size_type __pos, const_pointer __s, size_type __n);
1310 basic_string& insert(size_type __pos, const_pointer __s);
1311 basic_string& insert(size_type __pos, size_type __n, value_type __c);
1312 iterator insert(const_iterator __pos, value_type __c);
Howard Hinnant2d72b1e2010-12-17 14:46:43 +00001313 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001314 iterator insert(const_iterator __pos, size_type __n, value_type __c);
1315 template<class _InputIterator>
1316 typename enable_if
1317 <
1318 __is_input_iterator <_InputIterator>::value &&
1319 !__is_forward_iterator<_InputIterator>::value,
1320 iterator
1321 >::type
1322 insert(const_iterator __pos, _InputIterator __first, _InputIterator __last);
1323 template<class _ForwardIterator>
1324 typename enable_if
1325 <
1326 __is_forward_iterator<_ForwardIterator>::value,
1327 iterator
1328 >::type
1329 insert(const_iterator __pos, _ForwardIterator __first, _ForwardIterator __last);
Howard Hinnant8d7a9552010-09-23 17:31:07 +00001330 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001331 iterator insert(const_iterator __pos, initializer_list<value_type> __il)
1332 {return insert(__pos, __il.begin(), __il.end());}
1333
1334 basic_string& erase(size_type __pos = 0, size_type __n = npos);
Howard Hinnant2d72b1e2010-12-17 14:46:43 +00001335 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001336 iterator erase(const_iterator __pos);
Howard Hinnant2d72b1e2010-12-17 14:46:43 +00001337 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001338 iterator erase(const_iterator __first, const_iterator __last);
1339
Howard Hinnant2d72b1e2010-12-17 14:46:43 +00001340 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001341 basic_string& replace(size_type __pos1, size_type __n1, const basic_string& __str);
1342 basic_string& replace(size_type __pos1, size_type __n1, const basic_string& __str, size_type __pos2, size_type __n2);
1343 basic_string& replace(size_type __pos, size_type __n1, const_pointer __s, size_type __n2);
1344 basic_string& replace(size_type __pos, size_type __n1, const_pointer __s);
1345 basic_string& replace(size_type __pos, size_type __n1, size_type __n2, value_type __c);
Howard Hinnant2d72b1e2010-12-17 14:46:43 +00001346 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant7b2cb482010-11-17 21:11:40 +00001347 basic_string& replace(const_iterator __i1, const_iterator __i2, const basic_string& __str);
Howard Hinnant2d72b1e2010-12-17 14:46:43 +00001348 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant7b2cb482010-11-17 21:11:40 +00001349 basic_string& replace(const_iterator __i1, const_iterator __i2, const_pointer __s, size_type __n);
Howard Hinnant2d72b1e2010-12-17 14:46:43 +00001350 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant7b2cb482010-11-17 21:11:40 +00001351 basic_string& replace(const_iterator __i1, const_iterator __i2, const_pointer __s);
Howard Hinnant2d72b1e2010-12-17 14:46:43 +00001352 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant7b2cb482010-11-17 21:11:40 +00001353 basic_string& replace(const_iterator __i1, const_iterator __i2, size_type __n, value_type __c);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001354 template<class _InputIterator>
1355 typename enable_if
1356 <
1357 __is_input_iterator<_InputIterator>::value,
1358 basic_string&
1359 >::type
Howard Hinnant7b2cb482010-11-17 21:11:40 +00001360 replace(const_iterator __i1, const_iterator __i2, _InputIterator __j1, _InputIterator __j2);
Howard Hinnant8d7a9552010-09-23 17:31:07 +00001361 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant7b2cb482010-11-17 21:11:40 +00001362 basic_string& replace(const_iterator __i1, const_iterator __i2, initializer_list<value_type> __il)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001363 {return replace(__i1, __i2, __il.begin(), __il.end());}
1364
1365 size_type copy(pointer __s, size_type __n, size_type __pos = 0) const;
Howard Hinnant2d72b1e2010-12-17 14:46:43 +00001366 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001367 basic_string substr(size_type __pos = 0, size_type __n = npos) const;
1368
Howard Hinnant2d72b1e2010-12-17 14:46:43 +00001369 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant53f7d4c2011-06-03 18:40:47 +00001370 void swap(basic_string& __str)
1371 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
1372 __is_nothrow_swappable<allocator_type>::value);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001373
Howard Hinnant2d72b1e2010-12-17 14:46:43 +00001374 _LIBCPP_INLINE_VISIBILITY
Howard Hinnanta6119a82011-05-29 19:57:12 +00001375 const_pointer c_str() const _NOEXCEPT {return data();}
Howard Hinnant2d72b1e2010-12-17 14:46:43 +00001376 _LIBCPP_INLINE_VISIBILITY
Howard Hinnanta6119a82011-05-29 19:57:12 +00001377 const_pointer data() const _NOEXCEPT {return __get_pointer();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001378
Howard Hinnant2d72b1e2010-12-17 14:46:43 +00001379 _LIBCPP_INLINE_VISIBILITY
Howard Hinnanta6119a82011-05-29 19:57:12 +00001380 allocator_type get_allocator() const _NOEXCEPT {return __alloc();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001381
Howard Hinnant2d72b1e2010-12-17 14:46:43 +00001382 _LIBCPP_INLINE_VISIBILITY
Howard Hinnanta6119a82011-05-29 19:57:12 +00001383 size_type find(const basic_string& __str, size_type __pos = 0) const _NOEXCEPT;
1384 size_type find(const_pointer __s, size_type __pos, size_type __n) const _NOEXCEPT;
Howard Hinnant2d72b1e2010-12-17 14:46:43 +00001385 _LIBCPP_INLINE_VISIBILITY
Howard Hinnanta6119a82011-05-29 19:57:12 +00001386 size_type find(const_pointer __s, size_type __pos = 0) const _NOEXCEPT;
1387 size_type find(value_type __c, size_type __pos = 0) const _NOEXCEPT;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001388
Howard Hinnant2d72b1e2010-12-17 14:46:43 +00001389 _LIBCPP_INLINE_VISIBILITY
Howard Hinnanta6119a82011-05-29 19:57:12 +00001390 size_type rfind(const basic_string& __str, size_type __pos = npos) const _NOEXCEPT;
1391 size_type rfind(const_pointer __s, size_type __pos, size_type __n) const _NOEXCEPT;
Howard Hinnant2d72b1e2010-12-17 14:46:43 +00001392 _LIBCPP_INLINE_VISIBILITY
Howard Hinnanta6119a82011-05-29 19:57:12 +00001393 size_type rfind(const_pointer __s, size_type __pos = npos) const _NOEXCEPT;
1394 size_type rfind(value_type __c, size_type __pos = npos) const _NOEXCEPT;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001395
Howard Hinnant2d72b1e2010-12-17 14:46:43 +00001396 _LIBCPP_INLINE_VISIBILITY
Howard Hinnanta6119a82011-05-29 19:57:12 +00001397 size_type find_first_of(const basic_string& __str, size_type __pos = 0) const _NOEXCEPT;
1398 size_type find_first_of(const_pointer __s, size_type __pos, size_type __n) const _NOEXCEPT;
Howard Hinnant2d72b1e2010-12-17 14:46:43 +00001399 _LIBCPP_INLINE_VISIBILITY
Howard Hinnanta6119a82011-05-29 19:57:12 +00001400 size_type find_first_of(const_pointer __s, size_type __pos = 0) const _NOEXCEPT;
Howard Hinnant2d72b1e2010-12-17 14:46:43 +00001401 _LIBCPP_INLINE_VISIBILITY
Howard Hinnanta6119a82011-05-29 19:57:12 +00001402 size_type find_first_of(value_type __c, size_type __pos = 0) const _NOEXCEPT;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001403
Howard Hinnant2d72b1e2010-12-17 14:46:43 +00001404 _LIBCPP_INLINE_VISIBILITY
Howard Hinnanta6119a82011-05-29 19:57:12 +00001405 size_type find_last_of(const basic_string& __str, size_type __pos = npos) const _NOEXCEPT;
1406 size_type find_last_of(const_pointer __s, size_type __pos, size_type __n) const _NOEXCEPT;
Howard Hinnant2d72b1e2010-12-17 14:46:43 +00001407 _LIBCPP_INLINE_VISIBILITY
Howard Hinnanta6119a82011-05-29 19:57:12 +00001408 size_type find_last_of(const_pointer __s, size_type __pos = npos) const _NOEXCEPT;
Howard Hinnant2d72b1e2010-12-17 14:46:43 +00001409 _LIBCPP_INLINE_VISIBILITY
Howard Hinnanta6119a82011-05-29 19:57:12 +00001410 size_type find_last_of(value_type __c, size_type __pos = npos) const _NOEXCEPT;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001411
Howard Hinnant2d72b1e2010-12-17 14:46:43 +00001412 _LIBCPP_INLINE_VISIBILITY
Howard Hinnanta6119a82011-05-29 19:57:12 +00001413 size_type find_first_not_of(const basic_string& __str, size_type __pos = 0) const _NOEXCEPT;
1414 size_type find_first_not_of(const_pointer __s, size_type __pos, size_type __n) const _NOEXCEPT;
1415 _LIBCPP_INLINE_VISIBILITY
1416 size_type find_first_not_of(const_pointer __s, size_type __pos = 0) const _NOEXCEPT;
1417 _LIBCPP_INLINE_VISIBILITY
1418 size_type find_first_not_of(value_type __c, size_type __pos = 0) const _NOEXCEPT;
1419
1420 _LIBCPP_INLINE_VISIBILITY
1421 size_type find_last_not_of(const basic_string& __str, size_type __pos = npos) const _NOEXCEPT;
1422 size_type find_last_not_of(const_pointer __s, size_type __pos, size_type __n) const _NOEXCEPT;
1423 _LIBCPP_INLINE_VISIBILITY
1424 size_type find_last_not_of(const_pointer __s, size_type __pos = npos) const _NOEXCEPT;
1425 _LIBCPP_INLINE_VISIBILITY
1426 size_type find_last_not_of(value_type __c, size_type __pos = npos) const _NOEXCEPT;
1427
1428 _LIBCPP_INLINE_VISIBILITY
1429 int compare(const basic_string& __str) const _NOEXCEPT;
Howard Hinnant2d72b1e2010-12-17 14:46:43 +00001430 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001431 int compare(size_type __pos1, size_type __n1, const basic_string& __str) const;
1432 int compare(size_type __pos1, size_type __n1, const basic_string& __str, size_type __pos2, size_type __n2) const;
Howard Hinnanta6119a82011-05-29 19:57:12 +00001433 int compare(const_pointer __s) const _NOEXCEPT;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001434 int compare(size_type __pos1, size_type __n1, const_pointer __s) const;
1435 int compare(size_type __pos1, size_type __n1, const_pointer __s, size_type __n2) const;
1436
Howard Hinnant2d72b1e2010-12-17 14:46:43 +00001437 _LIBCPP_INLINE_VISIBILITY bool __invariants() const;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001438private:
Howard Hinnanta6119a82011-05-29 19:57:12 +00001439 _LIBCPP_INLINE_VISIBILITY
1440 allocator_type& __alloc() _NOEXCEPT
1441 {return __r_.second();}
1442 _LIBCPP_INLINE_VISIBILITY
1443 const allocator_type& __alloc() const _NOEXCEPT
1444 {return __r_.second();}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001445
Howard Hinnanta6119a82011-05-29 19:57:12 +00001446 _LIBCPP_INLINE_VISIBILITY
1447 bool __is_long() const _NOEXCEPT
1448 {return bool(__r_.first().__s.__size_ & __short_mask);}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001449
Howard Hinnanta6119a82011-05-29 19:57:12 +00001450 _LIBCPP_INLINE_VISIBILITY
1451 void __set_short_size(size_type __s) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001452#if _LIBCPP_BIG_ENDIAN
1453 {__r_.first().__s.__size_ = (unsigned char)(__s);}
1454#else
1455 {__r_.first().__s.__size_ = (unsigned char)(__s << 1);}
1456#endif
Howard Hinnanta6119a82011-05-29 19:57:12 +00001457 _LIBCPP_INLINE_VISIBILITY
1458 size_type __get_short_size() const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001459#if _LIBCPP_BIG_ENDIAN
1460 {return __r_.first().__s.__size_;}
1461#else
1462 {return __r_.first().__s.__size_ >> 1;}
1463#endif
Howard Hinnanta6119a82011-05-29 19:57:12 +00001464 _LIBCPP_INLINE_VISIBILITY
1465 void __set_long_size(size_type __s) _NOEXCEPT
1466 {__r_.first().__l.__size_ = __s;}
1467 _LIBCPP_INLINE_VISIBILITY
1468 size_type __get_long_size() const _NOEXCEPT
1469 {return __r_.first().__l.__size_;}
1470 _LIBCPP_INLINE_VISIBILITY
1471 void __set_size(size_type __s) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001472 {if (__is_long()) __set_long_size(__s); else __set_short_size(__s);}
1473
Howard Hinnanta6119a82011-05-29 19:57:12 +00001474 _LIBCPP_INLINE_VISIBILITY
1475 void __set_long_cap(size_type __s) _NOEXCEPT
1476 {__r_.first().__l.__cap_ = __long_mask | __s;}
1477 _LIBCPP_INLINE_VISIBILITY
1478 size_type __get_long_cap() const _NOEXCEPT
1479 {return __r_.first().__l.__cap_ & ~__long_mask;}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001480
Howard Hinnanta6119a82011-05-29 19:57:12 +00001481 _LIBCPP_INLINE_VISIBILITY
1482 void __set_long_pointer(pointer __p) _NOEXCEPT
1483 {__r_.first().__l.__data_ = __p;}
1484 _LIBCPP_INLINE_VISIBILITY
1485 pointer __get_long_pointer() _NOEXCEPT
1486 {return __r_.first().__l.__data_;}
1487 _LIBCPP_INLINE_VISIBILITY
1488 const_pointer __get_long_pointer() const _NOEXCEPT
1489 {return __r_.first().__l.__data_;}
1490 _LIBCPP_INLINE_VISIBILITY
1491 pointer __get_short_pointer() _NOEXCEPT
1492 {return __r_.first().__s.__data_;}
1493 _LIBCPP_INLINE_VISIBILITY
1494 const_pointer __get_short_pointer() const _NOEXCEPT
1495 {return __r_.first().__s.__data_;}
1496 _LIBCPP_INLINE_VISIBILITY
1497 pointer __get_pointer() _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001498 {return __is_long() ? __get_long_pointer() : __get_short_pointer();}
Howard Hinnanta6119a82011-05-29 19:57:12 +00001499 _LIBCPP_INLINE_VISIBILITY
1500 const_pointer __get_pointer() const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001501 {return __is_long() ? __get_long_pointer() : __get_short_pointer();}
1502
Howard Hinnanta6119a82011-05-29 19:57:12 +00001503 _LIBCPP_INLINE_VISIBILITY
1504 void __zero() _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001505 {
1506 size_type (&__a)[__n_words] = __r_.first().__r.__words;
1507 for (unsigned __i = 0; __i < __n_words; ++__i)
1508 __a[__i] = 0;
1509 }
1510
1511 template <size_type __a> static
Howard Hinnanta6119a82011-05-29 19:57:12 +00001512 _LIBCPP_INLINE_VISIBILITY
1513 size_type __align(size_type __s) _NOEXCEPT
1514 {return __s + (__a-1) & ~(__a-1);}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001515 enum {__alignment = 16};
Howard Hinnanta6119a82011-05-29 19:57:12 +00001516 static _LIBCPP_INLINE_VISIBILITY
1517 size_type __recommend(size_type __s) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001518 {return (__s < __min_cap ? __min_cap :
Howard Hinnanta6119a82011-05-29 19:57:12 +00001519 __align<sizeof(value_type) < __alignment ?
1520 __alignment/sizeof(value_type) : 1 > (__s+1)) - 1;}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001521
1522 void __init(const_pointer __s, size_type __sz, size_type __reserve);
1523 void __init(const_pointer __s, size_type __sz);
1524 void __init(size_type __n, value_type __c);
Howard Hinnant324bb032010-08-22 00:02:43 +00001525
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001526 template <class _InputIterator>
1527 typename enable_if
1528 <
1529 __is_input_iterator <_InputIterator>::value &&
1530 !__is_forward_iterator<_InputIterator>::value,
1531 void
1532 >::type
1533 __init(_InputIterator __first, _InputIterator __last);
1534
1535 template <class _ForwardIterator>
1536 typename enable_if
1537 <
1538 __is_forward_iterator<_ForwardIterator>::value,
1539 void
1540 >::type
1541 __init(_ForwardIterator __first, _ForwardIterator __last);
1542
1543 void __grow_by(size_type __old_cap, size_type __delta_cap, size_type __old_sz,
Howard Hinnant324bb032010-08-22 00:02:43 +00001544 size_type __n_copy, size_type __n_del, size_type __n_add = 0);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001545 void __grow_by_and_replace(size_type __old_cap, size_type __delta_cap, size_type __old_sz,
1546 size_type __n_copy, size_type __n_del,
1547 size_type __n_add, const_pointer __p_new_stuff);
1548
Howard Hinnant2d72b1e2010-12-17 14:46:43 +00001549 _LIBCPP_INLINE_VISIBILITY
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001550 void __erase_to_end(size_type __pos);
1551
Howard Hinnante32b5e22010-11-17 17:55:08 +00001552 _LIBCPP_INLINE_VISIBILITY
1553 void __copy_assign_alloc(const basic_string& __str)
1554 {__copy_assign_alloc(__str, integral_constant<bool,
1555 __alloc_traits::propagate_on_container_copy_assignment::value>());}
1556
1557 _LIBCPP_INLINE_VISIBILITY
1558 void __copy_assign_alloc(const basic_string& __str, true_type)
1559 {
1560 if (__alloc() != __str.__alloc())
1561 {
1562 clear();
1563 shrink_to_fit();
1564 }
1565 __alloc() = __str.__alloc();
1566 }
1567
1568 _LIBCPP_INLINE_VISIBILITY
Howard Hinnanta6119a82011-05-29 19:57:12 +00001569 void __copy_assign_alloc(const basic_string& __str, false_type) _NOEXCEPT
Howard Hinnante32b5e22010-11-17 17:55:08 +00001570 {}
1571
1572#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnant2d72b1e2010-12-17 14:46:43 +00001573 _LIBCPP_INLINE_VISIBILITY
Howard Hinnante32b5e22010-11-17 17:55:08 +00001574 void __move_assign(basic_string& __str, false_type);
Howard Hinnant2d72b1e2010-12-17 14:46:43 +00001575 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant53f7d4c2011-06-03 18:40:47 +00001576 void __move_assign(basic_string& __str, true_type)
1577 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value);
Howard Hinnante32b5e22010-11-17 17:55:08 +00001578#endif
1579
1580 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant53f7d4c2011-06-03 18:40:47 +00001581 static void __swap_alloc(allocator_type& __x, allocator_type& __y)
1582 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
1583 __is_nothrow_swappable<allocator_type>::value)
Howard Hinnante32b5e22010-11-17 17:55:08 +00001584 {__swap_alloc(__x, __y, integral_constant<bool,
1585 __alloc_traits::propagate_on_container_swap::value>());}
1586
1587 _LIBCPP_INLINE_VISIBILITY
Howard Hinnant53f7d4c2011-06-03 18:40:47 +00001588 static void __swap_alloc(allocator_type& __x, allocator_type& __y, true_type)
1589 _NOEXCEPT_(__is_nothrow_swappable<allocator_type>::value)
Howard Hinnante32b5e22010-11-17 17:55:08 +00001590 {
Howard Hinnant0949eed2011-06-30 21:18:19 +00001591 using _VSTD::swap;
Howard Hinnante32b5e22010-11-17 17:55:08 +00001592 swap(__x, __y);
1593 }
1594 _LIBCPP_INLINE_VISIBILITY
Howard Hinnanta6119a82011-05-29 19:57:12 +00001595 static void __swap_alloc(allocator_type& __x, allocator_type& __y, false_type) _NOEXCEPT
Howard Hinnante32b5e22010-11-17 17:55:08 +00001596 {}
1597
Howard Hinnant2d72b1e2010-12-17 14:46:43 +00001598 _LIBCPP_INLINE_VISIBILITY void __invalidate_all_iterators();
1599 _LIBCPP_INLINE_VISIBILITY void __invalidate_iterators_past(size_type);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001600
1601 friend basic_string operator+<>(const basic_string&, const basic_string&);
1602 friend basic_string operator+<>(const value_type*, const basic_string&);
1603 friend basic_string operator+<>(value_type, const basic_string&);
1604 friend basic_string operator+<>(const basic_string&, const value_type*);
1605 friend basic_string operator+<>(const basic_string&, value_type);
1606};
1607
1608template <class _CharT, class _Traits, class _Allocator>
1609#ifndef _LIBCPP_DEBUG
1610_LIBCPP_INLINE_VISIBILITY inline
1611#endif
1612void
1613basic_string<_CharT, _Traits, _Allocator>::__invalidate_all_iterators()
1614{
1615#ifdef _LIBCPP_DEBUG
1616 iterator::__remove_all(this);
1617 const_iterator::__remove_all(this);
Howard Hinnant324bb032010-08-22 00:02:43 +00001618#endif // _LIBCPP_DEBUG
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001619}
1620
1621template <class _CharT, class _Traits, class _Allocator>
1622#ifndef _LIBCPP_DEBUG
1623_LIBCPP_INLINE_VISIBILITY inline
1624#endif
1625void
1626basic_string<_CharT, _Traits, _Allocator>::__invalidate_iterators_past(size_type __pos)
1627{
1628#ifdef _LIBCPP_DEBUG
1629 const_iterator __beg = begin();
1630 if (__iterator_list_.first)
1631 {
1632 for (iterator* __p = __iterator_list_.first; __p;)
1633 {
1634 if (*__p - __beg > static_cast<difference_type>(__pos))
1635 {
1636 iterator* __n = __p;
1637 __p = __p->__next;
1638 __n->__remove_owner();
1639 }
1640 else
1641 __p = __p->__next;
1642 }
1643 }
1644 if (__iterator_list_.second)
1645 {
1646 for (const_iterator* __p = __iterator_list_.second; __p;)
1647 {
1648 if (*__p - __beg > static_cast<difference_type>(__pos))
1649 {
1650 const_iterator* __n = __p;
1651 __p = __p->__next;
1652 __n->__remove_owner();
1653 }
1654 else
1655 __p = __p->__next;
1656 }
1657 }
Howard Hinnant324bb032010-08-22 00:02:43 +00001658#endif // _LIBCPP_DEBUG
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001659}
1660
1661template <class _CharT, class _Traits, class _Allocator>
1662_LIBCPP_INLINE_VISIBILITY inline
Howard Hinnant53f7d4c2011-06-03 18:40:47 +00001663basic_string<_CharT, _Traits, _Allocator>::basic_string()
1664 _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001665{
1666 __zero();
1667}
1668
1669template <class _CharT, class _Traits, class _Allocator>
1670_LIBCPP_INLINE_VISIBILITY inline
1671basic_string<_CharT, _Traits, _Allocator>::basic_string(const allocator_type& __a)
1672 : __r_(__a)
1673{
1674 __zero();
1675}
1676
1677template <class _CharT, class _Traits, class _Allocator>
1678void
1679basic_string<_CharT, _Traits, _Allocator>::__init(const_pointer __s, size_type __sz, size_type __reserve)
1680{
1681 if (__reserve > max_size())
1682 this->__throw_length_error();
1683 pointer __p;
1684 if (__reserve < __min_cap)
1685 {
1686 __set_short_size(__sz);
1687 __p = __get_short_pointer();
1688 }
1689 else
1690 {
1691 size_type __cap = __recommend(__reserve);
Howard Hinnante32b5e22010-11-17 17:55:08 +00001692 __p = __alloc_traits::allocate(__alloc(), __cap+1);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001693 __set_long_pointer(__p);
1694 __set_long_cap(__cap+1);
1695 __set_long_size(__sz);
1696 }
1697 traits_type::copy(__p, __s, __sz);
1698 traits_type::assign(__p[__sz], value_type());
1699}
1700
1701template <class _CharT, class _Traits, class _Allocator>
1702void
1703basic_string<_CharT, _Traits, _Allocator>::__init(const_pointer __s, size_type __sz)
1704{
1705 if (__sz > max_size())
1706 this->__throw_length_error();
1707 pointer __p;
1708 if (__sz < __min_cap)
1709 {
1710 __set_short_size(__sz);
1711 __p = __get_short_pointer();
1712 }
1713 else
1714 {
1715 size_type __cap = __recommend(__sz);
Howard Hinnante32b5e22010-11-17 17:55:08 +00001716 __p = __alloc_traits::allocate(__alloc(), __cap+1);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001717 __set_long_pointer(__p);
1718 __set_long_cap(__cap+1);
1719 __set_long_size(__sz);
1720 }
1721 traits_type::copy(__p, __s, __sz);
1722 traits_type::assign(__p[__sz], value_type());
1723}
1724
1725template <class _CharT, class _Traits, class _Allocator>
1726_LIBCPP_INLINE_VISIBILITY inline
1727basic_string<_CharT, _Traits, _Allocator>::basic_string(const_pointer __s)
1728{
1729#ifdef _LIBCPP_DEBUG
1730 assert(__s != 0);
1731#endif
1732 __init(__s, traits_type::length(__s));
1733}
1734
1735template <class _CharT, class _Traits, class _Allocator>
1736_LIBCPP_INLINE_VISIBILITY inline
1737basic_string<_CharT, _Traits, _Allocator>::basic_string(const_pointer __s, const allocator_type& __a)
1738 : __r_(__a)
1739{
1740#ifdef _LIBCPP_DEBUG
1741 assert(__s != 0);
1742#endif
1743 __init(__s, traits_type::length(__s));
1744}
1745
1746template <class _CharT, class _Traits, class _Allocator>
1747_LIBCPP_INLINE_VISIBILITY inline
1748basic_string<_CharT, _Traits, _Allocator>::basic_string(const_pointer __s, size_type __n)
1749{
1750#ifdef _LIBCPP_DEBUG
1751 assert(__s != 0);
1752#endif
1753 __init(__s, __n);
1754}
1755
1756template <class _CharT, class _Traits, class _Allocator>
1757_LIBCPP_INLINE_VISIBILITY inline
1758basic_string<_CharT, _Traits, _Allocator>::basic_string(const_pointer __s, size_type __n, const allocator_type& __a)
1759 : __r_(__a)
1760{
1761#ifdef _LIBCPP_DEBUG
1762 assert(__s != 0);
1763#endif
1764 __init(__s, __n);
1765}
1766
1767template <class _CharT, class _Traits, class _Allocator>
1768basic_string<_CharT, _Traits, _Allocator>::basic_string(const basic_string& __str)
Howard Hinnante32b5e22010-11-17 17:55:08 +00001769 : __r_(__alloc_traits::select_on_container_copy_construction(__str.__alloc()))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001770{
1771 if (!__str.__is_long())
1772 __r_.first().__r = __str.__r_.first().__r;
1773 else
1774 __init(__str.__get_long_pointer(), __str.__get_long_size());
1775}
1776
1777template <class _CharT, class _Traits, class _Allocator>
1778basic_string<_CharT, _Traits, _Allocator>::basic_string(const basic_string& __str, const allocator_type& __a)
1779 : __r_(__a)
1780{
1781 if (!__str.__is_long())
1782 __r_.first().__r = __str.__r_.first().__r;
1783 else
1784 __init(__str.__get_long_pointer(), __str.__get_long_size());
1785}
1786
Howard Hinnant73d21a42010-09-04 23:28:19 +00001787#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001788
1789template <class _CharT, class _Traits, class _Allocator>
1790_LIBCPP_INLINE_VISIBILITY inline
Howard Hinnant53f7d4c2011-06-03 18:40:47 +00001791basic_string<_CharT, _Traits, _Allocator>::basic_string(basic_string&& __str)
1792 _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value)
Howard Hinnant0949eed2011-06-30 21:18:19 +00001793 : __r_(_VSTD::move(__str.__r_))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001794{
1795 __str.__zero();
1796#ifdef _LIBCPP_DEBUG
1797 __str.__invalidate_all_iterators();
1798#endif
1799}
1800
1801template <class _CharT, class _Traits, class _Allocator>
1802_LIBCPP_INLINE_VISIBILITY inline
1803basic_string<_CharT, _Traits, _Allocator>::basic_string(basic_string&& __str, const allocator_type& __a)
Howard Hinnante32b5e22010-11-17 17:55:08 +00001804 : __r_(__a)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001805{
Howard Hinnante32b5e22010-11-17 17:55:08 +00001806 if (__a == __str.__alloc() || !__str.__is_long())
1807 __r_.first().__r = __str.__r_.first().__r;
1808 else
1809 __init(__str.__get_long_pointer(), __str.__get_long_size());
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001810 __str.__zero();
1811#ifdef _LIBCPP_DEBUG
1812 __str.__invalidate_all_iterators();
1813#endif
1814}
1815
Howard Hinnant73d21a42010-09-04 23:28:19 +00001816#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001817
1818template <class _CharT, class _Traits, class _Allocator>
1819void
1820basic_string<_CharT, _Traits, _Allocator>::__init(size_type __n, value_type __c)
1821{
1822 if (__n > max_size())
1823 this->__throw_length_error();
1824 pointer __p;
1825 if (__n < __min_cap)
1826 {
1827 __set_short_size(__n);
1828 __p = __get_short_pointer();
1829 }
1830 else
1831 {
1832 size_type __cap = __recommend(__n);
Howard Hinnante32b5e22010-11-17 17:55:08 +00001833 __p = __alloc_traits::allocate(__alloc(), __cap+1);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001834 __set_long_pointer(__p);
1835 __set_long_cap(__cap+1);
1836 __set_long_size(__n);
1837 }
1838 traits_type::assign(__p, __n, __c);
1839 traits_type::assign(__p[__n], value_type());
1840}
1841
1842template <class _CharT, class _Traits, class _Allocator>
1843_LIBCPP_INLINE_VISIBILITY inline
1844basic_string<_CharT, _Traits, _Allocator>::basic_string(size_type __n, value_type __c)
1845{
1846 __init(__n, __c);
1847}
1848
1849template <class _CharT, class _Traits, class _Allocator>
1850_LIBCPP_INLINE_VISIBILITY inline
1851basic_string<_CharT, _Traits, _Allocator>::basic_string(size_type __n, value_type __c, const allocator_type& __a)
1852 : __r_(__a)
1853{
1854 __init(__n, __c);
1855}
1856
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001857template <class _CharT, class _Traits, class _Allocator>
1858basic_string<_CharT, _Traits, _Allocator>::basic_string(const basic_string& __str, size_type __pos, size_type __n,
1859 const allocator_type& __a)
1860 : __r_(__a)
1861{
1862 size_type __str_sz = __str.size();
1863 if (__pos > __str_sz)
1864 this->__throw_out_of_range();
Howard Hinnant0949eed2011-06-30 21:18:19 +00001865 __init(__str.data() + __pos, _VSTD::min(__n, __str_sz - __pos));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001866}
1867
1868template <class _CharT, class _Traits, class _Allocator>
1869template <class _InputIterator>
1870typename enable_if
1871<
1872 __is_input_iterator <_InputIterator>::value &&
1873 !__is_forward_iterator<_InputIterator>::value,
1874 void
1875>::type
1876basic_string<_CharT, _Traits, _Allocator>::__init(_InputIterator __first, _InputIterator __last)
1877{
1878 __zero();
1879#ifndef _LIBCPP_NO_EXCEPTIONS
1880 try
1881 {
Howard Hinnant324bb032010-08-22 00:02:43 +00001882#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001883 for (; __first != __last; ++__first)
1884 push_back(*__first);
1885#ifndef _LIBCPP_NO_EXCEPTIONS
1886 }
1887 catch (...)
1888 {
1889 if (__is_long())
Howard Hinnante32b5e22010-11-17 17:55:08 +00001890 __alloc_traits::deallocate(__alloc(), __get_long_pointer(), __get_long_cap());
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001891 throw;
1892 }
Howard Hinnant324bb032010-08-22 00:02:43 +00001893#endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001894}
1895
1896template <class _CharT, class _Traits, class _Allocator>
1897template <class _ForwardIterator>
1898typename enable_if
1899<
1900 __is_forward_iterator<_ForwardIterator>::value,
1901 void
1902>::type
1903basic_string<_CharT, _Traits, _Allocator>::__init(_ForwardIterator __first, _ForwardIterator __last)
1904{
Howard Hinnant0949eed2011-06-30 21:18:19 +00001905 size_type __sz = static_cast<size_type>(_VSTD::distance(__first, __last));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001906 if (__sz > max_size())
1907 this->__throw_length_error();
1908 pointer __p;
1909 if (__sz < __min_cap)
1910 {
1911 __set_short_size(__sz);
1912 __p = __get_short_pointer();
1913 }
1914 else
1915 {
1916 size_type __cap = __recommend(__sz);
Howard Hinnante32b5e22010-11-17 17:55:08 +00001917 __p = __alloc_traits::allocate(__alloc(), __cap+1);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001918 __set_long_pointer(__p);
1919 __set_long_cap(__cap+1);
1920 __set_long_size(__sz);
1921 }
1922 for (; __first != __last; ++__first, ++__p)
1923 traits_type::assign(*__p, *__first);
1924 traits_type::assign(*__p, value_type());
1925}
1926
1927template <class _CharT, class _Traits, class _Allocator>
1928template<class _InputIterator>
1929_LIBCPP_INLINE_VISIBILITY inline
1930basic_string<_CharT, _Traits, _Allocator>::basic_string(_InputIterator __first, _InputIterator __last)
1931{
1932 __init(__first, __last);
1933}
1934
1935template <class _CharT, class _Traits, class _Allocator>
1936template<class _InputIterator>
1937_LIBCPP_INLINE_VISIBILITY inline
1938basic_string<_CharT, _Traits, _Allocator>::basic_string(_InputIterator __first, _InputIterator __last,
1939 const allocator_type& __a)
1940 : __r_(__a)
1941{
1942 __init(__first, __last);
1943}
1944
1945template <class _CharT, class _Traits, class _Allocator>
1946_LIBCPP_INLINE_VISIBILITY inline
1947basic_string<_CharT, _Traits, _Allocator>::basic_string(initializer_list<value_type> __il)
1948{
1949 __init(__il.begin(), __il.end());
1950}
1951
1952template <class _CharT, class _Traits, class _Allocator>
1953_LIBCPP_INLINE_VISIBILITY inline
1954basic_string<_CharT, _Traits, _Allocator>::basic_string(initializer_list<value_type> __il, const allocator_type& __a)
1955 : __r_(__a)
1956{
1957 __init(__il.begin(), __il.end());
1958}
1959
1960template <class _CharT, class _Traits, class _Allocator>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001961basic_string<_CharT, _Traits, _Allocator>::~basic_string()
1962{
1963 __invalidate_all_iterators();
1964 if (__is_long())
Howard Hinnante32b5e22010-11-17 17:55:08 +00001965 __alloc_traits::deallocate(__alloc(), __get_long_pointer(), __get_long_cap());
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001966}
1967
1968template <class _CharT, class _Traits, class _Allocator>
1969void
1970basic_string<_CharT, _Traits, _Allocator>::__grow_by_and_replace
1971 (size_type __old_cap, size_type __delta_cap, size_type __old_sz,
1972 size_type __n_copy, size_type __n_del, size_type __n_add, const_pointer __p_new_stuff)
1973{
1974 size_type __ms = max_size();
1975 if (__delta_cap > __ms - __old_cap - 1)
1976 this->__throw_length_error();
1977 pointer __old_p = __get_pointer();
1978 size_type __cap = __old_cap < __ms / 2 - __alignment ?
Howard Hinnant0949eed2011-06-30 21:18:19 +00001979 __recommend(_VSTD::max(__old_cap + __delta_cap, 2 * __old_cap)) :
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001980 __ms - 1;
Howard Hinnante32b5e22010-11-17 17:55:08 +00001981 pointer __p = __alloc_traits::allocate(__alloc(), __cap+1);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001982 __invalidate_all_iterators();
1983 if (__n_copy != 0)
1984 traits_type::copy(__p, __old_p, __n_copy);
1985 if (__n_add != 0)
1986 traits_type::copy(__p + __n_copy, __p_new_stuff, __n_add);
1987 size_type __sec_cp_sz = __old_sz - __n_del - __n_copy;
1988 if (__sec_cp_sz != 0)
1989 traits_type::copy(__p + __n_copy + __n_add, __old_p + __n_copy + __n_del, __sec_cp_sz);
1990 if (__old_cap+1 != __min_cap)
Howard Hinnante32b5e22010-11-17 17:55:08 +00001991 __alloc_traits::deallocate(__alloc(), __old_p, __old_cap+1);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00001992 __set_long_pointer(__p);
1993 __set_long_cap(__cap+1);
1994 __old_sz = __n_copy + __n_add + __sec_cp_sz;
1995 __set_long_size(__old_sz);
1996 traits_type::assign(__p[__old_sz], value_type());
1997}
1998
1999template <class _CharT, class _Traits, class _Allocator>
2000void
2001basic_string<_CharT, _Traits, _Allocator>::__grow_by(size_type __old_cap, size_type __delta_cap, size_type __old_sz,
2002 size_type __n_copy, size_type __n_del, size_type __n_add)
2003{
2004 size_type __ms = max_size();
2005 if (__delta_cap > __ms - __old_cap - 1)
2006 this->__throw_length_error();
2007 pointer __old_p = __get_pointer();
2008 size_type __cap = __old_cap < __ms / 2 - __alignment ?
Howard Hinnant0949eed2011-06-30 21:18:19 +00002009 __recommend(_VSTD::max(__old_cap + __delta_cap, 2 * __old_cap)) :
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002010 __ms - 1;
Howard Hinnante32b5e22010-11-17 17:55:08 +00002011 pointer __p = __alloc_traits::allocate(__alloc(), __cap+1);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002012 __invalidate_all_iterators();
2013 if (__n_copy != 0)
2014 traits_type::copy(__p, __old_p, __n_copy);
2015 size_type __sec_cp_sz = __old_sz - __n_del - __n_copy;
2016 if (__sec_cp_sz != 0)
2017 traits_type::copy(__p + __n_copy + __n_add, __old_p + __n_copy + __n_del, __sec_cp_sz);
2018 if (__old_cap+1 != __min_cap)
Howard Hinnante32b5e22010-11-17 17:55:08 +00002019 __alloc_traits::deallocate(__alloc(), __old_p, __old_cap+1);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002020 __set_long_pointer(__p);
2021 __set_long_cap(__cap+1);
2022}
2023
2024// assign
2025
2026template <class _CharT, class _Traits, class _Allocator>
2027basic_string<_CharT, _Traits, _Allocator>&
2028basic_string<_CharT, _Traits, _Allocator>::assign(const_pointer __s, size_type __n)
2029{
2030#ifdef _LIBCPP_DEBUG
2031 assert(__s != 0);
2032#endif
2033 size_type __cap = capacity();
2034 if (__cap >= __n)
2035 {
2036 pointer __p = __get_pointer();
2037 traits_type::move(__p, __s, __n);
2038 traits_type::assign(__p[__n], value_type());
2039 __set_size(__n);
2040 __invalidate_iterators_past(__n);
2041 }
2042 else
2043 {
2044 size_type __sz = size();
2045 __grow_by_and_replace(__cap, __n - __cap, __sz, 0, __sz, __n, __s);
2046 }
2047 return *this;
2048}
2049
2050template <class _CharT, class _Traits, class _Allocator>
2051basic_string<_CharT, _Traits, _Allocator>&
2052basic_string<_CharT, _Traits, _Allocator>::assign(size_type __n, value_type __c)
2053{
2054 size_type __cap = capacity();
2055 if (__cap < __n)
2056 {
2057 size_type __sz = size();
2058 __grow_by(__cap, __n - __cap, __sz, 0, __sz);
2059 }
2060 else
2061 __invalidate_iterators_past(__n);
2062 pointer __p = __get_pointer();
2063 traits_type::assign(__p, __n, __c);
2064 traits_type::assign(__p[__n], value_type());
2065 __set_size(__n);
2066 return *this;
2067}
2068
2069template <class _CharT, class _Traits, class _Allocator>
2070basic_string<_CharT, _Traits, _Allocator>&
2071basic_string<_CharT, _Traits, _Allocator>::operator=(value_type __c)
2072{
2073 pointer __p;
2074 if (__is_long())
2075 {
2076 __p = __get_long_pointer();
2077 __set_long_size(1);
2078 }
2079 else
2080 {
2081 __p = __get_short_pointer();
2082 __set_short_size(1);
2083 }
2084 traits_type::assign(*__p, __c);
2085 traits_type::assign(*++__p, value_type());
2086 __invalidate_iterators_past(1);
2087 return *this;
2088}
2089
2090template <class _CharT, class _Traits, class _Allocator>
Howard Hinnante32b5e22010-11-17 17:55:08 +00002091basic_string<_CharT, _Traits, _Allocator>&
2092basic_string<_CharT, _Traits, _Allocator>::operator=(const basic_string& __str)
2093{
2094 if (this != &__str)
2095 {
2096 __copy_assign_alloc(__str);
2097 assign(__str);
2098 }
2099 return *this;
2100}
2101
2102#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
2103
2104template <class _CharT, class _Traits, class _Allocator>
2105_LIBCPP_INLINE_VISIBILITY inline
2106void
2107basic_string<_CharT, _Traits, _Allocator>::__move_assign(basic_string& __str, false_type)
2108{
2109 if (__alloc() != __str.__alloc())
2110 assign(__str);
2111 else
2112 __move_assign(__str, true_type());
2113}
2114
2115template <class _CharT, class _Traits, class _Allocator>
2116_LIBCPP_INLINE_VISIBILITY inline
2117void
2118basic_string<_CharT, _Traits, _Allocator>::__move_assign(basic_string& __str, true_type)
Howard Hinnant53f7d4c2011-06-03 18:40:47 +00002119 _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value)
Howard Hinnante32b5e22010-11-17 17:55:08 +00002120{
2121 clear();
2122 shrink_to_fit();
Howard Hinnant0949eed2011-06-30 21:18:19 +00002123 __r_ = _VSTD::move(__str.__r_);
Howard Hinnante32b5e22010-11-17 17:55:08 +00002124 __str.__zero();
2125}
2126
2127template <class _CharT, class _Traits, class _Allocator>
2128_LIBCPP_INLINE_VISIBILITY inline
2129basic_string<_CharT, _Traits, _Allocator>&
2130basic_string<_CharT, _Traits, _Allocator>::operator=(basic_string&& __str)
Howard Hinnant53f7d4c2011-06-03 18:40:47 +00002131 _NOEXCEPT_(__alloc_traits::propagate_on_container_move_assignment::value &&
2132 is_nothrow_move_assignable<allocator_type>::value)
Howard Hinnante32b5e22010-11-17 17:55:08 +00002133{
2134 __move_assign(__str, integral_constant<bool,
2135 __alloc_traits::propagate_on_container_move_assignment::value>());
2136 return *this;
2137}
2138
2139#endif
2140
2141template <class _CharT, class _Traits, class _Allocator>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002142template<class _InputIterator>
2143typename enable_if
2144<
2145 __is_input_iterator <_InputIterator>::value &&
2146 !__is_forward_iterator<_InputIterator>::value,
2147 basic_string<_CharT, _Traits, _Allocator>&
2148>::type
2149basic_string<_CharT, _Traits, _Allocator>::assign(_InputIterator __first, _InputIterator __last)
2150{
2151 clear();
2152 for (; __first != __last; ++__first)
2153 push_back(*__first);
2154}
2155
2156template <class _CharT, class _Traits, class _Allocator>
2157template<class _ForwardIterator>
2158typename enable_if
2159<
2160 __is_forward_iterator<_ForwardIterator>::value,
2161 basic_string<_CharT, _Traits, _Allocator>&
2162>::type
2163basic_string<_CharT, _Traits, _Allocator>::assign(_ForwardIterator __first, _ForwardIterator __last)
2164{
Howard Hinnant0949eed2011-06-30 21:18:19 +00002165 size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002166 size_type __cap = capacity();
2167 if (__cap < __n)
2168 {
2169 size_type __sz = size();
2170 __grow_by(__cap, __n - __cap, __sz, 0, __sz);
2171 }
2172 else
2173 __invalidate_iterators_past(__n);
2174 pointer __p = __get_pointer();
2175 for (; __first != __last; ++__first, ++__p)
2176 traits_type::assign(*__p, *__first);
2177 traits_type::assign(*__p, value_type());
2178 __set_size(__n);
2179 return *this;
2180}
2181
2182template <class _CharT, class _Traits, class _Allocator>
2183_LIBCPP_INLINE_VISIBILITY inline
2184basic_string<_CharT, _Traits, _Allocator>&
2185basic_string<_CharT, _Traits, _Allocator>::assign(const basic_string& __str)
2186{
2187 return assign(__str.data(), __str.size());
2188}
2189
2190template <class _CharT, class _Traits, class _Allocator>
2191basic_string<_CharT, _Traits, _Allocator>&
2192basic_string<_CharT, _Traits, _Allocator>::assign(const basic_string& __str, size_type __pos, size_type __n)
2193{
2194 size_type __sz = __str.size();
2195 if (__pos > __sz)
2196 this->__throw_out_of_range();
Howard Hinnant0949eed2011-06-30 21:18:19 +00002197 return assign(__str.data() + __pos, _VSTD::min(__n, __sz - __pos));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002198}
2199
2200template <class _CharT, class _Traits, class _Allocator>
2201basic_string<_CharT, _Traits, _Allocator>&
2202basic_string<_CharT, _Traits, _Allocator>::assign(const_pointer __s)
2203{
2204#ifdef _LIBCPP_DEBUG
2205 assert(__s != 0);
2206#endif
2207 return assign(__s, traits_type::length(__s));
2208}
2209
2210// append
2211
2212template <class _CharT, class _Traits, class _Allocator>
2213basic_string<_CharT, _Traits, _Allocator>&
2214basic_string<_CharT, _Traits, _Allocator>::append(const_pointer __s, size_type __n)
2215{
2216#ifdef _LIBCPP_DEBUG
2217 assert(__s != 0);
2218#endif
2219 size_type __cap = capacity();
2220 size_type __sz = size();
2221 if (__cap - __sz >= __n)
2222 {
2223 if (__n)
2224 {
2225 pointer __p = __get_pointer();
2226 traits_type::copy(__p + __sz, __s, __n);
2227 __sz += __n;
2228 __set_size(__sz);
2229 traits_type::assign(__p[__sz], value_type());
2230 }
2231 }
2232 else
2233 __grow_by_and_replace(__cap, __sz + __n - __cap, __sz, __sz, 0, __n, __s);
2234 return *this;
2235}
2236
2237template <class _CharT, class _Traits, class _Allocator>
2238basic_string<_CharT, _Traits, _Allocator>&
2239basic_string<_CharT, _Traits, _Allocator>::append(size_type __n, value_type __c)
2240{
2241 if (__n)
2242 {
2243 size_type __cap = capacity();
2244 size_type __sz = size();
2245 if (__cap - __sz < __n)
2246 __grow_by(__cap, __sz + __n - __cap, __sz, __sz, 0);
2247 pointer __p = __get_pointer();
2248 traits_type::assign(__p + __sz, __n, __c);
2249 __sz += __n;
2250 __set_size(__sz);
2251 traits_type::assign(__p[__sz], value_type());
2252 }
2253 return *this;
2254}
2255
2256template <class _CharT, class _Traits, class _Allocator>
2257void
2258basic_string<_CharT, _Traits, _Allocator>::push_back(value_type __c)
2259{
2260 size_type __cap = capacity();
2261 size_type __sz = size();
2262 if (__sz == __cap)
2263 __grow_by(__cap, 1, __sz, __sz, 0);
2264 pointer __p = __get_pointer() + __sz;
2265 traits_type::assign(*__p, __c);
2266 traits_type::assign(*++__p, value_type());
2267 __set_size(__sz+1);
2268}
2269
2270template <class _CharT, class _Traits, class _Allocator>
2271template<class _InputIterator>
2272typename enable_if
2273<
2274 __is_input_iterator <_InputIterator>::value &&
2275 !__is_forward_iterator<_InputIterator>::value,
2276 basic_string<_CharT, _Traits, _Allocator>&
2277>::type
2278basic_string<_CharT, _Traits, _Allocator>::append(_InputIterator __first, _InputIterator __last)
2279{
2280 for (; __first != __last; ++__first)
2281 push_back(*__first);
2282 return *this;
2283}
2284
2285template <class _CharT, class _Traits, class _Allocator>
2286template<class _ForwardIterator>
2287typename enable_if
2288<
2289 __is_forward_iterator<_ForwardIterator>::value,
2290 basic_string<_CharT, _Traits, _Allocator>&
2291>::type
2292basic_string<_CharT, _Traits, _Allocator>::append(_ForwardIterator __first, _ForwardIterator __last)
2293{
2294 size_type __sz = size();
2295 size_type __cap = capacity();
Howard Hinnant0949eed2011-06-30 21:18:19 +00002296 size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002297 if (__n)
2298 {
2299 if (__cap - __sz < __n)
2300 __grow_by(__cap, __sz + __n - __cap, __sz, __sz, 0);
2301 pointer __p = __get_pointer() + __sz;
2302 for (; __first != __last; ++__p, ++__first)
2303 traits_type::assign(*__p, *__first);
2304 traits_type::assign(*__p, value_type());
2305 __set_size(__sz + __n);
2306 }
2307 return *this;
2308}
2309
2310template <class _CharT, class _Traits, class _Allocator>
2311_LIBCPP_INLINE_VISIBILITY inline
2312basic_string<_CharT, _Traits, _Allocator>&
2313basic_string<_CharT, _Traits, _Allocator>::append(const basic_string& __str)
2314{
2315 return append(__str.data(), __str.size());
2316}
2317
2318template <class _CharT, class _Traits, class _Allocator>
2319basic_string<_CharT, _Traits, _Allocator>&
2320basic_string<_CharT, _Traits, _Allocator>::append(const basic_string& __str, size_type __pos, size_type __n)
2321{
2322 size_type __sz = __str.size();
2323 if (__pos > __sz)
2324 this->__throw_out_of_range();
Howard Hinnant0949eed2011-06-30 21:18:19 +00002325 return append(__str.data() + __pos, _VSTD::min(__n, __sz - __pos));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002326}
2327
2328template <class _CharT, class _Traits, class _Allocator>
2329basic_string<_CharT, _Traits, _Allocator>&
2330basic_string<_CharT, _Traits, _Allocator>::append(const_pointer __s)
2331{
2332#ifdef _LIBCPP_DEBUG
2333 assert(__s != 0);
2334#endif
2335 return append(__s, traits_type::length(__s));
2336}
2337
2338// insert
2339
2340template <class _CharT, class _Traits, class _Allocator>
2341basic_string<_CharT, _Traits, _Allocator>&
2342basic_string<_CharT, _Traits, _Allocator>::insert(size_type __pos, const_pointer __s, size_type __n)
2343{
2344#ifdef _LIBCPP_DEBUG
2345 assert(__s != 0);
2346#endif
2347 size_type __sz = size();
2348 if (__pos > __sz)
2349 this->__throw_out_of_range();
2350 size_type __cap = capacity();
2351 if (__cap - __sz >= __n)
2352 {
2353 if (__n)
2354 {
2355 pointer __p = __get_pointer();
2356 size_type __n_move = __sz - __pos;
2357 if (__n_move != 0)
2358 {
2359 if (__p + __pos <= __s && __s < __p + __sz)
2360 __s += __n;
2361 traits_type::move(__p + __pos + __n, __p + __pos, __n_move);
2362 }
2363 traits_type::move(__p + __pos, __s, __n);
2364 __sz += __n;
2365 __set_size(__sz);
2366 traits_type::assign(__p[__sz], value_type());
2367 }
2368 }
2369 else
2370 __grow_by_and_replace(__cap, __sz + __n - __cap, __sz, __pos, 0, __n, __s);
2371 return *this;
2372}
2373
2374template <class _CharT, class _Traits, class _Allocator>
2375basic_string<_CharT, _Traits, _Allocator>&
2376basic_string<_CharT, _Traits, _Allocator>::insert(size_type __pos, size_type __n, value_type __c)
2377{
2378 size_type __sz = size();
2379 if (__pos > __sz)
2380 this->__throw_out_of_range();
2381 if (__n)
2382 {
2383 size_type __cap = capacity();
2384 pointer __p;
2385 if (__cap - __sz >= __n)
2386 {
2387 __p = __get_pointer();
2388 size_type __n_move = __sz - __pos;
2389 if (__n_move != 0)
2390 traits_type::move(__p + __pos + __n, __p + __pos, __n_move);
2391 }
2392 else
2393 {
2394 __grow_by(__cap, __sz + __n - __cap, __sz, __pos, 0, __n);
2395 __p = __get_long_pointer();
2396 }
2397 traits_type::assign(__p + __pos, __n, __c);
2398 __sz += __n;
2399 __set_size(__sz);
2400 traits_type::assign(__p[__sz], value_type());
2401 }
2402 return *this;
2403}
2404
2405template <class _CharT, class _Traits, class _Allocator>
2406template<class _InputIterator>
2407typename enable_if
2408<
2409 __is_input_iterator <_InputIterator>::value &&
2410 !__is_forward_iterator<_InputIterator>::value,
2411 typename basic_string<_CharT, _Traits, _Allocator>::iterator
2412>::type
2413basic_string<_CharT, _Traits, _Allocator>::insert(const_iterator __pos, _InputIterator __first, _InputIterator __last)
2414{
2415 size_type __old_sz = size();
2416 difference_type __ip = __pos - begin();
2417 for (; __first != __last; ++__first)
2418 push_back(*__first);
2419 pointer __p = __get_pointer();
Howard Hinnant0949eed2011-06-30 21:18:19 +00002420 _VSTD::rotate(__p + __ip, __p + __old_sz, __p + size());
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002421 return iterator(__p + __ip);
2422}
2423
2424template <class _CharT, class _Traits, class _Allocator>
2425template<class _ForwardIterator>
2426typename enable_if
2427<
2428 __is_forward_iterator<_ForwardIterator>::value,
2429 typename basic_string<_CharT, _Traits, _Allocator>::iterator
2430>::type
2431basic_string<_CharT, _Traits, _Allocator>::insert(const_iterator __pos, _ForwardIterator __first, _ForwardIterator __last)
2432{
2433 size_type __ip = static_cast<size_type>(__pos - begin());
2434 size_type __sz = size();
2435 size_type __cap = capacity();
Howard Hinnant0949eed2011-06-30 21:18:19 +00002436 size_type __n = static_cast<size_type>(_VSTD::distance(__first, __last));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002437 if (__n)
2438 {
2439 pointer __p;
2440 if (__cap - __sz >= __n)
2441 {
2442 __p = __get_pointer();
2443 size_type __n_move = __sz - __ip;
2444 if (__n_move != 0)
2445 traits_type::move(__p + __ip + __n, __p + __ip, __n_move);
2446 }
2447 else
2448 {
2449 __grow_by(__cap, __sz + __n - __cap, __sz, __ip, 0, __n);
2450 __p = __get_long_pointer();
2451 }
2452 __sz += __n;
2453 __set_size(__sz);
2454 traits_type::assign(__p[__sz], value_type());
2455 for (__p += __ip; __first != __last; ++__p, ++__first)
2456 traits_type::assign(*__p, *__first);
2457 }
2458 return begin() + __ip;
2459}
2460
2461template <class _CharT, class _Traits, class _Allocator>
2462_LIBCPP_INLINE_VISIBILITY inline
2463basic_string<_CharT, _Traits, _Allocator>&
2464basic_string<_CharT, _Traits, _Allocator>::insert(size_type __pos1, const basic_string& __str)
2465{
2466 return insert(__pos1, __str.data(), __str.size());
2467}
2468
2469template <class _CharT, class _Traits, class _Allocator>
2470basic_string<_CharT, _Traits, _Allocator>&
2471basic_string<_CharT, _Traits, _Allocator>::insert(size_type __pos1, const basic_string& __str,
2472 size_type __pos2, size_type __n)
2473{
2474 size_type __str_sz = __str.size();
2475 if (__pos2 > __str_sz)
2476 this->__throw_out_of_range();
Howard Hinnant0949eed2011-06-30 21:18:19 +00002477 return insert(__pos1, __str.data() + __pos2, _VSTD::min(__n, __str_sz - __pos2));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002478}
2479
2480template <class _CharT, class _Traits, class _Allocator>
2481basic_string<_CharT, _Traits, _Allocator>&
2482basic_string<_CharT, _Traits, _Allocator>::insert(size_type __pos, const_pointer __s)
2483{
2484#ifdef _LIBCPP_DEBUG
2485 assert(__s != 0);
2486#endif
2487 return insert(__pos, __s, traits_type::length(__s));
2488}
2489
2490template <class _CharT, class _Traits, class _Allocator>
2491typename basic_string<_CharT, _Traits, _Allocator>::iterator
2492basic_string<_CharT, _Traits, _Allocator>::insert(const_iterator __pos, value_type __c)
2493{
2494 size_type __ip = static_cast<size_type>(__pos - begin());
2495 size_type __sz = size();
2496 size_type __cap = capacity();
2497 pointer __p;
2498 if (__cap == __sz)
2499 {
2500 __grow_by(__cap, 1, __sz, __ip, 0, 1);
2501 __p = __get_long_pointer();
2502 }
2503 else
2504 {
2505 __p = __get_pointer();
2506 size_type __n_move = __sz - __ip;
2507 if (__n_move != 0)
2508 traits_type::move(__p + __ip + 1, __p + __ip, __n_move);
2509 }
2510 traits_type::assign(__p[__ip], __c);
2511 traits_type::assign(__p[++__sz], value_type());
2512 __set_size(__sz);
2513 return begin() + static_cast<difference_type>(__ip);
2514}
2515
2516template <class _CharT, class _Traits, class _Allocator>
2517_LIBCPP_INLINE_VISIBILITY inline
2518typename basic_string<_CharT, _Traits, _Allocator>::iterator
2519basic_string<_CharT, _Traits, _Allocator>::insert(const_iterator __pos, size_type __n, value_type __c)
2520{
2521 difference_type __p = __pos - begin();
2522 insert(static_cast<size_type>(__p), __n, __c);
2523 return begin() + __p;
2524}
2525
2526// replace
2527
2528template <class _CharT, class _Traits, class _Allocator>
2529basic_string<_CharT, _Traits, _Allocator>&
2530basic_string<_CharT, _Traits, _Allocator>::replace(size_type __pos, size_type __n1, const_pointer __s, size_type __n2)
2531{
2532#ifdef _LIBCPP_DEBUG
2533 assert(__s != 0);
2534#endif
2535 size_type __sz = size();
2536 if (__pos > __sz)
2537 this->__throw_out_of_range();
Howard Hinnant0949eed2011-06-30 21:18:19 +00002538 __n1 = _VSTD::min(__n1, __sz - __pos);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002539 size_type __cap = capacity();
2540 if (__cap - __sz + __n1 >= __n2)
2541 {
2542 pointer __p = __get_pointer();
2543 if (__n1 != __n2)
2544 {
2545 size_type __n_move = __sz - __pos - __n1;
2546 if (__n_move != 0)
2547 {
2548 if (__n1 > __n2)
2549 {
2550 traits_type::move(__p + __pos, __s, __n2);
2551 traits_type::move(__p + __pos + __n2, __p + __pos + __n1, __n_move);
2552 goto __finish;
2553 }
2554 if (__p + __pos < __s && __s < __p + __sz)
2555 {
2556 if (__p + __pos + __n1 <= __s)
2557 __s += __n2 - __n1;
2558 else // __p + __pos < __s < __p + __pos + __n1
2559 {
2560 traits_type::move(__p + __pos, __s, __n1);
2561 __pos += __n1;
2562 __s += __n2;
2563 __n2 -= __n1;
2564 __n1 = 0;
2565 }
2566 }
2567 traits_type::move(__p + __pos + __n2, __p + __pos + __n1, __n_move);
2568 }
2569 }
2570 traits_type::move(__p + __pos, __s, __n2);
2571__finish:
2572 __sz += __n2 - __n1;
2573 __set_size(__sz);
2574 __invalidate_iterators_past(__sz);
2575 traits_type::assign(__p[__sz], value_type());
2576 }
2577 else
2578 __grow_by_and_replace(__cap, __sz - __n1 + __n2 - __cap, __sz, __pos, __n1, __n2, __s);
2579 return *this;
2580}
2581
2582template <class _CharT, class _Traits, class _Allocator>
2583basic_string<_CharT, _Traits, _Allocator>&
2584basic_string<_CharT, _Traits, _Allocator>::replace(size_type __pos, size_type __n1, size_type __n2, value_type __c)
2585{
2586 size_type __sz = size();
2587 if (__pos > __sz)
2588 this->__throw_out_of_range();
Howard Hinnant0949eed2011-06-30 21:18:19 +00002589 __n1 = _VSTD::min(__n1, __sz - __pos);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002590 size_type __cap = capacity();
2591 pointer __p;
2592 if (__cap - __sz + __n1 >= __n2)
2593 {
2594 __p = __get_pointer();
2595 if (__n1 != __n2)
2596 {
2597 size_type __n_move = __sz - __pos - __n1;
2598 if (__n_move != 0)
2599 traits_type::move(__p + __pos + __n2, __p + __pos + __n1, __n_move);
2600 }
2601 }
2602 else
2603 {
2604 __grow_by(__cap, __sz - __n1 + __n2 - __cap, __sz, __pos, __n1, __n2);
2605 __p = __get_long_pointer();
2606 }
2607 traits_type::assign(__p + __pos, __n2, __c);
2608 __sz += __n2 - __n1;
2609 __set_size(__sz);
2610 __invalidate_iterators_past(__sz);
2611 traits_type::assign(__p[__sz], value_type());
2612 return *this;
2613}
2614
2615template <class _CharT, class _Traits, class _Allocator>
2616template<class _InputIterator>
2617typename enable_if
2618<
2619 __is_input_iterator<_InputIterator>::value,
2620 basic_string<_CharT, _Traits, _Allocator>&
2621>::type
Howard Hinnant7b2cb482010-11-17 21:11:40 +00002622basic_string<_CharT, _Traits, _Allocator>::replace(const_iterator __i1, const_iterator __i2,
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002623 _InputIterator __j1, _InputIterator __j2)
2624{
2625 for (; true; ++__i1, ++__j1)
2626 {
2627 if (__i1 == __i2)
2628 {
2629 if (__j1 != __j2)
2630 insert(__i1, __j1, __j2);
2631 break;
2632 }
2633 if (__j1 == __j2)
2634 {
2635 erase(__i1, __i2);
2636 break;
2637 }
Howard Hinnant7b2cb482010-11-17 21:11:40 +00002638 traits_type::assign(const_cast<value_type&>(*__i1), *__j1);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002639 }
2640 return *this;
2641}
2642
2643template <class _CharT, class _Traits, class _Allocator>
2644_LIBCPP_INLINE_VISIBILITY inline
2645basic_string<_CharT, _Traits, _Allocator>&
2646basic_string<_CharT, _Traits, _Allocator>::replace(size_type __pos1, size_type __n1, const basic_string& __str)
2647{
2648 return replace(__pos1, __n1, __str.data(), __str.size());
2649}
2650
2651template <class _CharT, class _Traits, class _Allocator>
2652basic_string<_CharT, _Traits, _Allocator>&
2653basic_string<_CharT, _Traits, _Allocator>::replace(size_type __pos1, size_type __n1, const basic_string& __str,
2654 size_type __pos2, size_type __n2)
2655{
2656 size_type __str_sz = __str.size();
2657 if (__pos2 > __str_sz)
2658 this->__throw_out_of_range();
Howard Hinnant0949eed2011-06-30 21:18:19 +00002659 return replace(__pos1, __n1, __str.data() + __pos2, _VSTD::min(__n2, __str_sz - __pos2));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002660}
2661
2662template <class _CharT, class _Traits, class _Allocator>
2663basic_string<_CharT, _Traits, _Allocator>&
2664basic_string<_CharT, _Traits, _Allocator>::replace(size_type __pos, size_type __n1, const_pointer __s)
2665{
2666#ifdef _LIBCPP_DEBUG
2667 assert(__s != 0);
2668#endif
2669 return replace(__pos, __n1, __s, traits_type::length(__s));
2670}
2671
2672template <class _CharT, class _Traits, class _Allocator>
2673_LIBCPP_INLINE_VISIBILITY inline
2674basic_string<_CharT, _Traits, _Allocator>&
Howard Hinnant7b2cb482010-11-17 21:11:40 +00002675basic_string<_CharT, _Traits, _Allocator>::replace(const_iterator __i1, const_iterator __i2, const basic_string& __str)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002676{
2677 return replace(static_cast<size_type>(__i1 - begin()), static_cast<size_type>(__i2 - __i1),
2678 __str.data(), __str.size());
2679}
2680
2681template <class _CharT, class _Traits, class _Allocator>
2682_LIBCPP_INLINE_VISIBILITY inline
2683basic_string<_CharT, _Traits, _Allocator>&
Howard Hinnant7b2cb482010-11-17 21:11:40 +00002684basic_string<_CharT, _Traits, _Allocator>::replace(const_iterator __i1, const_iterator __i2, const_pointer __s, size_type __n)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002685{
2686 return replace(static_cast<size_type>(__i1 - begin()), static_cast<size_type>(__i2 - __i1), __s, __n);
2687}
2688
2689template <class _CharT, class _Traits, class _Allocator>
2690_LIBCPP_INLINE_VISIBILITY inline
2691basic_string<_CharT, _Traits, _Allocator>&
Howard Hinnant7b2cb482010-11-17 21:11:40 +00002692basic_string<_CharT, _Traits, _Allocator>::replace(const_iterator __i1, const_iterator __i2, const_pointer __s)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002693{
2694 return replace(static_cast<size_type>(__i1 - begin()), static_cast<size_type>(__i2 - __i1), __s);
2695}
2696
2697template <class _CharT, class _Traits, class _Allocator>
2698_LIBCPP_INLINE_VISIBILITY inline
2699basic_string<_CharT, _Traits, _Allocator>&
Howard Hinnant7b2cb482010-11-17 21:11:40 +00002700basic_string<_CharT, _Traits, _Allocator>::replace(const_iterator __i1, const_iterator __i2, size_type __n, value_type __c)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002701{
2702 return replace(static_cast<size_type>(__i1 - begin()), static_cast<size_type>(__i2 - __i1), __n, __c);
2703}
2704
2705// erase
2706
2707template <class _CharT, class _Traits, class _Allocator>
2708basic_string<_CharT, _Traits, _Allocator>&
2709basic_string<_CharT, _Traits, _Allocator>::erase(size_type __pos, size_type __n)
2710{
2711 size_type __sz = size();
2712 if (__pos > __sz)
2713 this->__throw_out_of_range();
2714 if (__n)
2715 {
2716 pointer __p = __get_pointer();
Howard Hinnant0949eed2011-06-30 21:18:19 +00002717 __n = _VSTD::min(__n, __sz - __pos);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002718 size_type __n_move = __sz - __pos - __n;
2719 if (__n_move != 0)
2720 traits_type::move(__p + __pos, __p + __pos + __n, __n_move);
2721 __sz -= __n;
2722 __set_size(__sz);
2723 __invalidate_iterators_past(__sz);
2724 traits_type::assign(__p[__sz], value_type());
2725 }
2726 return *this;
2727}
2728
2729template <class _CharT, class _Traits, class _Allocator>
2730_LIBCPP_INLINE_VISIBILITY inline
2731typename basic_string<_CharT, _Traits, _Allocator>::iterator
2732basic_string<_CharT, _Traits, _Allocator>::erase(const_iterator __pos)
2733{
2734 iterator __b = begin();
2735 size_type __r = static_cast<size_type>(__pos - __b);
2736 erase(__r, 1);
2737 return __b + __r;
2738}
2739
2740template <class _CharT, class _Traits, class _Allocator>
2741_LIBCPP_INLINE_VISIBILITY inline
2742typename basic_string<_CharT, _Traits, _Allocator>::iterator
2743basic_string<_CharT, _Traits, _Allocator>::erase(const_iterator __first, const_iterator __last)
2744{
2745 iterator __b = begin();
2746 size_type __r = static_cast<size_type>(__first - __b);
2747 erase(__r, static_cast<size_type>(__last - __first));
2748 return __b + __r;
2749}
2750
2751template <class _CharT, class _Traits, class _Allocator>
2752_LIBCPP_INLINE_VISIBILITY inline
2753void
2754basic_string<_CharT, _Traits, _Allocator>::pop_back()
2755{
2756#ifdef _LIBCPP_DEBUG
2757 assert(!empty());
2758#endif
2759 size_type __sz;
2760 if (__is_long())
2761 {
2762 __sz = __get_long_size() - 1;
2763 __set_long_size(__sz);
2764 traits_type::assign(*(__get_long_pointer() + __sz), value_type());
2765 }
2766 else
2767 {
2768 __sz = __get_short_size() - 1;
2769 __set_short_size(__sz);
2770 traits_type::assign(*(__get_short_pointer() + __sz), value_type());
2771 }
2772 __invalidate_iterators_past(__sz);
2773}
2774
2775template <class _CharT, class _Traits, class _Allocator>
2776_LIBCPP_INLINE_VISIBILITY inline
2777void
Howard Hinnanta6119a82011-05-29 19:57:12 +00002778basic_string<_CharT, _Traits, _Allocator>::clear() _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002779{
2780 __invalidate_all_iterators();
2781 if (__is_long())
2782 {
2783 traits_type::assign(*__get_long_pointer(), value_type());
2784 __set_long_size(0);
2785 }
2786 else
2787 {
2788 traits_type::assign(*__get_short_pointer(), value_type());
2789 __set_short_size(0);
2790 }
2791}
2792
2793template <class _CharT, class _Traits, class _Allocator>
2794_LIBCPP_INLINE_VISIBILITY inline
2795void
2796basic_string<_CharT, _Traits, _Allocator>::__erase_to_end(size_type __pos)
2797{
2798 if (__is_long())
2799 {
2800 traits_type::assign(*(__get_long_pointer() + __pos), value_type());
2801 __set_long_size(__pos);
2802 }
2803 else
2804 {
2805 traits_type::assign(*(__get_short_pointer() + __pos), value_type());
2806 __set_short_size(__pos);
2807 }
2808 __invalidate_iterators_past(__pos);
2809}
2810
2811template <class _CharT, class _Traits, class _Allocator>
2812void
2813basic_string<_CharT, _Traits, _Allocator>::resize(size_type __n, value_type __c)
2814{
2815 size_type __sz = size();
2816 if (__n > __sz)
2817 append(__n - __sz, __c);
2818 else
2819 __erase_to_end(__n);
2820}
2821
2822template <class _CharT, class _Traits, class _Allocator>
2823_LIBCPP_INLINE_VISIBILITY inline
2824typename basic_string<_CharT, _Traits, _Allocator>::size_type
Howard Hinnanta6119a82011-05-29 19:57:12 +00002825basic_string<_CharT, _Traits, _Allocator>::max_size() const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002826{
Howard Hinnante32b5e22010-11-17 17:55:08 +00002827 size_type __m = __alloc_traits::max_size(__alloc());
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002828#if _LIBCPP_BIG_ENDIAN
2829 return (__m <= ~__long_mask ? __m : __m/2) - 1;
2830#else
2831 return __m - 1;
2832#endif
2833}
2834
2835template <class _CharT, class _Traits, class _Allocator>
2836void
2837basic_string<_CharT, _Traits, _Allocator>::reserve(size_type __res_arg)
2838{
2839 if (__res_arg > max_size())
2840 this->__throw_length_error();
2841 size_type __cap = capacity();
2842 size_type __sz = size();
Howard Hinnant0949eed2011-06-30 21:18:19 +00002843 __res_arg = _VSTD::max(__res_arg, __sz);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002844 __res_arg = __recommend(__res_arg);
2845 if (__res_arg != __cap)
2846 {
2847 pointer __new_data, __p;
2848 bool __was_long, __now_long;
2849 if (__res_arg == __min_cap - 1)
2850 {
2851 __was_long = true;
2852 __now_long = false;
2853 __new_data = __get_short_pointer();
2854 __p = __get_long_pointer();
2855 }
2856 else
2857 {
2858 if (__res_arg > __cap)
Howard Hinnante32b5e22010-11-17 17:55:08 +00002859 __new_data = __alloc_traits::allocate(__alloc(), __res_arg+1);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002860 else
2861 {
2862 #ifndef _LIBCPP_NO_EXCEPTIONS
2863 try
2864 {
Howard Hinnant324bb032010-08-22 00:02:43 +00002865 #endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnante32b5e22010-11-17 17:55:08 +00002866 __new_data = __alloc_traits::allocate(__alloc(), __res_arg+1);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002867 #ifndef _LIBCPP_NO_EXCEPTIONS
2868 }
2869 catch (...)
2870 {
2871 return;
2872 }
Howard Hinnant324bb032010-08-22 00:02:43 +00002873 #else // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002874 if (__new_data == 0)
2875 return;
Howard Hinnant324bb032010-08-22 00:02:43 +00002876 #endif // _LIBCPP_NO_EXCEPTIONS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002877 }
2878 __now_long = true;
2879 __was_long = __is_long();
2880 __p = __get_pointer();
2881 }
2882 traits_type::copy(__new_data, __p, size()+1);
2883 if (__was_long)
Howard Hinnante32b5e22010-11-17 17:55:08 +00002884 __alloc_traits::deallocate(__alloc(), __p, __cap+1);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002885 if (__now_long)
2886 {
2887 __set_long_cap(__res_arg+1);
2888 __set_long_size(__sz);
2889 __set_long_pointer(__new_data);
2890 }
2891 else
2892 __set_short_size(__sz);
2893 __invalidate_all_iterators();
2894 }
2895}
2896
2897template <class _CharT, class _Traits, class _Allocator>
2898_LIBCPP_INLINE_VISIBILITY inline
2899typename basic_string<_CharT, _Traits, _Allocator>::const_reference
2900basic_string<_CharT, _Traits, _Allocator>::operator[](size_type __pos) const
2901{
2902#ifdef __LIBCPP_DEBUG
2903 assert(__pos <= size());
2904#endif
2905 return *(data() + __pos);
2906}
2907
2908template <class _CharT, class _Traits, class _Allocator>
2909_LIBCPP_INLINE_VISIBILITY inline
2910typename basic_string<_CharT, _Traits, _Allocator>::reference
2911basic_string<_CharT, _Traits, _Allocator>::operator[](size_type __pos)
2912{
2913#ifdef __LIBCPP_DEBUG
2914 assert(__pos < size());
2915#endif
2916 return *(__get_pointer() + __pos);
2917}
2918
2919template <class _CharT, class _Traits, class _Allocator>
2920typename basic_string<_CharT, _Traits, _Allocator>::const_reference
2921basic_string<_CharT, _Traits, _Allocator>::at(size_type __n) const
2922{
2923 if (__n >= size())
2924 this->__throw_out_of_range();
2925 return (*this)[__n];
2926}
2927
2928template <class _CharT, class _Traits, class _Allocator>
2929typename basic_string<_CharT, _Traits, _Allocator>::reference
2930basic_string<_CharT, _Traits, _Allocator>::at(size_type __n)
2931{
2932 if (__n >= size())
2933 this->__throw_out_of_range();
2934 return (*this)[__n];
2935}
2936
2937template <class _CharT, class _Traits, class _Allocator>
2938_LIBCPP_INLINE_VISIBILITY inline
2939typename basic_string<_CharT, _Traits, _Allocator>::reference
2940basic_string<_CharT, _Traits, _Allocator>::front()
2941{
2942#ifdef _LIBCPP_DEBUG
2943 assert(!empty());
2944#endif
2945 return *__get_pointer();
2946}
2947
2948template <class _CharT, class _Traits, class _Allocator>
2949_LIBCPP_INLINE_VISIBILITY inline
2950typename basic_string<_CharT, _Traits, _Allocator>::const_reference
2951basic_string<_CharT, _Traits, _Allocator>::front() const
2952{
2953#ifdef _LIBCPP_DEBUG
2954 assert(!empty());
2955#endif
2956 return *data();
2957}
2958
2959template <class _CharT, class _Traits, class _Allocator>
2960_LIBCPP_INLINE_VISIBILITY inline
2961typename basic_string<_CharT, _Traits, _Allocator>::reference
2962basic_string<_CharT, _Traits, _Allocator>::back()
2963{
2964#ifdef _LIBCPP_DEBUG
2965 assert(!empty());
2966#endif
2967 return *(__get_pointer() + size() - 1);
2968}
2969
2970template <class _CharT, class _Traits, class _Allocator>
2971_LIBCPP_INLINE_VISIBILITY inline
2972typename basic_string<_CharT, _Traits, _Allocator>::const_reference
2973basic_string<_CharT, _Traits, _Allocator>::back() const
2974{
2975#ifdef _LIBCPP_DEBUG
2976 assert(!empty());
2977#endif
2978 return *(data() + size() - 1);
2979}
2980
2981template <class _CharT, class _Traits, class _Allocator>
2982typename basic_string<_CharT, _Traits, _Allocator>::size_type
2983basic_string<_CharT, _Traits, _Allocator>::copy(pointer __s, size_type __n, size_type __pos) const
2984{
2985 size_type __sz = size();
2986 if (__pos > __sz)
2987 this->__throw_out_of_range();
Howard Hinnant0949eed2011-06-30 21:18:19 +00002988 size_type __rlen = _VSTD::min(__n, __sz - __pos);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00002989 traits_type::copy(__s, data() + __pos, __rlen);
2990 return __rlen;
2991}
2992
2993template <class _CharT, class _Traits, class _Allocator>
2994_LIBCPP_INLINE_VISIBILITY inline
2995basic_string<_CharT, _Traits, _Allocator>
2996basic_string<_CharT, _Traits, _Allocator>::substr(size_type __pos, size_type __n) const
2997{
2998 return basic_string(*this, __pos, __n, __alloc());
2999}
3000
3001template <class _CharT, class _Traits, class _Allocator>
3002_LIBCPP_INLINE_VISIBILITY inline
3003void
3004basic_string<_CharT, _Traits, _Allocator>::swap(basic_string& __str)
Howard Hinnant53f7d4c2011-06-03 18:40:47 +00003005 _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value ||
3006 __is_nothrow_swappable<allocator_type>::value)
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003007{
Howard Hinnant0949eed2011-06-30 21:18:19 +00003008 _VSTD::swap(__r_.first(), __str.__r_.first());
Howard Hinnante32b5e22010-11-17 17:55:08 +00003009 __swap_alloc(__alloc(), __str.__alloc());
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003010#ifdef _LIBCPP_DEBUG
3011 __invalidate_all_iterators();
3012 __str.__invalidate_all_iterators();
Howard Hinnant324bb032010-08-22 00:02:43 +00003013#endif // _LIBCPP_DEBUG
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003014}
3015
3016// find
3017
3018template <class _Traits>
3019struct _LIBCPP_HIDDEN __traits_eq
3020{
3021 typedef typename _Traits::char_type char_type;
Howard Hinnanta6119a82011-05-29 19:57:12 +00003022 _LIBCPP_INLINE_VISIBILITY
3023 bool operator()(const char_type& __x, const char_type& __y) _NOEXCEPT
3024 {return _Traits::eq(__x, __y);}
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003025};
3026
3027template<class _CharT, class _Traits, class _Allocator>
3028typename basic_string<_CharT, _Traits, _Allocator>::size_type
Howard Hinnanta6119a82011-05-29 19:57:12 +00003029basic_string<_CharT, _Traits, _Allocator>::find(const_pointer __s,
3030 size_type __pos,
3031 size_type __n) const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003032{
3033#ifdef _LIBCPP_DEBUG
3034 assert(__s != 0);
3035#endif
3036 size_type __sz = size();
3037 if (__pos > __sz || __sz - __pos < __n)
3038 return npos;
3039 if (__n == 0)
3040 return __pos;
3041 const_pointer __p = data();
Howard Hinnant0949eed2011-06-30 21:18:19 +00003042 const_pointer __r = _VSTD::search(__p + __pos, __p + __sz, __s, __s + __n,
Howard Hinnanta6119a82011-05-29 19:57:12 +00003043 __traits_eq<traits_type>());
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003044 if (__r == __p + __sz)
3045 return npos;
3046 return static_cast<size_type>(__r - __p);
3047}
3048
3049template<class _CharT, class _Traits, class _Allocator>
3050_LIBCPP_INLINE_VISIBILITY inline
3051typename basic_string<_CharT, _Traits, _Allocator>::size_type
Howard Hinnanta6119a82011-05-29 19:57:12 +00003052basic_string<_CharT, _Traits, _Allocator>::find(const basic_string& __str,
3053 size_type __pos) const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003054{
3055 return find(__str.data(), __pos, __str.size());
3056}
3057
3058template<class _CharT, class _Traits, class _Allocator>
3059_LIBCPP_INLINE_VISIBILITY inline
3060typename basic_string<_CharT, _Traits, _Allocator>::size_type
Howard Hinnanta6119a82011-05-29 19:57:12 +00003061basic_string<_CharT, _Traits, _Allocator>::find(const_pointer __s,
3062 size_type __pos) const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003063{
3064#ifdef _LIBCPP_DEBUG
3065 assert(__s != 0);
3066#endif
3067 return find(__s, __pos, traits_type::length(__s));
3068}
3069
3070template<class _CharT, class _Traits, class _Allocator>
3071typename basic_string<_CharT, _Traits, _Allocator>::size_type
Howard Hinnanta6119a82011-05-29 19:57:12 +00003072basic_string<_CharT, _Traits, _Allocator>::find(value_type __c,
3073 size_type __pos) const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003074{
3075 size_type __sz = size();
3076 if (__pos >= __sz)
3077 return npos;
3078 const_pointer __p = data();
3079 const_pointer __r = traits_type::find(__p + __pos, __sz - __pos, __c);
3080 if (__r == 0)
3081 return npos;
3082 return static_cast<size_type>(__r - __p);
3083}
3084
3085// rfind
3086
3087template<class _CharT, class _Traits, class _Allocator>
3088typename basic_string<_CharT, _Traits, _Allocator>::size_type
Howard Hinnanta6119a82011-05-29 19:57:12 +00003089basic_string<_CharT, _Traits, _Allocator>::rfind(const_pointer __s,
3090 size_type __pos,
3091 size_type __n) const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003092{
3093#ifdef _LIBCPP_DEBUG
3094 assert(__s != 0);
3095#endif
3096 size_type __sz = size();
Howard Hinnant0949eed2011-06-30 21:18:19 +00003097 __pos = _VSTD::min(__pos, __sz);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003098 if (__n < __sz - __pos)
3099 __pos += __n;
3100 else
3101 __pos = __sz;
3102 const_pointer __p = data();
Howard Hinnant0949eed2011-06-30 21:18:19 +00003103 const_pointer __r = _VSTD::find_end(__p, __p + __pos, __s, __s + __n,
Howard Hinnanta6119a82011-05-29 19:57:12 +00003104 __traits_eq<traits_type>());
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003105 if (__n > 0 && __r == __p + __pos)
3106 return npos;
3107 return static_cast<size_type>(__r - __p);
3108}
3109
3110template<class _CharT, class _Traits, class _Allocator>
3111_LIBCPP_INLINE_VISIBILITY inline
3112typename basic_string<_CharT, _Traits, _Allocator>::size_type
Howard Hinnanta6119a82011-05-29 19:57:12 +00003113basic_string<_CharT, _Traits, _Allocator>::rfind(const basic_string& __str,
3114 size_type __pos) const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003115{
3116 return rfind(__str.data(), __pos, __str.size());
3117}
3118
3119template<class _CharT, class _Traits, class _Allocator>
3120_LIBCPP_INLINE_VISIBILITY inline
3121typename basic_string<_CharT, _Traits, _Allocator>::size_type
Howard Hinnanta6119a82011-05-29 19:57:12 +00003122basic_string<_CharT, _Traits, _Allocator>::rfind(const_pointer __s,
3123 size_type __pos) const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003124{
3125#ifdef _LIBCPP_DEBUG
3126 assert(__s != 0);
3127#endif
3128 return rfind(__s, __pos, traits_type::length(__s));
3129}
3130
3131template<class _CharT, class _Traits, class _Allocator>
3132typename basic_string<_CharT, _Traits, _Allocator>::size_type
Howard Hinnanta6119a82011-05-29 19:57:12 +00003133basic_string<_CharT, _Traits, _Allocator>::rfind(value_type __c,
3134 size_type __pos) const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003135{
3136 size_type __sz = size();
3137 if (__sz)
3138 {
3139 if (__pos < __sz)
3140 ++__pos;
3141 else
3142 __pos = __sz;
3143 const_pointer __p = data();
3144 for (const_pointer __ps = __p + __pos; __ps != __p;)
3145 {
3146 if (traits_type::eq(*--__ps, __c))
3147 return static_cast<size_type>(__ps - __p);
3148 }
3149 }
3150 return npos;
3151}
3152
3153// find_first_of
3154
3155template<class _CharT, class _Traits, class _Allocator>
3156typename basic_string<_CharT, _Traits, _Allocator>::size_type
Howard Hinnanta6119a82011-05-29 19:57:12 +00003157basic_string<_CharT, _Traits, _Allocator>::find_first_of(const_pointer __s,
3158 size_type __pos,
3159 size_type __n) const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003160{
3161#ifdef _LIBCPP_DEBUG
3162 assert(__s != 0);
3163#endif
3164 size_type __sz = size();
3165 if (__pos >= __sz || __n == 0)
3166 return npos;
3167 const_pointer __p = data();
Howard Hinnant0949eed2011-06-30 21:18:19 +00003168 const_pointer __r = _VSTD::find_first_of(__p + __pos, __p + __sz, __s,
Howard Hinnanta6119a82011-05-29 19:57:12 +00003169 __s + __n, __traits_eq<traits_type>());
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003170 if (__r == __p + __sz)
3171 return npos;
3172 return static_cast<size_type>(__r - __p);
3173}
3174
3175template<class _CharT, class _Traits, class _Allocator>
3176_LIBCPP_INLINE_VISIBILITY inline
3177typename basic_string<_CharT, _Traits, _Allocator>::size_type
Howard Hinnanta6119a82011-05-29 19:57:12 +00003178basic_string<_CharT, _Traits, _Allocator>::find_first_of(const basic_string& __str,
3179 size_type __pos) const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003180{
3181 return find_first_of(__str.data(), __pos, __str.size());
3182}
3183
3184template<class _CharT, class _Traits, class _Allocator>
3185_LIBCPP_INLINE_VISIBILITY inline
3186typename basic_string<_CharT, _Traits, _Allocator>::size_type
Howard Hinnanta6119a82011-05-29 19:57:12 +00003187basic_string<_CharT, _Traits, _Allocator>::find_first_of(const_pointer __s,
3188 size_type __pos) const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003189{
3190#ifdef _LIBCPP_DEBUG
3191 assert(__s != 0);
3192#endif
3193 return find_first_of(__s, __pos, traits_type::length(__s));
3194}
3195
3196template<class _CharT, class _Traits, class _Allocator>
3197_LIBCPP_INLINE_VISIBILITY inline
3198typename basic_string<_CharT, _Traits, _Allocator>::size_type
Howard Hinnanta6119a82011-05-29 19:57:12 +00003199basic_string<_CharT, _Traits, _Allocator>::find_first_of(value_type __c,
3200 size_type __pos) const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003201{
3202 return find(__c, __pos);
3203}
3204
3205// find_last_of
3206
3207template<class _CharT, class _Traits, class _Allocator>
3208typename basic_string<_CharT, _Traits, _Allocator>::size_type
Howard Hinnanta6119a82011-05-29 19:57:12 +00003209basic_string<_CharT, _Traits, _Allocator>::find_last_of(const_pointer __s,
3210 size_type __pos,
3211 size_type __n) const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003212{
3213#ifdef _LIBCPP_DEBUG
3214 assert(__s != 0);
3215#endif
3216 if (__n != 0)
3217 {
3218 size_type __sz = size();
3219 if (__pos < __sz)
3220 ++__pos;
3221 else
3222 __pos = __sz;
3223 const_pointer __p = data();
3224 for (const_pointer __ps = __p + __pos; __ps != __p;)
3225 {
3226 const_pointer __r = traits_type::find(__s, __n, *--__ps);
3227 if (__r)
3228 return static_cast<size_type>(__ps - __p);
3229 }
3230 }
3231 return npos;
3232}
3233
3234template<class _CharT, class _Traits, class _Allocator>
3235_LIBCPP_INLINE_VISIBILITY inline
3236typename basic_string<_CharT, _Traits, _Allocator>::size_type
Howard Hinnanta6119a82011-05-29 19:57:12 +00003237basic_string<_CharT, _Traits, _Allocator>::find_last_of(const basic_string& __str,
3238 size_type __pos) const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003239{
3240 return find_last_of(__str.data(), __pos, __str.size());
3241}
3242
3243template<class _CharT, class _Traits, class _Allocator>
3244_LIBCPP_INLINE_VISIBILITY inline
3245typename basic_string<_CharT, _Traits, _Allocator>::size_type
Howard Hinnanta6119a82011-05-29 19:57:12 +00003246basic_string<_CharT, _Traits, _Allocator>::find_last_of(const_pointer __s,
3247 size_type __pos) const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003248{
3249#ifdef _LIBCPP_DEBUG
3250 assert(__s != 0);
3251#endif
3252 return find_last_of(__s, __pos, traits_type::length(__s));
3253}
3254
3255template<class _CharT, class _Traits, class _Allocator>
3256_LIBCPP_INLINE_VISIBILITY inline
3257typename basic_string<_CharT, _Traits, _Allocator>::size_type
Howard Hinnanta6119a82011-05-29 19:57:12 +00003258basic_string<_CharT, _Traits, _Allocator>::find_last_of(value_type __c,
3259 size_type __pos) const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003260{
3261 return rfind(__c, __pos);
3262}
3263
3264// find_first_not_of
3265
3266template<class _CharT, class _Traits, class _Allocator>
3267typename basic_string<_CharT, _Traits, _Allocator>::size_type
Howard Hinnanta6119a82011-05-29 19:57:12 +00003268basic_string<_CharT, _Traits, _Allocator>::find_first_not_of(const_pointer __s,
3269 size_type __pos,
3270 size_type __n) const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003271{
3272#ifdef _LIBCPP_DEBUG
3273 assert(__s != 0);
3274#endif
3275 size_type __sz = size();
3276 if (__pos < __sz)
3277 {
3278 const_pointer __p = data();
3279 const_pointer __pe = __p + __sz;
3280 for (const_pointer __ps = __p + __pos; __ps != __pe; ++__ps)
3281 if (traits_type::find(__s, __n, *__ps) == 0)
3282 return static_cast<size_type>(__ps - __p);
3283 }
3284 return npos;
3285}
3286
3287template<class _CharT, class _Traits, class _Allocator>
3288_LIBCPP_INLINE_VISIBILITY inline
3289typename basic_string<_CharT, _Traits, _Allocator>::size_type
Howard Hinnanta6119a82011-05-29 19:57:12 +00003290basic_string<_CharT, _Traits, _Allocator>::find_first_not_of(const basic_string& __str,
3291 size_type __pos) const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003292{
3293 return find_first_not_of(__str.data(), __pos, __str.size());
3294}
3295
3296template<class _CharT, class _Traits, class _Allocator>
3297_LIBCPP_INLINE_VISIBILITY inline
3298typename basic_string<_CharT, _Traits, _Allocator>::size_type
Howard Hinnanta6119a82011-05-29 19:57:12 +00003299basic_string<_CharT, _Traits, _Allocator>::find_first_not_of(const_pointer __s,
3300 size_type __pos) const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003301{
3302#ifdef _LIBCPP_DEBUG
3303 assert(__s != 0);
3304#endif
3305 return find_first_not_of(__s, __pos, traits_type::length(__s));
3306}
3307
3308template<class _CharT, class _Traits, class _Allocator>
3309_LIBCPP_INLINE_VISIBILITY inline
3310typename basic_string<_CharT, _Traits, _Allocator>::size_type
Howard Hinnanta6119a82011-05-29 19:57:12 +00003311basic_string<_CharT, _Traits, _Allocator>::find_first_not_of(value_type __c,
3312 size_type __pos) const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003313{
3314 size_type __sz = size();
3315 if (__pos < __sz)
3316 {
3317 const_pointer __p = data();
3318 const_pointer __pe = __p + __sz;
3319 for (const_pointer __ps = __p + __pos; __p != __pe; ++__ps)
3320 if (!traits_type::eq(*__ps, __c))
3321 return static_cast<size_type>(__ps - __p);
3322 }
3323 return npos;
3324}
3325
3326// find_last_not_of
3327
3328template<class _CharT, class _Traits, class _Allocator>
3329typename basic_string<_CharT, _Traits, _Allocator>::size_type
Howard Hinnanta6119a82011-05-29 19:57:12 +00003330basic_string<_CharT, _Traits, _Allocator>::find_last_not_of(const_pointer __s,
3331 size_type __pos,
3332 size_type __n) const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003333{
3334#ifdef _LIBCPP_DEBUG
3335 assert(__s != 0);
3336#endif
3337 size_type __sz = size();
3338 if (__pos < __sz)
3339 ++__pos;
3340 else
3341 __pos = __sz;
3342 const_pointer __p = data();
3343 for (const_pointer __ps = __p + __pos; __ps != __p;)
3344 if (traits_type::find(__s, __n, *--__ps) == 0)
3345 return static_cast<size_type>(__ps - __p);
3346 return npos;
3347}
3348
3349template<class _CharT, class _Traits, class _Allocator>
3350_LIBCPP_INLINE_VISIBILITY inline
3351typename basic_string<_CharT, _Traits, _Allocator>::size_type
Howard Hinnanta6119a82011-05-29 19:57:12 +00003352basic_string<_CharT, _Traits, _Allocator>::find_last_not_of(const basic_string& __str,
3353 size_type __pos) const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003354{
3355 return find_last_not_of(__str.data(), __pos, __str.size());
3356}
3357
3358template<class _CharT, class _Traits, class _Allocator>
3359_LIBCPP_INLINE_VISIBILITY inline
3360typename basic_string<_CharT, _Traits, _Allocator>::size_type
Howard Hinnanta6119a82011-05-29 19:57:12 +00003361basic_string<_CharT, _Traits, _Allocator>::find_last_not_of(const_pointer __s,
3362 size_type __pos) const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003363{
3364#ifdef _LIBCPP_DEBUG
3365 assert(__s != 0);
3366#endif
3367 return find_last_not_of(__s, __pos, traits_type::length(__s));
3368}
3369
3370template<class _CharT, class _Traits, class _Allocator>
3371_LIBCPP_INLINE_VISIBILITY inline
3372typename basic_string<_CharT, _Traits, _Allocator>::size_type
Howard Hinnanta6119a82011-05-29 19:57:12 +00003373basic_string<_CharT, _Traits, _Allocator>::find_last_not_of(value_type __c,
3374 size_type __pos) const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003375{
3376 size_type __sz = size();
3377 if (__pos < __sz)
3378 ++__pos;
3379 else
3380 __pos = __sz;
3381 const_pointer __p = data();
3382 for (const_pointer __ps = __p + __pos; __ps != __p;)
3383 if (!traits_type::eq(*--__ps, __c))
3384 return static_cast<size_type>(__ps - __p);
3385 return npos;
3386}
3387
3388// compare
3389
3390template <class _CharT, class _Traits, class _Allocator>
3391_LIBCPP_INLINE_VISIBILITY inline
3392int
Howard Hinnanta6119a82011-05-29 19:57:12 +00003393basic_string<_CharT, _Traits, _Allocator>::compare(const basic_string& __str) const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003394{
3395 return compare(0, npos, __str.data(), __str.size());
3396}
3397
3398template <class _CharT, class _Traits, class _Allocator>
3399_LIBCPP_INLINE_VISIBILITY inline
3400int
Howard Hinnanta6119a82011-05-29 19:57:12 +00003401basic_string<_CharT, _Traits, _Allocator>::compare(size_type __pos1,
3402 size_type __n1,
3403 const basic_string& __str) const
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003404{
3405 return compare(__pos1, __n1, __str.data(), __str.size());
3406}
3407
3408template <class _CharT, class _Traits, class _Allocator>
3409int
Howard Hinnanta6119a82011-05-29 19:57:12 +00003410basic_string<_CharT, _Traits, _Allocator>::compare(size_type __pos1,
3411 size_type __n1,
3412 const basic_string& __str,
3413 size_type __pos2,
3414 size_type __n2) const
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003415{
3416 size_type __sz = __str.size();
3417 if (__pos2 > __sz)
3418 this->__throw_out_of_range();
Howard Hinnant0949eed2011-06-30 21:18:19 +00003419 return compare(__pos1, __n1, __str.data() + __pos2, _VSTD::min(__n2,
Howard Hinnanta6119a82011-05-29 19:57:12 +00003420 __sz - __pos2));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003421}
3422
3423template <class _CharT, class _Traits, class _Allocator>
3424int
3425basic_string<_CharT, _Traits, _Allocator>::compare(const_pointer __s) const
3426{
3427#ifdef _LIBCPP_DEBUG
3428 assert(__s != 0);
3429#endif
3430 return compare(0, npos, __s, traits_type::length(__s));
3431}
3432
3433template <class _CharT, class _Traits, class _Allocator>
3434int
Howard Hinnanta6119a82011-05-29 19:57:12 +00003435basic_string<_CharT, _Traits, _Allocator>::compare(size_type __pos1,
3436 size_type __n1,
3437 const_pointer __s) const
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003438{
3439#ifdef _LIBCPP_DEBUG
3440 assert(__s != 0);
3441#endif
3442 return compare(__pos1, __n1, __s, traits_type::length(__s));
3443}
3444
3445template <class _CharT, class _Traits, class _Allocator>
3446int
Howard Hinnanta6119a82011-05-29 19:57:12 +00003447basic_string<_CharT, _Traits, _Allocator>::compare(size_type __pos1,
3448 size_type __n1,
3449 const_pointer __s,
3450 size_type __n2) const
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003451{
3452#ifdef _LIBCPP_DEBUG
3453 assert(__s != 0);
3454#endif
3455 size_type __sz = size();
3456 if (__pos1 > __sz || __n2 == npos)
3457 this->__throw_out_of_range();
Howard Hinnant0949eed2011-06-30 21:18:19 +00003458 size_type __rlen = _VSTD::min(__n1, __sz - __pos1);
3459 int __r = traits_type::compare(data() + __pos1, __s, _VSTD::min(__rlen, __n2));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003460 if (__r == 0)
3461 {
3462 if (__rlen < __n2)
3463 __r = -1;
3464 else if (__rlen > __n2)
3465 __r = 1;
3466 }
3467 return __r;
3468}
3469
3470// __invariants
3471
3472template<class _CharT, class _Traits, class _Allocator>
Howard Hinnant2d72b1e2010-12-17 14:46:43 +00003473_LIBCPP_INLINE_VISIBILITY inline
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003474bool
3475basic_string<_CharT, _Traits, _Allocator>::__invariants() const
3476{
3477 if (size() > capacity())
3478 return false;
3479 if (capacity() < __min_cap - 1)
3480 return false;
3481 if (data() == 0)
3482 return false;
3483 if (data()[size()] != value_type(0))
3484 return false;
3485 return true;
3486}
3487
3488// operator==
3489
3490template<class _CharT, class _Traits, class _Allocator>
3491_LIBCPP_INLINE_VISIBILITY inline
3492bool
3493operator==(const basic_string<_CharT, _Traits, _Allocator>& __lhs,
Howard Hinnanta6119a82011-05-29 19:57:12 +00003494 const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003495{
Howard Hinnanta6119a82011-05-29 19:57:12 +00003496 return __lhs.size() == __rhs.size() && _Traits::compare(__lhs.data(),
3497 __rhs.data(),
3498 __lhs.size()) == 0;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003499}
3500
3501template<class _CharT, class _Traits, class _Allocator>
3502_LIBCPP_INLINE_VISIBILITY inline
3503bool
Howard Hinnanta6119a82011-05-29 19:57:12 +00003504operator==(const _CharT* __lhs,
3505 const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003506{
3507 return __rhs.compare(__lhs) == 0;
3508}
3509
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003510template<class _CharT, class _Traits, class _Allocator>
3511_LIBCPP_INLINE_VISIBILITY inline
3512bool
Howard Hinnanta6119a82011-05-29 19:57:12 +00003513operator==(const basic_string<_CharT,_Traits,_Allocator>& __lhs,
3514 const _CharT* __rhs) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003515{
3516 return __lhs.compare(__rhs) == 0;
3517}
3518
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003519// operator!=
3520
Howard Hinnant324bb032010-08-22 00:02:43 +00003521template<class _CharT, class _Traits, class _Allocator>
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003522_LIBCPP_INLINE_VISIBILITY inline
3523bool
3524operator!=(const basic_string<_CharT,_Traits,_Allocator>& __lhs,
Howard Hinnanta6119a82011-05-29 19:57:12 +00003525 const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003526{
3527 return !(__lhs == __rhs);
3528}
3529
3530template<class _CharT, class _Traits, class _Allocator>
3531_LIBCPP_INLINE_VISIBILITY inline
3532bool
Howard Hinnanta6119a82011-05-29 19:57:12 +00003533operator!=(const _CharT* __lhs,
3534 const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003535{
3536 return !(__lhs == __rhs);
3537}
3538
3539template<class _CharT, class _Traits, class _Allocator>
3540_LIBCPP_INLINE_VISIBILITY inline
3541bool
Howard Hinnanta6119a82011-05-29 19:57:12 +00003542operator!=(const basic_string<_CharT, _Traits, _Allocator>& __lhs,
3543 const _CharT* __rhs) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003544{
3545 return !(__lhs == __rhs);
3546}
3547
3548// operator<
3549
3550template<class _CharT, class _Traits, class _Allocator>
3551_LIBCPP_INLINE_VISIBILITY inline
3552bool
3553operator< (const basic_string<_CharT, _Traits, _Allocator>& __lhs,
Howard Hinnanta6119a82011-05-29 19:57:12 +00003554 const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003555{
Howard Hinnant2644a7b2011-07-24 15:07:21 +00003556 return __lhs.compare(__rhs) < 0;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003557}
3558
3559template<class _CharT, class _Traits, class _Allocator>
3560_LIBCPP_INLINE_VISIBILITY inline
3561bool
Howard Hinnanta6119a82011-05-29 19:57:12 +00003562operator< (const basic_string<_CharT, _Traits, _Allocator>& __lhs,
3563 const _CharT* __rhs) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003564{
Howard Hinnant2644a7b2011-07-24 15:07:21 +00003565 return __lhs.compare(__rhs) < 0;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003566}
3567
3568template<class _CharT, class _Traits, class _Allocator>
3569_LIBCPP_INLINE_VISIBILITY inline
3570bool
Howard Hinnanta6119a82011-05-29 19:57:12 +00003571operator< (const _CharT* __lhs,
3572 const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003573{
3574 return __rhs.compare(__lhs) > 0;
3575}
3576
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003577// operator>
3578
3579template<class _CharT, class _Traits, class _Allocator>
3580_LIBCPP_INLINE_VISIBILITY inline
3581bool
3582operator> (const basic_string<_CharT, _Traits, _Allocator>& __lhs,
Howard Hinnanta6119a82011-05-29 19:57:12 +00003583 const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003584{
3585 return __rhs < __lhs;
3586}
3587
3588template<class _CharT, class _Traits, class _Allocator>
3589_LIBCPP_INLINE_VISIBILITY inline
3590bool
Howard Hinnanta6119a82011-05-29 19:57:12 +00003591operator> (const basic_string<_CharT, _Traits, _Allocator>& __lhs,
3592 const _CharT* __rhs) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003593{
3594 return __rhs < __lhs;
3595}
3596
3597template<class _CharT, class _Traits, class _Allocator>
3598_LIBCPP_INLINE_VISIBILITY inline
3599bool
Howard Hinnanta6119a82011-05-29 19:57:12 +00003600operator> (const _CharT* __lhs,
3601 const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003602{
3603 return __rhs < __lhs;
3604}
3605
3606// operator<=
3607
3608template<class _CharT, class _Traits, class _Allocator>
3609_LIBCPP_INLINE_VISIBILITY inline
3610bool
3611operator<=(const basic_string<_CharT, _Traits, _Allocator>& __lhs,
Howard Hinnanta6119a82011-05-29 19:57:12 +00003612 const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003613{
3614 return !(__rhs < __lhs);
3615}
3616
3617template<class _CharT, class _Traits, class _Allocator>
3618_LIBCPP_INLINE_VISIBILITY inline
3619bool
Howard Hinnanta6119a82011-05-29 19:57:12 +00003620operator<=(const basic_string<_CharT, _Traits, _Allocator>& __lhs,
3621 const _CharT* __rhs) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003622{
3623 return !(__rhs < __lhs);
3624}
3625
3626template<class _CharT, class _Traits, class _Allocator>
3627_LIBCPP_INLINE_VISIBILITY inline
3628bool
Howard Hinnanta6119a82011-05-29 19:57:12 +00003629operator<=(const _CharT* __lhs,
3630 const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003631{
3632 return !(__rhs < __lhs);
3633}
3634
3635// operator>=
3636
3637template<class _CharT, class _Traits, class _Allocator>
3638_LIBCPP_INLINE_VISIBILITY inline
3639bool
3640operator>=(const basic_string<_CharT, _Traits, _Allocator>& __lhs,
Howard Hinnanta6119a82011-05-29 19:57:12 +00003641 const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003642{
3643 return !(__lhs < __rhs);
3644}
3645
3646template<class _CharT, class _Traits, class _Allocator>
3647_LIBCPP_INLINE_VISIBILITY inline
3648bool
Howard Hinnanta6119a82011-05-29 19:57:12 +00003649operator>=(const basic_string<_CharT, _Traits, _Allocator>& __lhs,
3650 const _CharT* __rhs) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003651{
3652 return !(__lhs < __rhs);
3653}
3654
3655template<class _CharT, class _Traits, class _Allocator>
3656_LIBCPP_INLINE_VISIBILITY inline
3657bool
Howard Hinnanta6119a82011-05-29 19:57:12 +00003658operator>=(const _CharT* __lhs,
3659 const basic_string<_CharT, _Traits, _Allocator>& __rhs) _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003660{
3661 return !(__lhs < __rhs);
3662}
3663
3664// operator +
3665
3666template<class _CharT, class _Traits, class _Allocator>
3667basic_string<_CharT, _Traits, _Allocator>
3668operator+(const basic_string<_CharT, _Traits, _Allocator>& __lhs,
3669 const basic_string<_CharT, _Traits, _Allocator>& __rhs)
3670{
3671 basic_string<_CharT, _Traits, _Allocator> __r(__lhs.get_allocator());
3672 typename basic_string<_CharT, _Traits, _Allocator>::size_type __lhs_sz = __lhs.size();
3673 typename basic_string<_CharT, _Traits, _Allocator>::size_type __rhs_sz = __rhs.size();
3674 __r.__init(__lhs.data(), __lhs_sz, __lhs_sz + __rhs_sz);
3675 __r.append(__rhs.data(), __rhs_sz);
3676 return __r;
3677}
3678
3679template<class _CharT, class _Traits, class _Allocator>
3680basic_string<_CharT, _Traits, _Allocator>
3681operator+(const _CharT* __lhs , const basic_string<_CharT,_Traits,_Allocator>& __rhs)
3682{
3683 basic_string<_CharT, _Traits, _Allocator> __r(__rhs.get_allocator());
3684 typename basic_string<_CharT, _Traits, _Allocator>::size_type __lhs_sz = _Traits::length(__lhs);
3685 typename basic_string<_CharT, _Traits, _Allocator>::size_type __rhs_sz = __rhs.size();
3686 __r.__init(__lhs, __lhs_sz, __lhs_sz + __rhs_sz);
3687 __r.append(__rhs.data(), __rhs_sz);
3688 return __r;
3689}
3690
3691template<class _CharT, class _Traits, class _Allocator>
3692basic_string<_CharT, _Traits, _Allocator>
3693operator+(_CharT __lhs, const basic_string<_CharT,_Traits,_Allocator>& __rhs)
3694{
3695 basic_string<_CharT, _Traits, _Allocator> __r(__rhs.get_allocator());
3696 typename basic_string<_CharT, _Traits, _Allocator>::size_type __rhs_sz = __rhs.size();
3697 __r.__init(&__lhs, 1, 1 + __rhs_sz);
3698 __r.append(__rhs.data(), __rhs_sz);
3699 return __r;
3700}
3701
3702template<class _CharT, class _Traits, class _Allocator>
3703basic_string<_CharT, _Traits, _Allocator>
3704operator+(const basic_string<_CharT, _Traits, _Allocator>& __lhs, const _CharT* __rhs)
3705{
3706 basic_string<_CharT, _Traits, _Allocator> __r(__lhs.get_allocator());
3707 typename basic_string<_CharT, _Traits, _Allocator>::size_type __lhs_sz = __lhs.size();
3708 typename basic_string<_CharT, _Traits, _Allocator>::size_type __rhs_sz = _Traits::length(__rhs);
3709 __r.__init(__lhs.data(), __lhs_sz, __lhs_sz + __rhs_sz);
3710 __r.append(__rhs, __rhs_sz);
3711 return __r;
3712}
3713
3714template<class _CharT, class _Traits, class _Allocator>
3715basic_string<_CharT, _Traits, _Allocator>
3716operator+(const basic_string<_CharT, _Traits, _Allocator>& __lhs, _CharT __rhs)
3717{
3718 basic_string<_CharT, _Traits, _Allocator> __r(__lhs.get_allocator());
3719 typename basic_string<_CharT, _Traits, _Allocator>::size_type __lhs_sz = __lhs.size();
3720 __r.__init(__lhs.data(), __lhs_sz, __lhs_sz + 1);
3721 __r.push_back(__rhs);
3722 return __r;
3723}
3724
Howard Hinnant73d21a42010-09-04 23:28:19 +00003725#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003726
3727template<class _CharT, class _Traits, class _Allocator>
3728_LIBCPP_INLINE_VISIBILITY inline
3729basic_string<_CharT, _Traits, _Allocator>
3730operator+(basic_string<_CharT, _Traits, _Allocator>&& __lhs, const basic_string<_CharT, _Traits, _Allocator>& __rhs)
3731{
Howard Hinnant0949eed2011-06-30 21:18:19 +00003732 return _VSTD::move(__lhs.append(__rhs));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003733}
3734
3735template<class _CharT, class _Traits, class _Allocator>
3736_LIBCPP_INLINE_VISIBILITY inline
3737basic_string<_CharT, _Traits, _Allocator>
3738operator+(const basic_string<_CharT, _Traits, _Allocator>& __lhs, basic_string<_CharT, _Traits, _Allocator>&& __rhs)
3739{
Howard Hinnant0949eed2011-06-30 21:18:19 +00003740 return _VSTD::move(__rhs.insert(0, __lhs));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003741}
3742
3743template<class _CharT, class _Traits, class _Allocator>
3744_LIBCPP_INLINE_VISIBILITY inline
3745basic_string<_CharT, _Traits, _Allocator>
3746operator+(basic_string<_CharT, _Traits, _Allocator>&& __lhs, basic_string<_CharT, _Traits, _Allocator>&& __rhs)
3747{
Howard Hinnant0949eed2011-06-30 21:18:19 +00003748 return _VSTD::move(__lhs.append(__rhs));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003749}
3750
3751template<class _CharT, class _Traits, class _Allocator>
3752_LIBCPP_INLINE_VISIBILITY inline
3753basic_string<_CharT, _Traits, _Allocator>
3754operator+(const _CharT* __lhs , basic_string<_CharT,_Traits,_Allocator>&& __rhs)
3755{
Howard Hinnant0949eed2011-06-30 21:18:19 +00003756 return _VSTD::move(__rhs.insert(0, __lhs));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003757}
3758
3759template<class _CharT, class _Traits, class _Allocator>
3760_LIBCPP_INLINE_VISIBILITY inline
3761basic_string<_CharT, _Traits, _Allocator>
3762operator+(_CharT __lhs, basic_string<_CharT,_Traits,_Allocator>&& __rhs)
3763{
3764 __rhs.insert(__rhs.begin(), __lhs);
Howard Hinnant0949eed2011-06-30 21:18:19 +00003765 return _VSTD::move(__rhs);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003766}
3767
3768template<class _CharT, class _Traits, class _Allocator>
3769_LIBCPP_INLINE_VISIBILITY inline
3770basic_string<_CharT, _Traits, _Allocator>
3771operator+(basic_string<_CharT, _Traits, _Allocator>&& __lhs, const _CharT* __rhs)
3772{
Howard Hinnant0949eed2011-06-30 21:18:19 +00003773 return _VSTD::move(__lhs.append(__rhs));
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003774}
3775
3776template<class _CharT, class _Traits, class _Allocator>
3777_LIBCPP_INLINE_VISIBILITY inline
3778basic_string<_CharT, _Traits, _Allocator>
3779operator+(basic_string<_CharT, _Traits, _Allocator>&& __lhs, _CharT __rhs)
3780{
3781 __lhs.push_back(__rhs);
Howard Hinnant0949eed2011-06-30 21:18:19 +00003782 return _VSTD::move(__lhs);
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003783}
3784
Howard Hinnant73d21a42010-09-04 23:28:19 +00003785#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003786
3787// swap
3788
3789template<class _CharT, class _Traits, class _Allocator>
3790_LIBCPP_INLINE_VISIBILITY inline
3791void
Howard Hinnanta6119a82011-05-29 19:57:12 +00003792swap(basic_string<_CharT, _Traits, _Allocator>& __lhs,
Howard Hinnant53f7d4c2011-06-03 18:40:47 +00003793 basic_string<_CharT, _Traits, _Allocator>& __rhs)
3794 _NOEXCEPT_(_NOEXCEPT_(__lhs.swap(__rhs)))
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003795{
3796 __lhs.swap(__rhs);
3797}
3798
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003799#ifndef _LIBCPP_HAS_NO_UNICODE_CHARS
3800
3801typedef basic_string<char16_t> u16string;
3802typedef basic_string<char32_t> u32string;
3803
Howard Hinnant324bb032010-08-22 00:02:43 +00003804#endif // _LIBCPP_HAS_NO_UNICODE_CHARS
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003805
Howard Hinnanta6a062d2010-06-02 18:20:39 +00003806int stoi (const string& __str, size_t* __idx = 0, int __base = 10);
3807long stol (const string& __str, size_t* __idx = 0, int __base = 10);
3808unsigned long stoul (const string& __str, size_t* __idx = 0, int __base = 10);
3809long long stoll (const string& __str, size_t* __idx = 0, int __base = 10);
3810unsigned long long stoull(const string& __str, size_t* __idx = 0, int __base = 10);
3811
3812float stof (const string& __str, size_t* __idx = 0);
3813double stod (const string& __str, size_t* __idx = 0);
3814long double stold(const string& __str, size_t* __idx = 0);
3815
3816string to_string(int __val);
3817string to_string(unsigned __val);
3818string to_string(long __val);
3819string to_string(unsigned long __val);
3820string to_string(long long __val);
3821string to_string(unsigned long long __val);
3822string to_string(float __val);
3823string to_string(double __val);
3824string to_string(long double __val);
3825
3826int stoi (const wstring& __str, size_t* __idx = 0, int __base = 10);
3827long stol (const wstring& __str, size_t* __idx = 0, int __base = 10);
3828unsigned long stoul (const wstring& __str, size_t* __idx = 0, int __base = 10);
3829long long stoll (const wstring& __str, size_t* __idx = 0, int __base = 10);
3830unsigned long long stoull(const wstring& __str, size_t* __idx = 0, int __base = 10);
3831
3832float stof (const wstring& __str, size_t* __idx = 0);
3833double stod (const wstring& __str, size_t* __idx = 0);
3834long double stold(const wstring& __str, size_t* __idx = 0);
3835
3836wstring to_wstring(int __val);
3837wstring to_wstring(unsigned __val);
3838wstring to_wstring(long __val);
3839wstring to_wstring(unsigned long __val);
3840wstring to_wstring(long long __val);
3841wstring to_wstring(unsigned long long __val);
3842wstring to_wstring(float __val);
3843wstring to_wstring(double __val);
3844wstring to_wstring(long double __val);
3845
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003846template<class _CharT, class _Traits, class _Allocator>
3847 const typename basic_string<_CharT, _Traits, _Allocator>::size_type
3848 basic_string<_CharT, _Traits, _Allocator>::npos;
3849
3850template<class _CharT, class _Traits, class _Allocator>
Howard Hinnant8d7a9552010-09-23 17:31:07 +00003851struct _LIBCPP_VISIBLE hash<basic_string<_CharT, _Traits, _Allocator> >
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003852 : public unary_function<basic_string<_CharT, _Traits, _Allocator>, size_t>
3853{
3854 size_t
Howard Hinnanta6119a82011-05-29 19:57:12 +00003855 operator()(const basic_string<_CharT, _Traits, _Allocator>& __val) const _NOEXCEPT;
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003856};
3857
3858template<class _CharT, class _Traits, class _Allocator>
3859size_t
3860hash<basic_string<_CharT, _Traits, _Allocator> >::operator()(
Howard Hinnanta6119a82011-05-29 19:57:12 +00003861 const basic_string<_CharT, _Traits, _Allocator>& __val) const _NOEXCEPT
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003862{
3863 typedef basic_string<_CharT, _Traits, _Allocator> S;
3864 typedef typename S::const_pointer const_pointer;
3865 size_t __r = 0;
3866 const size_t __sr = __CHAR_BIT__ * sizeof(size_t) - 8;
3867 const size_t __m = size_t(0xF) << (__sr + 4);
3868 const_pointer __p = __val.data();
3869 const_pointer __e = __p + __val.size();
3870 for (; __p != __e; ++__p)
3871 {
3872 __r = (__r << 4) + *__p;
3873 size_t __g = __r & __m;
3874 __r ^= __g | (__g >> __sr);
3875 }
3876 return __r;
3877}
3878
Howard Hinnant464aa5c2011-07-18 15:51:59 +00003879template<class _CharT, class _Traits, class _Allocator>
3880basic_ostream<_CharT, _Traits>&
3881operator<<(basic_ostream<_CharT, _Traits>& __os,
3882 const basic_string<_CharT, _Traits, _Allocator>& __str);
3883
3884template<class _CharT, class _Traits, class _Allocator>
3885basic_istream<_CharT, _Traits>&
3886operator>>(basic_istream<_CharT, _Traits>& __is,
3887 basic_string<_CharT, _Traits, _Allocator>& __str);
3888
3889template<class _CharT, class _Traits, class _Allocator>
3890basic_istream<_CharT, _Traits>&
3891getline(basic_istream<_CharT, _Traits>& __is,
3892 basic_string<_CharT, _Traits, _Allocator>& __str, _CharT __dlm);
3893
3894template<class _CharT, class _Traits, class _Allocator>
3895inline _LIBCPP_INLINE_VISIBILITY
3896basic_istream<_CharT, _Traits>&
3897getline(basic_istream<_CharT, _Traits>& __is,
3898 basic_string<_CharT, _Traits, _Allocator>& __str);
3899
3900#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
3901
3902template<class _CharT, class _Traits, class _Allocator>
3903inline _LIBCPP_INLINE_VISIBILITY
3904basic_istream<_CharT, _Traits>&
3905getline(basic_istream<_CharT, _Traits>&& __is,
3906 basic_string<_CharT, _Traits, _Allocator>& __str, _CharT __dlm);
3907
3908template<class _CharT, class _Traits, class _Allocator>
3909inline _LIBCPP_INLINE_VISIBILITY
3910basic_istream<_CharT, _Traits>&
3911getline(basic_istream<_CharT, _Traits>&& __is,
3912 basic_string<_CharT, _Traits, _Allocator>& __str);
3913
3914#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
3915
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003916extern template class basic_string<char>;
3917extern template class basic_string<wchar_t>;
3918
3919extern template
Howard Hinnantbc8d3f92010-05-11 19:42:16 +00003920 string
3921 operator+<char, char_traits<char>, allocator<char> >(char const*, string const&);
3922
3923_LIBCPP_END_NAMESPACE_STD
3924
3925#endif // _LIBCPP_STRING