basic_string.h source code [include/c++/6/bits/basic_string.h]

1	// Components for manipulating sequences of characters -- C++ --
2
3	// Copyright (C) 1997-2016 Free Software Foundation, Inc.
4	//
5	// This file is part of the GNU ISO C++ Library. This library is free
6	// software; you can redistribute it and/or modify it under the
7	// terms of the GNU General Public License as published by the
8	// Free Software Foundation; either version 3, or (at your option)
9	// any later version.
10
11	// This library is distributed in the hope that it will be useful,
12	// but WITHOUT ANY WARRANTY; without even the implied warranty of
13	// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14	// GNU General Public License for more details.
15
16	// Under Section 7 of GPL version 3, you are granted additional
17	// permissions described in the GCC Runtime Library Exception, version
18	// 3.1, as published by the Free Software Foundation.
19
20	// You should have received a copy of the GNU General Public License and
21	// a copy of the GCC Runtime Library Exception along with this program;
22	// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23	// <http://www.gnu.org/licenses/>.
24
25	/* @file bits/basic_string.h*
26	* This is an internal header file, included by other library headers.
27	* Do not attempt to use it directly. @headername{string}
28	*/
29
30	//
31	// ISO C++ 14882: 21 Strings library
32	//
33
34	#ifndef _BASIC_STRING_H
35	#define _BASIC_STRING_H 1
36
37	#pragma GCC system_header
38
39	#include <ext/atomicity.h>
40	#include <ext/alloc_traits.h>
41	#include <debug/debug.h>
42
43	#if __cplusplus >= 201103L
44	#include <initializer_list>
45	#endif
46
47	namespace std _GLIBCXX_VISIBILITY(default)
48	{
49	_GLIBCXX_BEGIN_NAMESPACE_VERSION
50
51	#if _GLIBCXX_USE_CXX11_ABI
52	_GLIBCXX_BEGIN_NAMESPACE_CXX11
53	/**
54	* @class basic_string basic_string.h <string>
55	* @brief Managing sequences of characters and character-like objects.
56	*
57	* @ingroup strings
58	* @ingroup sequences
59	*
60	* @tparam _CharT Type of character
61	* @tparam _Traits Traits for character type, defaults to
62	* char_traits<_CharT>.
63	* @tparam _Alloc Allocator type, defaults to allocator<_CharT>.
64	*
65	* Meets the requirements of a <a href="tables.html#65">container</a>, a
66	* <a href="tables.html#66">reversible container</a>, and a
67	* <a href="tables.html#67">sequence</a>. Of the
68	* <a href="tables.html#68">optional sequence requirements</a>, only
69	* @c push_back, @c at, and @c %array access are supported.
70	*/
71	template<typename _CharT, typename _Traits, typename _Alloc>
72	class basic_string
73	{
74	typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
75	rebind<_CharT>::other _Char_alloc_type;
76	typedef __gnu_cxx::__alloc_traits<_Char_alloc_type> _Alloc_traits;
77
78	// Types:
79	public:
80	typedef _Traits traits_type;
81	typedef typename _Traits::char_type value_type;
82	typedef _Char_alloc_type allocator_type;
83	typedef typename _Alloc_traits::size_type size_type;
84	typedef typename _Alloc_traits::difference_type difference_type;
85	typedef typename _Alloc_traits::reference reference;
86	typedef typename _Alloc_traits::const_reference const_reference;
87	typedef typename _Alloc_traits::pointer pointer;
88	typedef typename _Alloc_traits::const_pointer const_pointer;
89	typedef __gnu_cxx::__normal_iterator<pointer, basic_string> iterator;
90	typedef __gnu_cxx::__normal_iterator<const_pointer, basic_string>
91	const_iterator;
92	typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
93	typedef std::reverse_iterator<iterator> reverse_iterator;
94
95	/// Value returned by various member functions when they fail.
96	static const size_type npos = static_cast<size_type>(-`1`);
97
98	private:
99	// type used for positions in insert, erase etc.
100	#if __cplusplus < 201103L
101	typedef iterator __const_iterator;
102	#else
103	typedef const_iterator __const_iterator;
104	#endif
105
106	// Use empty-base optimization: http://www.cantrip.org/emptyopt.html
107	struct _Alloc_hider : allocator_type // TODO check __is_final
108	{
109	_Alloc_hider(pointer __dat, const _Alloc& __a = _Alloc())
110	: allocator_type(__a), _M_p(__dat) { }
111
112	pointer _M_p; // The actual data.
113	};
114
115	_Alloc_hider _M_dataplus;
116	size_type _M_string_length;
117
118	enum { _S_local_capacity = `15` / sizeof(_CharT) };
119
120	union
121	{
122	_CharT _M_local_buf[_S_local_capacity + `1`];
123	size_type _M_allocated_capacity;
124	};
125
126	void
127	_M_data(pointer __p)
128	{ _M_dataplus._M_p = __p; }
129
130	void
131	_M_length(size_type __length)
132	{ _M_string_length = __length; }
133
134	pointer
135	_M_data() const
136	{ return _M_dataplus._M_p; }
137
138	pointer
139	_M_local_data()
140	{
141	#if __cplusplus >= 201103L
142	return std::pointer_traits<pointer>::pointer_to(*_M_local_buf);
143	#else
144	return pointer(_M_local_buf);
145	#endif
146	}
147
148	const_pointer
149	_M_local_data() const
150	{
151	#if __cplusplus >= 201103L
152	return std::pointer_traits<const_pointer>::pointer_to(*_M_local_buf);
153	#else
154	return const_pointer(_M_local_buf);
155	#endif
156	}
157
158	void
159	_M_capacity(size_type __capacity)
160	{ _M_allocated_capacity = __capacity; }
161
162	void
163	_M_set_length(size_type __n)
164	{
165	_M_length(__n);
166	traits_type::assign(_M_data()[__n], _CharT());
167	}
168
169	bool
170	_M_is_local() const
171	{ return _M_data() == _M_local_data(); }
172
173	// Create & Destroy
174	pointer
175	_M_create(size_type&, size_type);
176
177	void
178	_M_dispose()
179	{
180	if (!_M_is_local())
181	_M_destroy(_M_allocated_capacity);
182	}
183
184	void
185	_M_destroy(size_type __size) throw()
186	{ _Alloc_traits::deallocate(_M_get_allocator(), _M_data(), __size + `1`); }
187
188	// _M_construct_aux is used to implement the 21.3.1 para 15 which
189	// requires special behaviour if _InIterator is an integral type
190	template<typename _InIterator>
191	void
192	_M_construct_aux(_InIterator __beg, _InIterator __end,
193	std::__false_type)
194	{
195	typedef typename iterator_traits<_InIterator>::iterator_category _Tag;
196	_M_construct(__beg, __end, _Tag());
197	}
198
199	// _GLIBCXX_RESOLVE_LIB_DEFECTS
200	// 438. Ambiguity in the "do the right thing" clause
201	template<typename _Integer>
202	void
203	_M_construct_aux(_Integer __beg, _Integer __end, std::__true_type)
204	{ _M_construct_aux_2(static_cast<size_type>(__beg), __end); }
205
206	void
207	_M_construct_aux_2(size_type __req, _CharT __c)
208	{ _M_construct(__req, __c); }
209
210	template<typename _InIterator>
211	void
212	_M_construct(_InIterator __beg, _InIterator __end)
213	{
214	typedef typename std::__is_integer<_InIterator>::__type _Integral;
215	_M_construct_aux(__beg, __end, _Integral());
216	}
217
218	// For Input Iterators, used in istreambuf_iterators, etc.
219	template<typename _InIterator>
220	void
221	_M_construct(_InIterator __beg, _InIterator __end,
222	std::input_iterator_tag);
223
224	// For forward_iterators up to random_access_iterators, used for
225	// string::iterator, _CharT, etc.*
226	template<typename _FwdIterator>
227	void
228	_M_construct(_FwdIterator __beg, _FwdIterator __end,
229	std::forward_iterator_tag);
230
231	void
232	_M_construct(size_type __req, _CharT __c);
233
234	allocator_type&
235	_M_get_allocator()
236	{ return _M_dataplus; }
237
238	const allocator_type&
239	_M_get_allocator() const
240	{ return _M_dataplus; }
241
242	private:
243
244	#ifdef _GLIBCXX_DISAMBIGUATE_REPLACE_INST
245	// The explicit instantiations in misc-inst.cc require this due to
246	// https://gcc.gnu.org/bugzilla/show_bug.cgi?id=64063
247	template<typename _Tp, bool _Requires =
248	!__are_same<_Tp, _CharT*>::__value
249	&& !__are_same<_Tp, const _CharT*>::__value
250	&& !__are_same<_Tp, iterator>::__value
251	&& !__are_same<_Tp, const_iterator>::__value>
252	struct __enable_if_not_native_iterator
253	{ typedef basic_string& __type; };
254	template<typename _Tp>
255	struct __enable_if_not_native_iterator<_Tp, false> { };
256	#endif
257
258	size_type
259	_M_check(size_type __pos, const char* __s) const
260	{
261	if (__pos > this->size())
262	__throw_out_of_range_fmt(__N("%s: __pos (which is %zu) > "
263	"this->size() (which is %zu)"),
264	__s, __pos, this->size());
265	return __pos;
266	}
267
268	void
269	_M_check_length(size_type __n1, size_type __n2, const char* __s) const
270	{
271	if (this->max_size() - (this->size() - __n1) < __n2)
272	__throw_length_error(__N(__s));
273	}
274
275
276	// NB: _M_limit doesn't check for a bad __pos value.
277	size_type
278	_M_limit(size_type __pos, size_type __off) const _GLIBCXX_NOEXCEPT
279	{
280	const bool __testoff = __off < this->size() - __pos;
281	return __testoff ? __off : this->size() - __pos;
282	}
283
284	// True if _Rep and source do not overlap.
285	bool
286	_M_disjunct(const _CharT* __s) const _GLIBCXX_NOEXCEPT
287	{
288	return (less<const _CharT*>()(__s, _M_data())
289	\|\| less<const _CharT>()(_M_data() + this*->size(), __s));
290	}
291
292	// When __n = 1 way faster than the general multichar
293	// traits_type::copy/move/assign.
294	static void
295	_S_copy(_CharT* __d, const _CharT* __s, size_type __n)
296	{
297	if (__n == `1`)
298	traits_type::assign(__d, __s);
299	else
300	traits_type::copy(__d, __s, __n);
301	}
302
303	static void
304	_S_move(_CharT* __d, const _CharT* __s, size_type __n)
305	{
306	if (__n == `1`)
307	traits_type::assign(__d, __s);
308	else
309	traits_type::move(__d, __s, __n);
310	}
311
312	static void
313	_S_assign(_CharT* __d, size_type __n, _CharT __c)
314	{
315	if (__n == `1`)
316	traits_type::assign(*__d, __c);
317	else
318	traits_type::assign(__d, __n, __c);
319	}
320
321	// _S_copy_chars is a separate template to permit specialization
322	// to optimize for the common case of pointers as iterators.
323	template<class _Iterator>
324	static void
325	_S_copy_chars(_CharT* __p, _Iterator __k1, _Iterator __k2)
326	{
327	for (; __k1 != __k2; ++__k1, (void)++__p)
328	traits_type::assign(__p, __k1); // These types are off.
329	}
330
331	static void
332	_S_copy_chars(_CharT* __p, iterator __k1, iterator __k2) _GLIBCXX_NOEXCEPT
333	{ _S_copy_chars(__p, __k1.base(), __k2.base()); }
334
335	static void
336	_S_copy_chars(_CharT* __p, const_iterator __k1, const_iterator __k2)
337	_GLIBCXX_NOEXCEPT
338	{ _S_copy_chars(__p, __k1.base(), __k2.base()); }
339
340	static void
341	_S_copy_chars(_CharT* __p, _CharT* __k1, _CharT* __k2) _GLIBCXX_NOEXCEPT
342	{ _S_copy(__p, __k1, __k2 - __k1); }
343
344	static void
345	_S_copy_chars(_CharT* __p, const _CharT* __k1, const _CharT* __k2)
346	_GLIBCXX_NOEXCEPT
347	{ _S_copy(__p, __k1, __k2 - __k1); }
348
349	static int
350	_S_compare(size_type __n1, size_type __n2) _GLIBCXX_NOEXCEPT
351	{
352	const difference_type __d = difference_type(__n1 - __n2);
353
354	if (__d > __gnu_cxx::__numeric_traits<int>::__max)
355	return __gnu_cxx::__numeric_traits<int>::__max;
356	else if (__d < __gnu_cxx::__numeric_traits<int>::__min)
357	return __gnu_cxx::__numeric_traits<int>::__min;
358	else
359	return int(__d);
360	}
361
362	void
363	_M_assign(const basic_string& __rcs);
364
365	void
366	_M_mutate(size_type __pos, size_type __len1, const _CharT* __s,
367	size_type __len2);
368
369	void
370	_M_erase(size_type __pos, size_type __n);
371
372	public:
373	// Construct/copy/destroy:
374	// NB: We overload ctors in some cases instead of using default
375	// arguments, per 17.4.4.4 para. 2 item 2.
376
377	/**
378	* @brief Default constructor creates an empty string.
379	*/
380	basic_string()
381	_GLIBCXX_NOEXCEPT_IF(is_nothrow_default_constructible<_Alloc>::value)
382	: _M_dataplus(_M_local_data())
383	{ _M_set_length(`0`); }
384
385	/**
386	* @brief Construct an empty string using allocator @a a.
387	*/
388	explicit
389	basic_string(const _Alloc& __a) _GLIBCXX_NOEXCEPT
390	: _M_dataplus(_M_local_data(), __a)
391	{ _M_set_length(`0`); }
392
393	/**
394	* @brief Construct string with copy of value of @a __str.
395	* @param __str Source string.
396	*/
397	basic_string(const basic_string& __str)
398	: _M_dataplus(_M_local_data(),
399	_Alloc_traits::_S_select_on_copy(__str._M_get_allocator()))
400	{ _M_construct(__str._M_data(), __str._M_data() + __str.length()); }
401
402	/**
403	* @brief Construct string as copy of a substring.
404	* @param __str Source string.
405	* @param __pos Index of first character to copy from.
406	* @param __n Number of characters to copy (default remainder).
407	*/
408	// _GLIBCXX_RESOLVE_LIB_DEFECTS
409	// 2402. [this constructor] shouldn't use Allocator()
410	basic_string(const basic_string& __str, size_type __pos,
411	size_type __n = npos)
412	: _M_dataplus(_M_local_data())
413	{
414	const _CharT* __start = __str._M_data()
415	+ __str._M_check(__pos, "basic_string::basic_string");
416	_M_construct(__start, __start + __str._M_limit(__pos, __n));
417	}
418
419	/**
420	* @brief Construct string as copy of a substring.
421	* @param __str Source string.
422	* @param __pos Index of first character to copy from.
423	* @param __n Number of characters to copy (default remainder).
424	* @param __a Allocator to use.
425	*/
426	basic_string(const basic_string& __str, size_type __pos,
427	size_type __n, const _Alloc& __a)
428	: _M_dataplus(_M_local_data(), __a)
429	{
430	const _CharT* __start
431	= __str._M_data() + __str._M_check(__pos, "string::string");
432	_M_construct(__start, __start + __str._M_limit(__pos, __n));
433	}
434
435	/**
436	* @brief Construct string initialized by a character %array.
437	* @param __s Source character %array.
438	* @param __n Number of characters to copy.
439	* @param __a Allocator to use (default is default allocator).
440	*
441	* NB: @a __s must have at least @a __n characters, '\\0'
442	* has no special meaning.
443	*/
444	basic_string(const _CharT* __s, size_type __n,
445	const _Alloc& __a = _Alloc())
446	: _M_dataplus(_M_local_data(), __a)
447	{ _M_construct(__s, __s + __n); }
448
449	/**
450	* @brief Construct string as copy of a C string.
451	* @param __s Source C string.
452	* @param __a Allocator to use (default is default allocator).
453	*/
454	basic_string(const _CharT* __s, const _Alloc& __a = _Alloc())
455	: _M_dataplus(_M_local_data(), __a)
456	{ _M_construct(__s, __s ? __s + traits_type::length(__s) : __s+npos); }
457
458	/**
459	* @brief Construct string as multiple characters.
460	* @param __n Number of characters.
461	* @param __c Character to use.
462	* @param __a Allocator to use (default is default allocator).
463	*/
464	basic_string(size_type __n, _CharT __c, const _Alloc& __a = _Alloc())
465	: _M_dataplus(_M_local_data(), __a)
466	{ _M_construct(__n, __c); }
467
468	#if __cplusplus >= 201103L
469	/**
470	* @brief Move construct string.
471	* @param __str Source string.
472	*
473	* The newly-created string contains the exact contents of @a __str.
474	* @a __str is a valid, but unspecified string.
475	**/
476	basic_string(basic_string&& __str) noexcept
477	: _M_dataplus(_M_local_data(), std::move(__str._M_get_allocator()))
478	{
479	if (__str._M_is_local())
480	{
481	traits_type::copy(_M_local_buf, __str._M_local_buf,
482	_S_local_capacity + `1`);
483	}
484	else
485	{
486	_M_data(__str._M_data());
487	_M_capacity(__str._M_allocated_capacity);
488	}
489
490	// Must use _M_length() here not _M_set_length() because
491	// basic_stringbuf relies on writing into unallocated capacity so
492	// we mess up the contents if we put a '\0' in the string.
493	_M_length(__str.length());
494	__str._M_data(__str._M_local_data());
495	__str._M_set_length(`0`);
496	}
497
498	/**
499	* @brief Construct string from an initializer %list.
500	* @param __l std::initializer_list of characters.
501	* @param __a Allocator to use (default is default allocator).
502	*/
503	basic_string(initializer_list<_CharT> __l, const _Alloc& __a = _Alloc())
504	: _M_dataplus(_M_local_data(), __a)
505	{ _M_construct(__l.begin(), __l.end()); }
506
507	basic_string(const basic_string& __str, const _Alloc& __a)
508	: _M_dataplus(_M_local_data(), __a)
509	{ _M_construct(__str.begin(), __str.end()); }
510
511	basic_string(basic_string&& __str, const _Alloc& __a)
512	noexcept(_Alloc_traits::_S_always_equal())
513	: _M_dataplus(_M_local_data(), __a)
514	{
515	if (__str._M_is_local())
516	{
517	traits_type::copy(_M_local_buf, __str._M_local_buf,
518	_S_local_capacity + `1`);
519	_M_length(__str.length());
520	__str._M_set_length(`0`);
521	}
522	else if (_Alloc_traits::_S_always_equal()
523	\|\| __str.get_allocator() == __a)
524	{
525	_M_data(__str._M_data());
526	_M_length(__str.length());
527	_M_capacity(__str._M_allocated_capacity);
528	__str._M_data(__str._M_local_buf);
529	__str._M_set_length(`0`);
530	}
531	else
532	_M_construct(__str.begin(), __str.end());
533	}
534
535	#endif // C++11
536
537	/**
538	* @brief Construct string as copy of a range.
539	* @param __beg Start of range.
540	* @param __end End of range.
541	* @param __a Allocator to use (default is default allocator).
542	*/
543	#if __cplusplus >= 201103L
544	template<typename _InputIterator,
545	typename = std::_RequireInputIter<_InputIterator>>
546	#else
547	template<typename _InputIterator>
548	#endif
549	basic_string(_InputIterator __beg, _InputIterator __end,
550	const _Alloc& __a = _Alloc())
551	: _M_dataplus(_M_local_data(), __a)
552	{ _M_construct(__beg, __end); }
553
554	/**
555	* @brief Destroy the string instance.
556	*/
557	~basic_string()
558	{ _M_dispose(); }
559
560	/**
561	* @brief Assign the value of @a str to this string.
562	* @param __str Source string.
563	*/
564	basic_string&
565	operator=(const basic_string& __str)
566	{
567	#if __cplusplus >= 201103L
568	if (_Alloc_traits::_S_propagate_on_copy_assign())
569	{
570	if (!_Alloc_traits::_S_always_equal() && !_M_is_local()
571	&& _M_get_allocator() != __str._M_get_allocator())
572	{
573	// Propagating allocator cannot free existing storage so must
574	// deallocate it before replacing current allocator.
575	if (__str.size() <= _S_local_capacity)
576	{
577	_M_destroy(_M_allocated_capacity);
578	_M_data(_M_local_data());
579	_M_set_length(`0`);
580	}
581	else
582	{
583	const auto __len = __str.size();
584	auto __alloc = __str._M_get_allocator();
585	// If this allocation throws there are no effects:
586	auto __ptr = _Alloc_traits::allocate(__alloc, __len + `1`);
587	_M_destroy(_M_allocated_capacity);
588	_M_data(__ptr);
589	_M_capacity(__len);
590	_M_set_length(__len);
591	}
592	}
593	std::__alloc_on_copy(_M_get_allocator(), __str._M_get_allocator());
594	}
595	#endif
596	return this->assign(__str);
597	}
598
599	/**
600	* @brief Copy contents of @a s into this string.
601	* @param __s Source null-terminated string.
602	*/
603	basic_string&
604	operator=(const _CharT* __s)
605	{ return this->assign(__s); }
606
607	/**
608	* @brief Set value to string of length 1.
609	* @param __c Source character.
610	*
611	* Assigning to a character makes this string length 1 and
612	* (*this)[0] == @a c.
613	*/
614	basic_string&
615	operator=(_CharT __c)
616	{
617	this->assign(`1`, __c);
618	return *this;
619	}
620
621	#if __cplusplus >= 201103L
622	/**
623	* @brief Move assign the value of @a str to this string.
624	* @param __str Source string.
625	*
626	* The contents of @a str are moved into this string (without copying).
627	* @a str is a valid, but unspecified string.
628	**/
629	// PR 58265, this should be noexcept.
630	// _GLIBCXX_RESOLVE_LIB_DEFECTS
631	// 2063. Contradictory requirements for string move assignment
632	basic_string&
633	operator=(basic_string&& __str)
634	noexcept(_Alloc_traits::_S_nothrow_move())
635	{
636	if (!_M_is_local() && _Alloc_traits::_S_propagate_on_move_assign()
637	&& !_Alloc_traits::_S_always_equal()
638	&& _M_get_allocator() != __str._M_get_allocator())
639	{
640	// Destroy existing storage before replacing allocator.
641	_M_destroy(_M_allocated_capacity);
642	_M_data(_M_local_data());
643	_M_set_length(`0`);
644	}
645	// Replace allocator if POCMA is true.
646	std::__alloc_on_move(_M_get_allocator(), __str._M_get_allocator());
647
648	if (!__str._M_is_local()
649	&& (_Alloc_traits::_S_propagate_on_move_assign()
650	\|\| _Alloc_traits::_S_always_equal()))
651	{
652	pointer __data = nullptr;
653	size_type __capacity;
654	if (!_M_is_local())
655	{
656	if (_Alloc_traits::_S_always_equal())
657	{
658	__data = _M_data();
659	__capacity = _M_allocated_capacity;
660	}
661	else
662	_M_destroy(_M_allocated_capacity);
663	}
664
665	_M_data(__str._M_data());
666	_M_length(__str.length());
667	_M_capacity(__str._M_allocated_capacity);
668	if (__data)
669	{
670	__str._M_data(__data);
671	__str._M_capacity(__capacity);
672	}
673	else
674	__str._M_data(__str._M_local_buf);
675	}
676	else
677	assign(__str);
678	__str.clear();
679	return *this;
680	}
681
682	/**
683	* @brief Set value to string constructed from initializer %list.
684	* @param __l std::initializer_list.
685	*/
686	basic_string&
687	operator=(initializer_list<_CharT> __l)
688	{
689	this->assign(__l.begin(), __l.size());
690	return *this;
691	}
692	#endif // C++11
693
694	// Iterators:
695	/**
696	* Returns a read/write iterator that points to the first character in
697	* the %string.
698	*/
699	iterator
700	begin() _GLIBCXX_NOEXCEPT
701	{ return iterator(_M_data()); }
702
703	/**
704	* Returns a read-only (constant) iterator that points to the first
705	* character in the %string.
706	*/
707	const_iterator
708	begin() const _GLIBCXX_NOEXCEPT
709	{ return const_iterator(_M_data()); }
710
711	/**
712	* Returns a read/write iterator that points one past the last
713	* character in the %string.
714	*/
715	iterator
716	end() _GLIBCXX_NOEXCEPT
717	{ return iterator(_M_data() + this->size()); }
718
719	/**
720	* Returns a read-only (constant) iterator that points one past the
721	* last character in the %string.
722	*/
723	const_iterator
724	end() const _GLIBCXX_NOEXCEPT
725	{ return const_iterator(_M_data() + this->size()); }
726
727	/**
728	* Returns a read/write reverse iterator that points to the last
729	* character in the %string. Iteration is done in reverse element
730	* order.
731	*/
732	reverse_iterator
733	rbegin() _GLIBCXX_NOEXCEPT
734	{ return reverse_iterator(this->end()); }
735
736	/**
737	* Returns a read-only (constant) reverse iterator that points
738	* to the last character in the %string. Iteration is done in
739	* reverse element order.
740	*/
741	const_reverse_iterator
742	rbegin() const _GLIBCXX_NOEXCEPT
743	{ return const_reverse_iterator(this->end()); }
744
745	/**
746	* Returns a read/write reverse iterator that points to one before the
747	* first character in the %string. Iteration is done in reverse
748	* element order.
749	*/
750	reverse_iterator
751	rend() _GLIBCXX_NOEXCEPT
752	{ return reverse_iterator(this->begin()); }
753
754	/**
755	* Returns a read-only (constant) reverse iterator that points
756	* to one before the first character in the %string. Iteration
757	* is done in reverse element order.
758	*/
759	const_reverse_iterator
760	rend() const _GLIBCXX_NOEXCEPT
761	{ return const_reverse_iterator(this->begin()); }
762
763	#if __cplusplus >= 201103L
764	/**
765	* Returns a read-only (constant) iterator that points to the first
766	* character in the %string.
767	*/
768	const_iterator
769	cbegin() const noexcept
770	{ return const_iterator(this->_M_data()); }
771
772	/**
773	* Returns a read-only (constant) iterator that points one past the
774	* last character in the %string.
775	*/
776	const_iterator
777	cend() const noexcept
778	{ return const_iterator(this->_M_data() + this->size()); }
779
780	/**
781	* Returns a read-only (constant) reverse iterator that points
782	* to the last character in the %string. Iteration is done in
783	* reverse element order.
784	*/
785	const_reverse_iterator
786	crbegin() const noexcept
787	{ return const_reverse_iterator(this->end()); }
788
789	/**
790	* Returns a read-only (constant) reverse iterator that points
791	* to one before the first character in the %string. Iteration
792	* is done in reverse element order.
793	*/
794	const_reverse_iterator
795	crend() const noexcept
796	{ return const_reverse_iterator(this->begin()); }
797	#endif
798
799	public:
800	// Capacity:
801	/// Returns the number of characters in the string, not including any
802	/// null-termination.
803	size_type
804	size() const _GLIBCXX_NOEXCEPT
805	{ return _M_string_length; }
806
807	/// Returns the number of characters in the string, not including any
808	/// null-termination.
809	size_type
810	length() const _GLIBCXX_NOEXCEPT
811	{ return _M_string_length; }
812
813	/// Returns the size() of the largest possible %string.
814	size_type
815	max_size() const _GLIBCXX_NOEXCEPT
816	{ return (_Alloc_traits::max_size(_M_get_allocator()) - `1`) / `2`; }
817
818	/**
819	* @brief Resizes the %string to the specified number of characters.
820	* @param __n Number of characters the %string should contain.
821	* @param __c Character to fill any new elements.
822	*
823	* This function will %resize the %string to the specified
824	* number of characters. If the number is smaller than the
825	* %string's current size the %string is truncated, otherwise
826	* the %string is extended and new elements are %set to @a __c.
827	*/
828	void
829	resize(size_type __n, _CharT __c);
830
831	/**
832	* @brief Resizes the %string to the specified number of characters.
833	* @param __n Number of characters the %string should contain.
834	*
835	* This function will resize the %string to the specified length. If
836	* the new size is smaller than the %string's current size the %string
837	* is truncated, otherwise the %string is extended and new characters
838	* are default-constructed. For basic types such as char, this means
839	* setting them to 0.
840	*/
841	void
842	resize(size_type __n)
843	{ this->resize(__n, _CharT()); }
844
845	#if __cplusplus >= 201103L
846	/// A non-binding request to reduce capacity() to size().
847	void
848	shrink_to_fit() noexcept
849	{
850	#if __cpp_exceptions
851	if (capacity() > size())
852	{
853	try
854	{ reserve(`0`); }
855	catch(...)
856	{ }
857	}
858	#endif
859	}
860	#endif
861
862	/**
863	* Returns the total number of characters that the %string can hold
864	* before needing to allocate more memory.
865	*/
866	size_type
867	capacity() const _GLIBCXX_NOEXCEPT
868	{
869	return _M_is_local() ? size_type(_S_local_capacity)
870	: _M_allocated_capacity;
871	}
872
873	/**
874	* @brief Attempt to preallocate enough memory for specified number of
875	* characters.
876	* @param __res_arg Number of characters required.
877	* @throw std::length_error If @a __res_arg exceeds @c max_size().
878	*
879	* This function attempts to reserve enough memory for the
880	* %string to hold the specified number of characters. If the
881	* number requested is more than max_size(), length_error is
882	* thrown.
883	*
884	* The advantage of this function is that if optimal code is a
885	* necessity and the user can determine the string length that will be
886	* required, the user can reserve the memory in %advance, and thus
887	* prevent a possible reallocation of memory and copying of %string
888	* data.
889	*/
890	void
891	reserve(size_type __res_arg = `0`);
892
893	/**
894	* Erases the string, making it empty.
895	*/
896	void
897	clear() _GLIBCXX_NOEXCEPT
898	{ _M_set_length(`0`); }
899
900	/**
901	* Returns true if the %string is empty. Equivalent to
902	* <code>*this == ""</code>.
903	*/
904	bool
905	empty() const _GLIBCXX_NOEXCEPT
906	{ return this->size() == `0`; }
907
908	// Element access:
909	/**
910	* @brief Subscript access to the data contained in the %string.
911	* @param __pos The index of the character to access.
912	* @return Read-only (constant) reference to the character.
913	*
914	* This operator allows for easy, array-style, data access.
915	* Note that data access with this operator is unchecked and
916	* out_of_range lookups are not defined. (For checked lookups
917	* see at().)
918	*/
919	const_reference
920	operator[] (size_type __pos) const _GLIBCXX_NOEXCEPT
921	{
922	__glibcxx_assert(__pos <= size());
923	return _M_data()[__pos];
924	}
925
926	/**
927	* @brief Subscript access to the data contained in the %string.
928	* @param __pos The index of the character to access.
929	* @return Read/write reference to the character.
930	*
931	* This operator allows for easy, array-style, data access.
932	* Note that data access with this operator is unchecked and
933	* out_of_range lookups are not defined. (For checked lookups
934	* see at().)
935	*/
936	reference
937	operator[](size_type __pos)
938	{
939	// Allow pos == size() both in C++98 mode, as v3 extension,
940	// and in C++11 mode.
941	__glibcxx_assert(__pos <= size());
942	// In pedantic mode be strict in C++98 mode.
943	_GLIBCXX_DEBUG_PEDASSERT(__cplusplus >= `201103L` \|\| __pos < size());
944	return _M_data()[__pos];
945	}
946
947	/**
948	* @brief Provides access to the data contained in the %string.
949	* @param __n The index of the character to access.
950	* @return Read-only (const) reference to the character.
951	* @throw std::out_of_range If @a n is an invalid index.
952	*
953	* This function provides for safer data access. The parameter is
954	* first checked that it is in the range of the string. The function
955	* throws out_of_range if the check fails.
956	*/
957	const_reference
958	at(size_type __n) const
959	{
960	if (__n >= this->size())
961	__throw_out_of_range_fmt(__N("basic_string::at: __n "
962	"(which is %zu) >= this->size() "
963	"(which is %zu)"),
964	__n, this->size());
965	return _M_data()[__n];
966	}
967
968	/**
969	* @brief Provides access to the data contained in the %string.
970	* @param __n The index of the character to access.
971	* @return Read/write reference to the character.
972	* @throw std::out_of_range If @a n is an invalid index.
973	*
974	* This function provides for safer data access. The parameter is
975	* first checked that it is in the range of the string. The function
976	* throws out_of_range if the check fails.
977	*/
978	reference
979	at(size_type __n)
980	{
981	if (__n >= size())
982	__throw_out_of_range_fmt(__N("basic_string::at: __n "
983	"(which is %zu) >= this->size() "
984	"(which is %zu)"),
985	__n, this->size());
986	return _M_data()[__n];
987	}
988
989	#if __cplusplus >= 201103L
990	/**
991	* Returns a read/write reference to the data at the first
992	* element of the %string.
993	*/
994	reference
995	front() noexcept
996	{
997	__glibcxx_assert(!empty());
998	return operator[](`0`);
999	}
1000
1001	/**
1002	* Returns a read-only (constant) reference to the data at the first
1003	* element of the %string.
1004	*/
1005	const_reference
1006	front() const noexcept
1007	{
1008	__glibcxx_assert(!empty());
1009	return operator[](`0`);
1010	}
1011
1012	/**
1013	* Returns a read/write reference to the data at the last
1014	* element of the %string.
1015	*/
1016	reference
1017	back() noexcept
1018	{
1019	__glibcxx_assert(!empty());
1020	return operator[](this->size() - `1`);
1021	}
1022
1023	/**
1024	* Returns a read-only (constant) reference to the data at the
1025	* last element of the %string.
1026	*/
1027	const_reference
1028	back() const noexcept
1029	{
1030	__glibcxx_assert(!empty());
1031	return operator[](this->size() - `1`);
1032	}
1033	#endif
1034
1035	// Modifiers:
1036	/**
1037	* @brief Append a string to this string.
1038	* @param __str The string to append.
1039	* @return Reference to this string.
1040	*/
1041	basic_string&
1042	operator+=(const basic_string& __str)
1043	{ return this->append(__str); }
1044
1045	/**
1046	* @brief Append a C string.
1047	* @param __s The C string to append.
1048	* @return Reference to this string.
1049	*/
1050	basic_string&
1051	operator+=(const _CharT* __s)
1052	{ return this->append(__s); }
1053
1054	/**
1055	* @brief Append a character.
1056	* @param __c The character to append.
1057	* @return Reference to this string.
1058	*/
1059	basic_string&
1060	operator+=(_CharT __c)
1061	{
1062	this->push_back(__c);
1063	return *this;
1064	}
1065
1066	#if __cplusplus >= 201103L
1067	/**
1068	* @brief Append an initializer_list of characters.
1069	* @param __l The initializer_list of characters to be appended.
1070	* @return Reference to this string.
1071	*/
1072	basic_string&
1073	operator+=(initializer_list<_CharT> __l)
1074	{ return this->append(__l.begin(), __l.size()); }
1075	#endif // C++11
1076
1077	/**
1078	* @brief Append a string to this string.
1079	* @param __str The string to append.
1080	* @return Reference to this string.
1081	*/
1082	basic_string&
1083	append(const basic_string& __str)
1084	{ return _M_append(__str._M_data(), __str.size()); }
1085
1086	/**
1087	* @brief Append a substring.
1088	* @param __str The string to append.
1089	* @param __pos Index of the first character of str to append.
1090	* @param __n The number of characters to append.
1091	* @return Reference to this string.
1092	* @throw std::out_of_range if @a __pos is not a valid index.
1093	*
1094	* This function appends @a __n characters from @a __str
1095	* starting at @a __pos to this string. If @a __n is is larger
1096	* than the number of available characters in @a __str, the
1097	* remainder of @a __str is appended.
1098	*/
1099	basic_string&
1100	append(const basic_string& __str, size_type __pos, size_type __n)
1101	{ return _M_append(__str._M_data()
1102	+ __str._M_check(__pos, "basic_string::append"),
1103	__str._M_limit(__pos, __n)); }
1104
1105	/**
1106	* @brief Append a C substring.
1107	* @param __s The C string to append.
1108	* @param __n The number of characters to append.
1109	* @return Reference to this string.
1110	*/
1111	basic_string&
1112	append(const _CharT* __s, size_type __n)
1113	{
1114	__glibcxx_requires_string_len(__s, __n);
1115	_M_check_length(size_type(`0`), __n, "basic_string::append");
1116	return _M_append(__s, __n);
1117	}
1118
1119	/**
1120	* @brief Append a C string.
1121	* @param __s The C string to append.
1122	* @return Reference to this string.
1123	*/
1124	basic_string&
1125	append(const _CharT* __s)
1126	{
1127	__glibcxx_requires_string(__s);
1128	const size_type __n = traits_type::length(__s);
1129	_M_check_length(size_type(`0`), __n, "basic_string::append");
1130	return _M_append(__s, __n);
1131	}
1132
1133	/**
1134	* @brief Append multiple characters.
1135	* @param __n The number of characters to append.
1136	* @param __c The character to use.
1137	* @return Reference to this string.
1138	*
1139	* Appends __n copies of __c to this string.
1140	*/
1141	basic_string&
1142	append(size_type __n, _CharT __c)
1143	{ return _M_replace_aux(this->size(), size_type(`0`), __n, __c); }
1144
1145	#if __cplusplus >= 201103L
1146	/**
1147	* @brief Append an initializer_list of characters.
1148	* @param __l The initializer_list of characters to append.
1149	* @return Reference to this string.
1150	*/
1151	basic_string&
1152	append(initializer_list<_CharT> __l)
1153	{ return this->append(__l.begin(), __l.size()); }
1154	#endif // C++11
1155
1156	/**
1157	* @brief Append a range of characters.
1158	* @param __first Iterator referencing the first character to append.
1159	* @param __last Iterator marking the end of the range.
1160	* @return Reference to this string.
1161	*
1162	* Appends characters in the range [__first,__last) to this string.
1163	*/
1164	#if __cplusplus >= 201103L
1165	template<class _InputIterator,
1166	typename = std::_RequireInputIter<_InputIterator>>
1167	#else
1168	template<class _InputIterator>
1169	#endif
1170	basic_string&
1171	append(_InputIterator __first, _InputIterator __last)
1172	{ return this->replace(end(), end(), __first, __last); }
1173
1174	/**
1175	* @brief Append a single character.
1176	* @param __c Character to append.
1177	*/
1178	void
1179	push_back(_CharT __c)
1180	{
1181	const size_type __size = this->size();
1182	if (__size + `1` > this->capacity())
1183	this->_M_mutate(__size, size_type(`0`), `0`, size_type(`1`));
1184	traits_type::assign(this->_M_data()[__size], __c);
1185	this->_M_set_length(__size + `1`);
1186	}
1187
1188	/**
1189	* @brief Set value to contents of another string.
1190	* @param __str Source string to use.
1191	* @return Reference to this string.
1192	*/
1193	basic_string&
1194	assign(const basic_string& __str)
1195	{
1196	this->_M_assign(__str);
1197	return *this;
1198	}
1199
1200	#if __cplusplus >= 201103L
1201	/**
1202	* @brief Set value to contents of another string.
1203	* @param __str Source string to use.
1204	* @return Reference to this string.
1205	*
1206	* This function sets this string to the exact contents of @a __str.
1207	* @a __str is a valid, but unspecified string.
1208	*/
1209	basic_string&
1210	assign(basic_string&& __str)
1211	noexcept(_Alloc_traits::_S_nothrow_move())
1212	{
1213	// _GLIBCXX_RESOLVE_LIB_DEFECTS
1214	// 2063. Contradictory requirements for string move assignment
1215	return *this = std::move(__str);
1216	}
1217	#endif // C++11
1218
1219	/**
1220	* @brief Set value to a substring of a string.
1221	* @param __str The string to use.
1222	* @param __pos Index of the first character of str.
1223	* @param __n Number of characters to use.
1224	* @return Reference to this string.
1225	* @throw std::out_of_range if @a pos is not a valid index.
1226	*
1227	* This function sets this string to the substring of @a __str
1228	* consisting of @a __n characters at @a __pos. If @a __n is
1229	* is larger than the number of available characters in @a
1230	* __str, the remainder of @a __str is used.
1231	*/
1232	basic_string&
1233	assign(const basic_string& __str, size_type __pos, size_type __n)
1234	{ return _M_replace(size_type(`0`), this->size(), __str._M_data()
1235	+ __str._M_check(__pos, "basic_string::assign"),
1236	__str._M_limit(__pos, __n)); }
1237
1238	/**
1239	* @brief Set value to a C substring.
1240	* @param __s The C string to use.
1241	* @param __n Number of characters to use.
1242	* @return Reference to this string.
1243	*
1244	* This function sets the value of this string to the first @a __n
1245	* characters of @a __s. If @a __n is is larger than the number of
1246	* available characters in @a __s, the remainder of @a __s is used.
1247	*/
1248	basic_string&
1249	assign(const _CharT* __s, size_type __n)
1250	{
1251	__glibcxx_requires_string_len(__s, __n);
1252	return _M_replace(size_type(`0`), this->size(), __s, __n);
1253	}
1254
1255	/**
1256	* @brief Set value to contents of a C string.
1257	* @param __s The C string to use.
1258	* @return Reference to this string.
1259	*
1260	* This function sets the value of this string to the value of @a __s.
1261	* The data is copied, so there is no dependence on @a __s once the
1262	* function returns.
1263	*/
1264	basic_string&
1265	assign(const _CharT* __s)
1266	{
1267	__glibcxx_requires_string(__s);
1268	return _M_replace(size_type(`0`), this->size(), __s,
1269	traits_type::length(__s));
1270	}
1271
1272	/**
1273	* @brief Set value to multiple characters.
1274	* @param __n Length of the resulting string.
1275	* @param __c The character to use.
1276	* @return Reference to this string.
1277	*
1278	* This function sets the value of this string to @a __n copies of
1279	* character @a __c.
1280	*/
1281	basic_string&
1282	assign(size_type __n, _CharT __c)
1283	{ return _M_replace_aux(size_type(`0`), this->size(), __n, __c); }
1284
1285	/**
1286	* @brief Set value to a range of characters.
1287	* @param __first Iterator referencing the first character to append.
1288	* @param __last Iterator marking the end of the range.
1289	* @return Reference to this string.
1290	*
1291	* Sets value of string to characters in the range [__first,__last).
1292	*/
1293	#if __cplusplus >= 201103L
1294	template<class _InputIterator,
1295	typename = std::_RequireInputIter<_InputIterator>>
1296	#else
1297	template<class _InputIterator>
1298	#endif
1299	basic_string&
1300	assign(_InputIterator __first, _InputIterator __last)
1301	{ return this->replace(begin(), end(), __first, __last); }
1302
1303	#if __cplusplus >= 201103L
1304	/**
1305	* @brief Set value to an initializer_list of characters.
1306	* @param __l The initializer_list of characters to assign.
1307	* @return Reference to this string.
1308	*/
1309	basic_string&
1310	assign(initializer_list<_CharT> __l)
1311	{ return this->assign(__l.begin(), __l.size()); }
1312	#endif // C++11
1313
1314	#if __cplusplus >= 201103L
1315	/**
1316	* @brief Insert multiple characters.
1317	* @param __p Const_iterator referencing location in string to
1318	* insert at.
1319	* @param __n Number of characters to insert
1320	* @param __c The character to insert.
1321	* @return Iterator referencing the first inserted char.
1322	* @throw std::length_error If new length exceeds @c max_size().
1323	*
1324	* Inserts @a __n copies of character @a __c starting at the
1325	* position referenced by iterator @a __p. If adding
1326	* characters causes the length to exceed max_size(),
1327	* length_error is thrown. The value of the string doesn't
1328	* change if an error is thrown.
1329	*/
1330	iterator
1331	insert(const_iterator __p, size_type __n, _CharT __c)
1332	{
1333	_GLIBCXX_DEBUG_PEDASSERT(__p >= begin() && __p <= end());
1334	const size_type __pos = __p - begin();
1335	this->replace(__p, __p, __n, __c);
1336	return iterator(this->_M_data() + __pos);
1337	}
1338	#else
1339	/**
1340	* @brief Insert multiple characters.
1341	* @param __p Iterator referencing location in string to insert at.
1342	* @param __n Number of characters to insert
1343	* @param __c The character to insert.
1344	* @throw std::length_error If new length exceeds @c max_size().
1345	*
1346	* Inserts @a __n copies of character @a __c starting at the
1347	* position referenced by iterator @a __p. If adding
1348	* characters causes the length to exceed max_size(),
1349	* length_error is thrown. The value of the string doesn't
1350	* change if an error is thrown.
1351	*/
1352	void
1353	insert(iterator __p, size_type __n, _CharT __c)
1354	{ this->replace(__p, __p, __n, __c); }
1355	#endif
1356
1357	#if __cplusplus >= 201103L
1358	/**
1359	* @brief Insert a range of characters.
1360	* @param __p Const_iterator referencing location in string to
1361	* insert at.
1362	* @param __beg Start of range.
1363	* @param __end End of range.
1364	* @return Iterator referencing the first inserted char.
1365	* @throw std::length_error If new length exceeds @c max_size().
1366	*
1367	* Inserts characters in range [beg,end). If adding characters
1368	* causes the length to exceed max_size(), length_error is
1369	* thrown. The value of the string doesn't change if an error
1370	* is thrown.
1371	*/
1372	template<class _InputIterator,
1373	typename = std::_RequireInputIter<_InputIterator>>
1374	iterator
1375	insert(const_iterator __p, _InputIterator __beg, _InputIterator __end)
1376	{
1377	_GLIBCXX_DEBUG_PEDASSERT(__p >= begin() && __p <= end());
1378	const size_type __pos = __p - begin();
1379	this->replace(__p, __p, __beg, __end);
1380	return iterator(this->_M_data() + __pos);
1381	}
1382	#else
1383	/**
1384	* @brief Insert a range of characters.
1385	* @param __p Iterator referencing location in string to insert at.
1386	* @param __beg Start of range.
1387	* @param __end End of range.
1388	* @throw std::length_error If new length exceeds @c max_size().
1389	*
1390	* Inserts characters in range [__beg,__end). If adding
1391	* characters causes the length to exceed max_size(),
1392	* length_error is thrown. The value of the string doesn't
1393	* change if an error is thrown.
1394	*/
1395	template<class _InputIterator>
1396	void
1397	insert(iterator __p, _InputIterator __beg, _InputIterator __end)
1398	{ this->replace(__p, __p, __beg, __end); }
1399	#endif
1400
1401	#if __cplusplus >= 201103L
1402	/**
1403	* @brief Insert an initializer_list of characters.
1404	* @param __p Iterator referencing location in string to insert at.
1405	* @param __l The initializer_list of characters to insert.
1406	* @throw std::length_error If new length exceeds @c max_size().
1407	*/
1408	void
1409	insert(iterator __p, initializer_list<_CharT> __l)
1410	{
1411	_GLIBCXX_DEBUG_PEDASSERT(__p >= begin() && __p <= end());
1412	this->insert(__p - begin(), __l.begin(), __l.size());
1413	}
1414	#endif // C++11
1415
1416	/**
1417	* @brief Insert value of a string.
1418	* @param __pos1 Iterator referencing location in string to insert at.
1419	* @param __str The string to insert.
1420	* @return Reference to this string.
1421	* @throw std::length_error If new length exceeds @c max_size().
1422	*
1423	* Inserts value of @a __str starting at @a __pos1. If adding
1424	* characters causes the length to exceed max_size(),
1425	* length_error is thrown. The value of the string doesn't
1426	* change if an error is thrown.
1427	*/
1428	basic_string&
1429	insert(size_type __pos1, const basic_string& __str)
1430	{ return this->replace(__pos1, size_type(`0`),
1431	__str._M_data(), __str.size()); }
1432
1433	/**
1434	* @brief Insert a substring.
1435	* @param __pos1 Iterator referencing location in string to insert at.
1436	* @param __str The string to insert.
1437	* @param __pos2 Start of characters in str to insert.
1438	* @param __n Number of characters to insert.
1439	* @return Reference to this string.
1440	* @throw std::length_error If new length exceeds @c max_size().
1441	* @throw std::out_of_range If @a pos1 > size() or
1442	* @a __pos2 > @a str.size().
1443	*
1444	* Starting at @a pos1, insert @a __n character of @a __str
1445	* beginning with @a __pos2. If adding characters causes the
1446	* length to exceed max_size(), length_error is thrown. If @a
1447	* __pos1 is beyond the end of this string or @a __pos2 is
1448	* beyond the end of @a __str, out_of_range is thrown. The
1449	* value of the string doesn't change if an error is thrown.
1450	*/
1451	basic_string&
1452	insert(size_type __pos1, const basic_string& __str,
1453	size_type __pos2, size_type __n)
1454	{ return this->replace(__pos1, size_type(`0`), __str._M_data()
1455	+ __str._M_check(__pos2, "basic_string::insert"),
1456	__str._M_limit(__pos2, __n)); }
1457
1458	/**
1459	* @brief Insert a C substring.
1460	* @param __pos Iterator referencing location in string to insert at.
1461	* @param __s The C string to insert.
1462	* @param __n The number of characters to insert.
1463	* @return Reference to this string.
1464	* @throw std::length_error If new length exceeds @c max_size().
1465	* @throw std::out_of_range If @a __pos is beyond the end of this
1466	* string.
1467	*
1468	* Inserts the first @a __n characters of @a __s starting at @a
1469	* __pos. If adding characters causes the length to exceed
1470	* max_size(), length_error is thrown. If @a __pos is beyond
1471	* end(), out_of_range is thrown. The value of the string
1472	* doesn't change if an error is thrown.
1473	*/
1474	basic_string&
1475	insert(size_type __pos, const _CharT* __s, size_type __n)
1476	{ return this->replace(__pos, size_type(`0`), __s, __n); }
1477
1478	/**
1479	* @brief Insert a C string.
1480	* @param __pos Iterator referencing location in string to insert at.
1481	* @param __s The C string to insert.
1482	* @return Reference to this string.
1483	* @throw std::length_error If new length exceeds @c max_size().
1484	* @throw std::out_of_range If @a pos is beyond the end of this
1485	* string.
1486	*
1487	* Inserts the first @a n characters of @a __s starting at @a __pos. If
1488	* adding characters causes the length to exceed max_size(),
1489	* length_error is thrown. If @a __pos is beyond end(), out_of_range is
1490	* thrown. The value of the string doesn't change if an error is
1491	* thrown.
1492	*/
1493	basic_string&
1494	insert(size_type __pos, const _CharT* __s)
1495	{
1496	__glibcxx_requires_string(__s);
1497	return this->replace(__pos, size_type(`0`), __s,
1498	traits_type::length(__s));
1499	}
1500
1501	/**
1502	* @brief Insert multiple characters.
1503	* @param __pos Index in string to insert at.
1504	* @param __n Number of characters to insert
1505	* @param __c The character to insert.
1506	* @return Reference to this string.
1507	* @throw std::length_error If new length exceeds @c max_size().
1508	* @throw std::out_of_range If @a __pos is beyond the end of this
1509	* string.
1510	*
1511	* Inserts @a __n copies of character @a __c starting at index
1512	* @a __pos. If adding characters causes the length to exceed
1513	* max_size(), length_error is thrown. If @a __pos > length(),
1514	* out_of_range is thrown. The value of the string doesn't
1515	* change if an error is thrown.
1516	*/
1517	basic_string&
1518	insert(size_type __pos, size_type __n, _CharT __c)
1519	{ return _M_replace_aux(_M_check(__pos, "basic_string::insert"),
1520	size_type(`0`), __n, __c); }
1521
1522	/**
1523	* @brief Insert one character.
1524	* @param __p Iterator referencing position in string to insert at.
1525	* @param __c The character to insert.
1526	* @return Iterator referencing newly inserted char.
1527	* @throw std::length_error If new length exceeds @c max_size().
1528	*
1529	* Inserts character @a __c at position referenced by @a __p.
1530	* If adding character causes the length to exceed max_size(),
1531	* length_error is thrown. If @a __p is beyond end of string,
1532	* out_of_range is thrown. The value of the string doesn't
1533	* change if an error is thrown.
1534	*/
1535	iterator
1536	insert(__const_iterator __p, _CharT __c)
1537	{
1538	_GLIBCXX_DEBUG_PEDASSERT(__p >= begin() && __p <= end());
1539	const size_type __pos = __p - begin();
1540	_M_replace_aux(__pos, size_type(`0`), size_type(`1`), __c);
1541	return iterator(_M_data() + __pos);
1542	}
1543
1544	/**
1545	* @brief Remove characters.
1546	* @param __pos Index of first character to remove (default 0).
1547	* @param __n Number of characters to remove (default remainder).
1548	* @return Reference to this string.
1549	* @throw std::out_of_range If @a pos is beyond the end of this
1550	* string.
1551	*
1552	* Removes @a __n characters from this string starting at @a
1553	* __pos. The length of the string is reduced by @a __n. If
1554	* there are < @a __n characters to remove, the remainder of
1555	* the string is truncated. If @a __p is beyond end of string,
1556	* out_of_range is thrown. The value of the string doesn't
1557	* change if an error is thrown.
1558	*/
1559	basic_string&
1560	erase(size_type __pos = `0`, size_type __n = npos)
1561	{
1562	this->_M_erase(_M_check(__pos, "basic_string::erase"),
1563	_M_limit(__pos, __n));
1564	return *this;
1565	}
1566
1567	/**
1568	* @brief Remove one character.
1569	* @param __position Iterator referencing the character to remove.
1570	* @return iterator referencing same location after removal.
1571	*
1572	* Removes the character at @a __position from this string. The value
1573	* of the string doesn't change if an error is thrown.
1574	*/
1575	iterator
1576	erase(__const_iterator __position)
1577	{
1578	_GLIBCXX_DEBUG_PEDASSERT(__position >= begin()
1579	&& __position < end());
1580	const size_type __pos = __position - begin();
1581	this->_M_erase(__pos, size_type(`1`));
1582	return iterator(_M_data() + __pos);
1583	}
1584
1585	/**
1586	* @brief Remove a range of characters.
1587	* @param __first Iterator referencing the first character to remove.
1588	* @param __last Iterator referencing the end of the range.
1589	* @return Iterator referencing location of first after removal.
1590	*
1591	* Removes the characters in the range [first,last) from this string.
1592	* The value of the string doesn't change if an error is thrown.
1593	*/
1594	iterator
1595	erase(__const_iterator __first, __const_iterator __last)
1596	{
1597	_GLIBCXX_DEBUG_PEDASSERT(__first >= begin() && __first <= __last
1598	&& __last <= end());
1599	const size_type __pos = __first - begin();
1600	this->_M_erase(__pos, __last - __first);
1601	return iterator(this->_M_data() + __pos);
1602	}
1603
1604	#if __cplusplus >= 201103L
1605	/**
1606	* @brief Remove the last character.
1607	*
1608	* The string must be non-empty.
1609	*/
1610	void
1611	pop_back() noexcept
1612	{
1613	__glibcxx_assert(!empty());
1614	_M_erase(size() - `1`, `1`);
1615	}
1616	#endif // C++11
1617
1618	/**
1619	* @brief Replace characters with value from another string.
1620	* @param __pos Index of first character to replace.
1621	* @param __n Number of characters to be replaced.
1622	* @param __str String to insert.
1623	* @return Reference to this string.
1624	* @throw std::out_of_range If @a pos is beyond the end of this
1625	* string.
1626	* @throw std::length_error If new length exceeds @c max_size().
1627	*
1628	* Removes the characters in the range [__pos,__pos+__n) from
1629	* this string. In place, the value of @a __str is inserted.
1630	* If @a __pos is beyond end of string, out_of_range is thrown.
1631	* If the length of the result exceeds max_size(), length_error
1632	* is thrown. The value of the string doesn't change if an
1633	* error is thrown.
1634	*/
1635	basic_string&
1636	replace(size_type __pos, size_type __n, const basic_string& __str)
1637	{ return this->replace(__pos, __n, __str._M_data(), __str.size()); }
1638
1639	/**
1640	* @brief Replace characters with value from another string.
1641	* @param __pos1 Index of first character to replace.
1642	* @param __n1 Number of characters to be replaced.
1643	* @param __str String to insert.
1644	* @param __pos2 Index of first character of str to use.
1645	* @param __n2 Number of characters from str to use.
1646	* @return Reference to this string.
1647	* @throw std::out_of_range If @a __pos1 > size() or @a __pos2 >
1648	* __str.size().
1649	* @throw std::length_error If new length exceeds @c max_size().
1650	*
1651	* Removes the characters in the range [__pos1,__pos1 + n) from this
1652	* string. In place, the value of @a __str is inserted. If @a __pos is
1653	* beyond end of string, out_of_range is thrown. If the length of the
1654	* result exceeds max_size(), length_error is thrown. The value of the
1655	* string doesn't change if an error is thrown.
1656	*/
1657	basic_string&
1658	replace(size_type __pos1, size_type __n1, const basic_string& __str,
1659	size_type __pos2, size_type __n2)
1660	{ return this->replace(__pos1, __n1, __str._M_data()
1661	+ __str._M_check(__pos2, "basic_string::replace"),
1662	__str._M_limit(__pos2, __n2)); }
1663
1664	/**
1665	* @brief Replace characters with value of a C substring.
1666	* @param __pos Index of first character to replace.
1667	* @param __n1 Number of characters to be replaced.
1668	* @param __s C string to insert.
1669	* @param __n2 Number of characters from @a s to use.
1670	* @return Reference to this string.
1671	* @throw std::out_of_range If @a pos1 > size().
1672	* @throw std::length_error If new length exceeds @c max_size().
1673	*
1674	* Removes the characters in the range [__pos,__pos + __n1)
1675	* from this string. In place, the first @a __n2 characters of
1676	* @a __s are inserted, or all of @a __s if @a __n2 is too large. If
1677	* @a __pos is beyond end of string, out_of_range is thrown. If
1678	* the length of result exceeds max_size(), length_error is
1679	* thrown. The value of the string doesn't change if an error
1680	* is thrown.
1681	*/
1682	basic_string&
1683	replace(size_type __pos, size_type __n1, const _CharT* __s,
1684	size_type __n2)
1685	{
1686	__glibcxx_requires_string_len(__s, __n2);
1687	return _M_replace(_M_check(__pos, "basic_string::replace"),
1688	_M_limit(__pos, __n1), __s, __n2);
1689	}
1690
1691	/**
1692	* @brief Replace characters with value of a C string.
1693	* @param __pos Index of first character to replace.
1694	* @param __n1 Number of characters to be replaced.
1695	* @param __s C string to insert.
1696	* @return Reference to this string.
1697	* @throw std::out_of_range If @a pos > size().
1698	* @throw std::length_error If new length exceeds @c max_size().
1699	*
1700	* Removes the characters in the range [__pos,__pos + __n1)
1701	* from this string. In place, the characters of @a __s are
1702	* inserted. If @a __pos is beyond end of string, out_of_range
1703	* is thrown. If the length of result exceeds max_size(),
1704	* length_error is thrown. The value of the string doesn't
1705	* change if an error is thrown.
1706	*/
1707	basic_string&
1708	replace(size_type __pos, size_type __n1, const _CharT* __s)
1709	{
1710	__glibcxx_requires_string(__s);
1711	return this->replace(__pos, __n1, __s, traits_type::length(__s));
1712	}
1713
1714	/**
1715	* @brief Replace characters with multiple characters.
1716	* @param __pos Index of first character to replace.
1717	* @param __n1 Number of characters to be replaced.
1718	* @param __n2 Number of characters to insert.
1719	* @param __c Character to insert.
1720	* @return Reference to this string.
1721	* @throw std::out_of_range If @a __pos > size().
1722	* @throw std::length_error If new length exceeds @c max_size().
1723	*
1724	* Removes the characters in the range [pos,pos + n1) from this
1725	* string. In place, @a __n2 copies of @a __c are inserted.
1726	* If @a __pos is beyond end of string, out_of_range is thrown.
1727	* If the length of result exceeds max_size(), length_error is
1728	* thrown. The value of the string doesn't change if an error
1729	* is thrown.
1730	*/
1731	basic_string&
1732	replace(size_type __pos, size_type __n1, size_type __n2, _CharT __c)
1733	{ return _M_replace_aux(_M_check(__pos, "basic_string::replace"),
1734	_M_limit(__pos, __n1), __n2, __c); }
1735
1736	/**
1737	* @brief Replace range of characters with string.
1738	* @param __i1 Iterator referencing start of range to replace.
1739	* @param __i2 Iterator referencing end of range to replace.
1740	* @param __str String value to insert.
1741	* @return Reference to this string.
1742	* @throw std::length_error If new length exceeds @c max_size().
1743	*
1744	* Removes the characters in the range [__i1,__i2). In place,
1745	* the value of @a __str is inserted. If the length of result
1746	* exceeds max_size(), length_error is thrown. The value of
1747	* the string doesn't change if an error is thrown.
1748	*/
1749	basic_string&
1750	replace(__const_iterator __i1, __const_iterator __i2,
1751	const basic_string& __str)
1752	{ return this->replace(__i1, __i2, __str._M_data(), __str.size()); }
1753
1754	/**
1755	* @brief Replace range of characters with C substring.
1756	* @param __i1 Iterator referencing start of range to replace.
1757	* @param __i2 Iterator referencing end of range to replace.
1758	* @param __s C string value to insert.
1759	* @param __n Number of characters from s to insert.
1760	* @return Reference to this string.
1761	* @throw std::length_error If new length exceeds @c max_size().
1762	*
1763	* Removes the characters in the range [__i1,__i2). In place,
1764	* the first @a __n characters of @a __s are inserted. If the
1765	* length of result exceeds max_size(), length_error is thrown.
1766	* The value of the string doesn't change if an error is
1767	* thrown.
1768	*/
1769	basic_string&
1770	replace(__const_iterator __i1, __const_iterator __i2,
1771	const _CharT* __s, size_type __n)
1772	{
1773	_GLIBCXX_DEBUG_PEDASSERT(begin() <= __i1 && __i1 <= __i2
1774	&& __i2 <= end());
1775	return this->replace(__i1 - begin(), __i2 - __i1, __s, __n);
1776	}
1777
1778	/**
1779	* @brief Replace range of characters with C string.
1780	* @param __i1 Iterator referencing start of range to replace.
1781	* @param __i2 Iterator referencing end of range to replace.
1782	* @param __s C string value to insert.
1783	* @return Reference to this string.
1784	* @throw std::length_error If new length exceeds @c max_size().
1785	*
1786	* Removes the characters in the range [__i1,__i2). In place,
1787	* the characters of @a __s are inserted. If the length of
1788	* result exceeds max_size(), length_error is thrown. The
1789	* value of the string doesn't change if an error is thrown.
1790	*/
1791	basic_string&
1792	replace(__const_iterator __i1, __const_iterator __i2, const _CharT* __s)
1793	{
1794	__glibcxx_requires_string(__s);
1795	return this->replace(__i1, __i2, __s, traits_type::length(__s));
1796	}
1797
1798	/**
1799	* @brief Replace range of characters with multiple characters
1800	* @param __i1 Iterator referencing start of range to replace.
1801	* @param __i2 Iterator referencing end of range to replace.
1802	* @param __n Number of characters to insert.
1803	* @param __c Character to insert.
1804	* @return Reference to this string.
1805	* @throw std::length_error If new length exceeds @c max_size().
1806	*
1807	* Removes the characters in the range [__i1,__i2). In place,
1808	* @a __n copies of @a __c are inserted. If the length of
1809	* result exceeds max_size(), length_error is thrown. The
1810	* value of the string doesn't change if an error is thrown.
1811	*/
1812	basic_string&
1813	replace(__const_iterator __i1, __const_iterator __i2, size_type __n,
1814	_CharT __c)
1815	{
1816	_GLIBCXX_DEBUG_PEDASSERT(begin() <= __i1 && __i1 <= __i2
1817	&& __i2 <= end());
1818	return _M_replace_aux(__i1 - begin(), __i2 - __i1, __n, __c);
1819	}
1820
1821	/**
1822	* @brief Replace range of characters with range.
1823	* @param __i1 Iterator referencing start of range to replace.
1824	* @param __i2 Iterator referencing end of range to replace.
1825	* @param __k1 Iterator referencing start of range to insert.
1826	* @param __k2 Iterator referencing end of range to insert.
1827	* @return Reference to this string.
1828	* @throw std::length_error If new length exceeds @c max_size().
1829	*
1830	* Removes the characters in the range [__i1,__i2). In place,
1831	* characters in the range [__k1,__k2) are inserted. If the
1832	* length of result exceeds max_size(), length_error is thrown.
1833	* The value of the string doesn't change if an error is
1834	* thrown.
1835	*/
1836	#if __cplusplus >= 201103L
1837	template<class _InputIterator,
1838	typename = std::_RequireInputIter<_InputIterator>>
1839	basic_string&
1840	replace(const_iterator __i1, const_iterator __i2,
1841	_InputIterator __k1, _InputIterator __k2)
1842	{
1843	_GLIBCXX_DEBUG_PEDASSERT(begin() <= __i1 && __i1 <= __i2
1844	&& __i2 <= end());
1845	__glibcxx_requires_valid_range(__k1, __k2);
1846	return this->_M_replace_dispatch(__i1, __i2, __k1, __k2,
1847	std::__false_type());
1848	}
1849	#else
1850	template<class _InputIterator>
1851	#ifdef _GLIBCXX_DISAMBIGUATE_REPLACE_INST
1852	typename __enable_if_not_native_iterator<_InputIterator>::__type
1853	#else
1854	basic_string&
1855	#endif
1856	replace(iterator __i1, iterator __i2,
1857	_InputIterator __k1, _InputIterator __k2)
1858	{
1859	_GLIBCXX_DEBUG_PEDASSERT(begin() <= __i1 && __i1 <= __i2
1860	&& __i2 <= end());
1861	__glibcxx_requires_valid_range(__k1, __k2);
1862	typedef typename std::__is_integer<_InputIterator>::__type _Integral;
1863	return _M_replace_dispatch(__i1, __i2, __k1, __k2, _Integral());
1864	}
1865	#endif
1866
1867	// Specializations for the common case of pointer and iterator:
1868	// useful to avoid the overhead of temporary buffering in _M_replace.
1869	basic_string&
1870	replace(__const_iterator __i1, __const_iterator __i2,
1871	_CharT* __k1, _CharT* __k2)
1872	{
1873	_GLIBCXX_DEBUG_PEDASSERT(begin() <= __i1 && __i1 <= __i2
1874	&& __i2 <= end());
1875	__glibcxx_requires_valid_range(__k1, __k2);
1876	return this->replace(__i1 - begin(), __i2 - __i1,
1877	__k1, __k2 - __k1);
1878	}
1879
1880	basic_string&
1881	replace(__const_iterator __i1, __const_iterator __i2,
1882	const _CharT* __k1, const _CharT* __k2)
1883	{
1884	_GLIBCXX_DEBUG_PEDASSERT(begin() <= __i1 && __i1 <= __i2
1885	&& __i2 <= end());
1886	__glibcxx_requires_valid_range(__k1, __k2);
1887	return this->replace(__i1 - begin(), __i2 - __i1,
1888	__k1, __k2 - __k1);
1889	}
1890
1891	basic_string&
1892	replace(__const_iterator __i1, __const_iterator __i2,
1893	iterator __k1, iterator __k2)
1894	{
1895	_GLIBCXX_DEBUG_PEDASSERT(begin() <= __i1 && __i1 <= __i2
1896	&& __i2 <= end());
1897	__glibcxx_requires_valid_range(__k1, __k2);
1898	return this->replace(__i1 - begin(), __i2 - __i1,
1899	__k1.base(), __k2 - __k1);
1900	}
1901
1902	basic_string&
1903	replace(__const_iterator __i1, __const_iterator __i2,
1904	const_iterator __k1, const_iterator __k2)
1905	{
1906	_GLIBCXX_DEBUG_PEDASSERT(begin() <= __i1 && __i1 <= __i2
1907	&& __i2 <= end());
1908	__glibcxx_requires_valid_range(__k1, __k2);
1909	return this->replace(__i1 - begin(), __i2 - __i1,
1910	__k1.base(), __k2 - __k1);
1911	}
1912
1913	#if __cplusplus >= 201103L
1914	/**
1915	* @brief Replace range of characters with initializer_list.
1916	* @param __i1 Iterator referencing start of range to replace.
1917	* @param __i2 Iterator referencing end of range to replace.
1918	* @param __l The initializer_list of characters to insert.
1919	* @return Reference to this string.
1920	* @throw std::length_error If new length exceeds @c max_size().
1921	*
1922	* Removes the characters in the range [__i1,__i2). In place,
1923	* characters in the range [__k1,__k2) are inserted. If the
1924	* length of result exceeds max_size(), length_error is thrown.
1925	* The value of the string doesn't change if an error is
1926	* thrown.
1927	*/
1928	basic_string& replace(const_iterator __i1, const_iterator __i2,
1929	initializer_list<_CharT> __l)
1930	{ return this->replace(__i1, __i2, __l.begin(), __l.end()); }
1931	#endif // C++11
1932
1933	private:
1934	template<class _Integer>
1935	basic_string&
1936	_M_replace_dispatch(const_iterator __i1, const_iterator __i2,
1937	_Integer __n, _Integer __val, __true_type)
1938	{ return _M_replace_aux(__i1 - begin(), __i2 - __i1, __n, __val); }
1939
1940	template<class _InputIterator>
1941	basic_string&
1942	_M_replace_dispatch(const_iterator __i1, const_iterator __i2,
1943	_InputIterator __k1, _InputIterator __k2,
1944	__false_type);
1945
1946	basic_string&
1947	_M_replace_aux(size_type __pos1, size_type __n1, size_type __n2,
1948	_CharT __c);
1949
1950	basic_string&
1951	_M_replace(size_type __pos, size_type __len1, const _CharT* __s,
1952	const size_type __len2);
1953
1954	basic_string&
1955	_M_append(const _CharT* __s, size_type __n);
1956
1957	public:
1958
1959	/**
1960	* @brief Copy substring into C string.
1961	* @param __s C string to copy value into.
1962	* @param __n Number of characters to copy.
1963	* @param __pos Index of first character to copy.
1964	* @return Number of characters actually copied
1965	* @throw std::out_of_range If __pos > size().
1966	*
1967	* Copies up to @a __n characters starting at @a __pos into the
1968	* C string @a __s. If @a __pos is %greater than size(),
1969	* out_of_range is thrown.
1970	*/
1971	size_type
1972	copy(_CharT* __s, size_type __n, size_type __pos = `0`) const;
1973
1974	/**
1975	* @brief Swap contents with another string.
1976	* @param __s String to swap with.
1977	*
1978	* Exchanges the contents of this string with that of @a __s in constant
1979	* time.
1980	*/
1981	void
1982	swap(basic_string& __s) _GLIBCXX_NOEXCEPT;
1983
1984	// String operations:
1985	/**
1986	* @brief Return const pointer to null-terminated contents.
1987	*
1988	* This is a handle to internal data. Do not modify or dire things may
1989	* happen.
1990	*/
1991	const _CharT*
1992	c_str() const _GLIBCXX_NOEXCEPT
1993	{ return _M_data(); }
1994
1995	/**
1996	* @brief Return const pointer to contents.
1997	*
1998	* This is a handle to internal data. Do not modify or dire things may
1999	* happen.
2000	*/
2001	const _CharT*
2002	data() const _GLIBCXX_NOEXCEPT
2003	{ return _M_data(); }
2004
2005	/**
2006	* @brief Return copy of allocator used to construct this string.
2007	*/
2008	allocator_type
2009	get_allocator() const _GLIBCXX_NOEXCEPT
2010	{ return _M_get_allocator(); }
2011
2012	/**
2013	* @brief Find position of a C substring.
2014	* @param __s C string to locate.
2015	* @param __pos Index of character to search from.
2016	* @param __n Number of characters from @a s to search for.
2017	* @return Index of start of first occurrence.
2018	*
2019	* Starting from @a __pos, searches forward for the first @a
2020	* __n characters in @a __s within this string. If found,
2021	* returns the index where it begins. If not found, returns
2022	* npos.
2023	*/
2024	size_type
2025	find(const _CharT* __s, size_type __pos, size_type __n) const;
2026
2027	/**
2028	* @brief Find position of a string.
2029	* @param __str String to locate.
2030	* @param __pos Index of character to search from (default 0).
2031	* @return Index of start of first occurrence.
2032	*
2033	* Starting from @a __pos, searches forward for value of @a __str within
2034	* this string. If found, returns the index where it begins. If not
2035	* found, returns npos.
2036	*/
2037	size_type
2038	find(const basic_string& __str, size_type __pos = `0`) const
2039	_GLIBCXX_NOEXCEPT
2040	{ return this->find(__str.data(), __pos, __str.size()); }
2041
2042	/**
2043	* @brief Find position of a C string.
2044	* @param __s C string to locate.
2045	* @param __pos Index of character to search from (default 0).
2046	* @return Index of start of first occurrence.
2047	*
2048	* Starting from @a __pos, searches forward for the value of @a
2049	* __s within this string. If found, returns the index where
2050	* it begins. If not found, returns npos.
2051	*/
2052	size_type
2053	find(const _CharT* __s, size_type __pos = `0`) const
2054	{
2055	__glibcxx_requires_string(__s);
2056	return this->find(__s, __pos, traits_type::length(__s));
2057	}
2058
2059	/**
2060	* @brief Find position of a character.
2061	* @param __c Character to locate.
2062	* @param __pos Index of character to search from (default 0).
2063	* @return Index of first occurrence.
2064	*
2065	* Starting from @a __pos, searches forward for @a __c within
2066	* this string. If found, returns the index where it was
2067	* found. If not found, returns npos.
2068	*/
2069	size_type
2070	find(_CharT __c, size_type __pos = `0`) const _GLIBCXX_NOEXCEPT;
2071
2072	/**
2073	* @brief Find last position of a string.
2074	* @param __str String to locate.
2075	* @param __pos Index of character to search back from (default end).
2076	* @return Index of start of last occurrence.
2077	*
2078	* Starting from @a __pos, searches backward for value of @a
2079	* __str within this string. If found, returns the index where
2080	* it begins. If not found, returns npos.
2081	*/
2082	size_type
2083	rfind(const basic_string& __str, size_type __pos = npos) const
2084	_GLIBCXX_NOEXCEPT
2085	{ return this->rfind(__str.data(), __pos, __str.size()); }
2086
2087	/**
2088	* @brief Find last position of a C substring.
2089	* @param __s C string to locate.
2090	* @param __pos Index of character to search back from.
2091	* @param __n Number of characters from s to search for.
2092	* @return Index of start of last occurrence.
2093	*
2094	* Starting from @a __pos, searches backward for the first @a
2095	* __n characters in @a __s within this string. If found,
2096	* returns the index where it begins. If not found, returns
2097	* npos.
2098	*/
2099	size_type
2100	rfind(const _CharT* __s, size_type __pos, size_type __n) const;
2101
2102	/**
2103	* @brief Find last position of a C string.
2104	* @param __s C string to locate.
2105	* @param __pos Index of character to start search at (default end).
2106	* @return Index of start of last occurrence.
2107	*
2108	* Starting from @a __pos, searches backward for the value of
2109	* @a __s within this string. If found, returns the index
2110	* where it begins. If not found, returns npos.
2111	*/
2112	size_type
2113	rfind(const _CharT* __s, size_type __pos = npos) const
2114	{
2115	__glibcxx_requires_string(__s);
2116	return this->rfind(__s, __pos, traits_type::length(__s));
2117	}
2118
2119	/**
2120	* @brief Find last position of a character.
2121	* @param __c Character to locate.
2122	* @param __pos Index of character to search back from (default end).
2123	* @return Index of last occurrence.
2124	*
2125	* Starting from @a __pos, searches backward for @a __c within
2126	* this string. If found, returns the index where it was
2127	* found. If not found, returns npos.
2128	*/
2129	size_type
2130	rfind(_CharT __c, size_type __pos = npos) const _GLIBCXX_NOEXCEPT;
2131
2132	/**
2133	* @brief Find position of a character of string.
2134	* @param __str String containing characters to locate.
2135	* @param __pos Index of character to search from (default 0).
2136	* @return Index of first occurrence.
2137	*
2138	* Starting from @a __pos, searches forward for one of the
2139	* characters of @a __str within this string. If found,
2140	* returns the index where it was found. If not found, returns
2141	* npos.
2142	*/
2143	size_type
2144	find_first_of(const basic_string& __str, size_type __pos = `0`) const
2145	_GLIBCXX_NOEXCEPT
2146	{ return this->find_first_of(__str.data(), __pos, __str.size()); }
2147
2148	/**
2149	* @brief Find position of a character of C substring.
2150	* @param __s String containing characters to locate.
2151	* @param __pos Index of character to search from.
2152	* @param __n Number of characters from s to search for.
2153	* @return Index of first occurrence.
2154	*
2155	* Starting from @a __pos, searches forward for one of the
2156	* first @a __n characters of @a __s within this string. If
2157	* found, returns the index where it was found. If not found,
2158	* returns npos.
2159	*/
2160	size_type
2161	find_first_of(const _CharT* __s, size_type __pos, size_type __n) const;
2162
2163	/**
2164	* @brief Find position of a character of C string.
2165	* @param __s String containing characters to locate.
2166	* @param __pos Index of character to search from (default 0).
2167	* @return Index of first occurrence.
2168	*
2169	* Starting from @a __pos, searches forward for one of the
2170	* characters of @a __s within this string. If found, returns
2171	* the index where it was found. If not found, returns npos.
2172	*/
2173	size_type
2174	find_first_of(const _CharT* __s, size_type __pos = `0`) const
2175	{
2176	__glibcxx_requires_string(__s);
2177	return this->find_first_of(__s, __pos, traits_type::length(__s));
2178	}
2179
2180	/**
2181	* @brief Find position of a character.
2182	* @param __c Character to locate.
2183	* @param __pos Index of character to search from (default 0).
2184	* @return Index of first occurrence.
2185	*
2186	* Starting from @a __pos, searches forward for the character
2187	* @a __c within this string. If found, returns the index
2188	* where it was found. If not found, returns npos.
2189	*
2190	* Note: equivalent to find(__c, __pos).
2191	*/
2192	size_type
2193	find_first_of(_CharT __c, size_type __pos = `0`) const _GLIBCXX_NOEXCEPT
2194	{ return this->find(__c, __pos); }
2195
2196	/**
2197	* @brief Find last position of a character of string.
2198	* @param __str String containing characters to locate.
2199	* @param __pos Index of character to search back from (default end).
2200	* @return Index of last occurrence.
2201	*
2202	* Starting from @a __pos, searches backward for one of the
2203	* characters of @a __str within this string. If found,
2204	* returns the index where it was found. If not found, returns
2205	* npos.
2206	*/
2207	size_type
2208	find_last_of(const basic_string& __str, size_type __pos = npos) const
2209	_GLIBCXX_NOEXCEPT
2210	{ return this->find_last_of(__str.data(), __pos, __str.size()); }
2211
2212	/**
2213	* @brief Find last position of a character of C substring.
2214	* @param __s C string containing characters to locate.
2215	* @param __pos Index of character to search back from.
2216	* @param __n Number of characters from s to search for.
2217	* @return Index of last occurrence.
2218	*
2219	* Starting from @a __pos, searches backward for one of the
2220	* first @a __n characters of @a __s within this string. If
2221	* found, returns the index where it was found. If not found,
2222	* returns npos.
2223	*/
2224	size_type
2225	find_last_of(const _CharT* __s, size_type __pos, size_type __n) const;
2226
2227	/**
2228	* @brief Find last position of a character of C string.
2229	* @param __s C string containing characters to locate.
2230	* @param __pos Index of character to search back from (default end).
2231	* @return Index of last occurrence.
2232	*
2233	* Starting from @a __pos, searches backward for one of the
2234	* characters of @a __s within this string. If found, returns
2235	* the index where it was found. If not found, returns npos.
2236	*/
2237	size_type
2238	find_last_of(const _CharT* __s, size_type __pos = npos) const
2239	{
2240	__glibcxx_requires_string(__s);
2241	return this->find_last_of(__s, __pos, traits_type::length(__s));
2242	}
2243
2244	/**
2245	* @brief Find last position of a character.
2246	* @param __c Character to locate.
2247	* @param __pos Index of character to search back from (default end).
2248	* @return Index of last occurrence.
2249	*
2250	* Starting from @a __pos, searches backward for @a __c within
2251	* this string. If found, returns the index where it was
2252	* found. If not found, returns npos.
2253	*
2254	* Note: equivalent to rfind(__c, __pos).
2255	*/
2256	size_type
2257	find_last_of(_CharT __c, size_type __pos = npos) const _GLIBCXX_NOEXCEPT
2258	{ return this->rfind(__c, __pos); }
2259
2260	/**
2261	* @brief Find position of a character not in string.
2262	* @param __str String containing characters to avoid.
2263	* @param __pos Index of character to search from (default 0).
2264	* @return Index of first occurrence.
2265	*
2266	* Starting from @a __pos, searches forward for a character not contained
2267	* in @a __str within this string. If found, returns the index where it
2268	* was found. If not found, returns npos.
2269	*/
2270	size_type
2271	find_first_not_of(const basic_string& __str, size_type __pos = `0`) const
2272	_GLIBCXX_NOEXCEPT
2273	{ return this->find_first_not_of(__str.data(), __pos, __str.size()); }
2274
2275	/**
2276	* @brief Find position of a character not in C substring.
2277	* @param __s C string containing characters to avoid.
2278	* @param __pos Index of character to search from.
2279	* @param __n Number of characters from __s to consider.
2280	* @return Index of first occurrence.
2281	*
2282	* Starting from @a __pos, searches forward for a character not
2283	* contained in the first @a __n characters of @a __s within
2284	* this string. If found, returns the index where it was
2285	* found. If not found, returns npos.
2286	*/
2287	size_type
2288	find_first_not_of(const _CharT* __s, size_type __pos,
2289	size_type __n) const;
2290
2291	/**
2292	* @brief Find position of a character not in C string.
2293	* @param __s C string containing characters to avoid.
2294	* @param __pos Index of character to search from (default 0).
2295	* @return Index of first occurrence.
2296	*
2297	* Starting from @a __pos, searches forward for a character not
2298	* contained in @a __s within this string. If found, returns
2299	* the index where it was found. If not found, returns npos.
2300	*/
2301	size_type
2302	find_first_not_of(const _CharT* __s, size_type __pos = `0`) const
2303	{
2304	__glibcxx_requires_string(__s);
2305	return this->find_first_not_of(__s, __pos, traits_type::length(__s));
2306	}
2307
2308	/**
2309	* @brief Find position of a different character.
2310	* @param __c Character to avoid.
2311	* @param __pos Index of character to search from (default 0).
2312	* @return Index of first occurrence.
2313	*
2314	* Starting from @a __pos, searches forward for a character
2315	* other than @a __c within this string. If found, returns the
2316	* index where it was found. If not found, returns npos.
2317	*/
2318	size_type
2319	find_first_not_of(_CharT __c, size_type __pos = `0`) const
2320	_GLIBCXX_NOEXCEPT;
2321
2322	/**
2323	* @brief Find last position of a character not in string.
2324	* @param __str String containing characters to avoid.
2325	* @param __pos Index of character to search back from (default end).
2326	* @return Index of last occurrence.
2327	*
2328	* Starting from @a __pos, searches backward for a character
2329	* not contained in @a __str within this string. If found,
2330	* returns the index where it was found. If not found, returns
2331	* npos.
2332	*/
2333	size_type
2334	find_last_not_of(const basic_string& __str, size_type __pos = npos) const
2335	_GLIBCXX_NOEXCEPT
2336	{ return this->find_last_not_of(__str.data(), __pos, __str.size()); }
2337
2338	/**
2339	* @brief Find last position of a character not in C substring.
2340	* @param __s C string containing characters to avoid.
2341	* @param __pos Index of character to search back from.
2342	* @param __n Number of characters from s to consider.
2343	* @return Index of last occurrence.
2344	*
2345	* Starting from @a __pos, searches backward for a character not
2346	* contained in the first @a __n characters of @a __s within this string.
2347	* If found, returns the index where it was found. If not found,
2348	* returns npos.
2349	*/
2350	size_type
2351	find_last_not_of(const _CharT* __s, size_type __pos,
2352	size_type __n) const;
2353	/**
2354	* @brief Find last position of a character not in C string.
2355	* @param __s C string containing characters to avoid.
2356	* @param __pos Index of character to search back from (default end).
2357	* @return Index of last occurrence.
2358	*
2359	* Starting from @a __pos, searches backward for a character
2360	* not contained in @a __s within this string. If found,
2361	* returns the index where it was found. If not found, returns
2362	* npos.
2363	*/
2364	size_type
2365	find_last_not_of(const _CharT* __s, size_type __pos = npos) const
2366	{
2367	__glibcxx_requires_string(__s);
2368	return this->find_last_not_of(__s, __pos, traits_type::length(__s));
2369	}
2370
2371	/**
2372	* @brief Find last position of a different character.
2373	* @param __c Character to avoid.
2374	* @param __pos Index of character to search back from (default end).
2375	* @return Index of last occurrence.
2376	*
2377	* Starting from @a __pos, searches backward for a character other than
2378	* @a __c within this string. If found, returns the index where it was
2379	* found. If not found, returns npos.
2380	*/
2381	size_type
2382	find_last_not_of(_CharT __c, size_type __pos = npos) const
2383	_GLIBCXX_NOEXCEPT;
2384
2385	/**
2386	* @brief Get a substring.
2387	* @param __pos Index of first character (default 0).
2388	* @param __n Number of characters in substring (default remainder).
2389	* @return The new string.
2390	* @throw std::out_of_range If __pos > size().
2391	*
2392	* Construct and return a new string using the @a __n
2393	* characters starting at @a __pos. If the string is too
2394	* short, use the remainder of the characters. If @a __pos is
2395	* beyond the end of the string, out_of_range is thrown.
2396	*/
2397	basic_string
2398	substr(size_type __pos = `0`, size_type __n = npos) const
2399	{ return basic_string(*this,
2400	_M_check(__pos, "basic_string::substr"), __n); }
2401
2402	/**
2403	* @brief Compare to a string.
2404	* @param __str String to compare against.
2405	* @return Integer < 0, 0, or > 0.
2406	*
2407	* Returns an integer < 0 if this string is ordered before @a
2408	* __str, 0 if their values are equivalent, or > 0 if this
2409	* string is ordered after @a __str. Determines the effective
2410	* length rlen of the strings to compare as the smallest of
2411	* size() and str.size(). The function then compares the two
2412	* strings by calling traits::compare(data(), str.data(),rlen).
2413	* If the result of the comparison is nonzero returns it,
2414	* otherwise the shorter one is ordered first.
2415	*/
2416	int
2417	compare(const basic_string& __str) const
2418	{
2419	const size_type __size = this->size();
2420	const size_type __osize = __str.size();
2421	const size_type __len = std::min(__size, __osize);
2422
2423	int __r = traits_type::compare(_M_data(), __str.data(), __len);
2424	if (!__r)
2425	__r = _S_compare(__size, __osize);
2426	return __r;
2427	}
2428
2429	/**
2430	* @brief Compare substring to a string.
2431	* @param __pos Index of first character of substring.
2432	* @param __n Number of characters in substring.
2433	* @param __str String to compare against.
2434	* @return Integer < 0, 0, or > 0.
2435	*
2436	* Form the substring of this string from the @a __n characters
2437	* starting at @a __pos. Returns an integer < 0 if the
2438	* substring is ordered before @a __str, 0 if their values are
2439	* equivalent, or > 0 if the substring is ordered after @a
2440	* __str. Determines the effective length rlen of the strings
2441	* to compare as the smallest of the length of the substring
2442	* and @a __str.size(). The function then compares the two
2443	* strings by calling
2444	* traits::compare(substring.data(),str.data(),rlen). If the
2445	* result of the comparison is nonzero returns it, otherwise
2446	* the shorter one is ordered first.
2447	*/
2448	int
2449	compare(size_type __pos, size_type __n, const basic_string& __str) const;
2450
2451	/**
2452	* @brief Compare substring to a substring.
2453	* @param __pos1 Index of first character of substring.
2454	* @param __n1 Number of characters in substring.
2455	* @param __str String to compare against.
2456	* @param __pos2 Index of first character of substring of str.
2457	* @param __n2 Number of characters in substring of str.
2458	* @return Integer < 0, 0, or > 0.
2459	*
2460	* Form the substring of this string from the @a __n1
2461	* characters starting at @a __pos1. Form the substring of @a
2462	* __str from the @a __n2 characters starting at @a __pos2.
2463	* Returns an integer < 0 if this substring is ordered before
2464	* the substring of @a __str, 0 if their values are equivalent,
2465	* or > 0 if this substring is ordered after the substring of
2466	* @a __str. Determines the effective length rlen of the
2467	* strings to compare as the smallest of the lengths of the
2468	* substrings. The function then compares the two strings by
2469	* calling
2470	* traits::compare(substring.data(),str.substr(pos2,n2).data(),rlen).
2471	* If the result of the comparison is nonzero returns it,
2472	* otherwise the shorter one is ordered first.
2473	*/
2474	int
2475	compare(size_type __pos1, size_type __n1, const basic_string& __str,
2476	size_type __pos2, size_type __n2) const;
2477
2478	/**
2479	* @brief Compare to a C string.
2480	* @param __s C string to compare against.
2481	* @return Integer < 0, 0, or > 0.
2482	*
2483	* Returns an integer < 0 if this string is ordered before @a __s, 0 if
2484	* their values are equivalent, or > 0 if this string is ordered after
2485	* @a __s. Determines the effective length rlen of the strings to
2486	* compare as the smallest of size() and the length of a string
2487	* constructed from @a __s. The function then compares the two strings
2488	* by calling traits::compare(data(),s,rlen). If the result of the
2489	* comparison is nonzero returns it, otherwise the shorter one is
2490	* ordered first.
2491	*/
2492	int
2493	compare(const _CharT* __s) const;
2494
2495	// _GLIBCXX_RESOLVE_LIB_DEFECTS
2496	// 5 String::compare specification questionable
2497	/**
2498	* @brief Compare substring to a C string.
2499	* @param __pos Index of first character of substring.
2500	* @param __n1 Number of characters in substring.
2501	* @param __s C string to compare against.
2502	* @return Integer < 0, 0, or > 0.
2503	*
2504	* Form the substring of this string from the @a __n1
2505	* characters starting at @a pos. Returns an integer < 0 if
2506	* the substring is ordered before @a __s, 0 if their values
2507	* are equivalent, or > 0 if the substring is ordered after @a
2508	* __s. Determines the effective length rlen of the strings to
2509	* compare as the smallest of the length of the substring and
2510	* the length of a string constructed from @a __s. The
2511	* function then compares the two string by calling
2512	* traits::compare(substring.data(),__s,rlen). If the result of
2513	* the comparison is nonzero returns it, otherwise the shorter
2514	* one is ordered first.
2515	*/
2516	int
2517	compare(size_type __pos, size_type __n1, const _CharT* __s) const;
2518
2519	/**
2520	* @brief Compare substring against a character %array.
2521	* @param __pos Index of first character of substring.
2522	* @param __n1 Number of characters in substring.
2523	* @param __s character %array to compare against.
2524	* @param __n2 Number of characters of s.
2525	* @return Integer < 0, 0, or > 0.
2526	*
2527	* Form the substring of this string from the @a __n1
2528	* characters starting at @a __pos. Form a string from the
2529	* first @a __n2 characters of @a __s. Returns an integer < 0
2530	* if this substring is ordered before the string from @a __s,
2531	* 0 if their values are equivalent, or > 0 if this substring
2532	* is ordered after the string from @a __s. Determines the
2533	* effective length rlen of the strings to compare as the
2534	* smallest of the length of the substring and @a __n2. The
2535	* function then compares the two strings by calling
2536	* traits::compare(substring.data(),s,rlen). If the result of
2537	* the comparison is nonzero returns it, otherwise the shorter
2538	* one is ordered first.
2539	*
2540	* NB: s must have at least n2 characters, '\\0' has
2541	* no special meaning.
2542	*/
2543	int
2544	compare(size_type __pos, size_type __n1, const _CharT* __s,
2545	size_type __n2) const;
2546	};
2547	_GLIBCXX_END_NAMESPACE_CXX11
2548	#else // !_GLIBCXX_USE_CXX11_ABI
2549	// Reference-counted COW string implentation
2550
2551	/**
2552	* @class basic_string basic_string.h <string>
2553	* @brief Managing sequences of characters and character-like objects.
2554	*
2555	* @ingroup strings
2556	* @ingroup sequences
2557	*
2558	* @tparam _CharT Type of character
2559	* @tparam _Traits Traits for character type, defaults to
2560	* char_traits<_CharT>.
2561	* @tparam _Alloc Allocator type, defaults to allocator<_CharT>.
2562	*
2563	* Meets the requirements of a <a href="tables.html#65">container</a>, a
2564	* <a href="tables.html#66">reversible container</a>, and a
2565	* <a href="tables.html#67">sequence</a>. Of the
2566	* <a href="tables.html#68">optional sequence requirements</a>, only
2567	* @c push_back, @c at, and @c %array access are supported.
2568	*
2569	* @doctodo
2570	*
2571	*
2572	* Documentation? What's that?
2573	* Nathan Myers <ncm@cantrip.org>.
2574	*
2575	* A string looks like this:
2576	*
2577	* @code
2578	* [_Rep]
2579	* _M_length
2580	* [basic_string<char_type>] _M_capacity
2581	* _M_dataplus _M_refcount
2582	* _M_p ----------------> unnamed array of char_type
2583	* @endcode
2584	*
2585	* Where the _M_p points to the first character in the string, and
2586	* you cast it to a pointer-to-_Rep and subtract 1 to get a
2587	* pointer to the header.
2588	*
2589	* This approach has the enormous advantage that a string object
2590	* requires only one allocation. All the ugliness is confined
2591	* within a single %pair of inline functions, which each compile to
2592	* a single @a add instruction: _Rep::_M_data(), and
2593	* string::_M_rep(); and the allocation function which gets a
2594	* block of raw bytes and with room enough and constructs a _Rep
2595	* object at the front.
2596	*
2597	* The reason you want _M_data pointing to the character %array and
2598	* not the _Rep is so that the debugger can see the string
2599	* contents. (Probably we should add a non-inline member to get
2600	* the _Rep for the debugger to use, so users can check the actual
2601	* string length.)
2602	*
2603	* Note that the _Rep object is a POD so that you can have a
2604	* static <em>empty string</em> _Rep object already @a constructed before
2605	* static constructors have run. The reference-count encoding is
2606	* chosen so that a 0 indicates one reference, so you never try to
2607	* destroy the empty-string _Rep object.
2608	*
2609	* All but the last paragraph is considered pretty conventional
2610	* for a C++ string implementation.
2611	*/
2612	// 21.3 Template class basic_string
2613	template<typename _CharT, typename _Traits, typename _Alloc>
2614	class basic_string
2615	{
2616	typedef typename _Alloc::template rebind<_CharT>::other _CharT_alloc_type;
2617
2618	// Types:
2619	public:
2620	typedef _Traits traits_type;
2621	typedef typename _Traits::char_type value_type;
2622	typedef _Alloc allocator_type;
2623	typedef typename _CharT_alloc_type::size_type size_type;
2624	typedef typename _CharT_alloc_type::difference_type difference_type;
2625	typedef typename _CharT_alloc_type::reference reference;
2626	typedef typename _CharT_alloc_type::const_reference const_reference;
2627	typedef typename _CharT_alloc_type::pointer pointer;
2628	typedef typename _CharT_alloc_type::const_pointer const_pointer;
2629	typedef __gnu_cxx::__normal_iterator<pointer, basic_string> iterator;
2630	typedef __gnu_cxx::__normal_iterator<const_pointer, basic_string>
2631	const_iterator;
2632	typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
2633	typedef std::reverse_iterator<iterator> reverse_iterator;
2634
2635	private:
2636	// _Rep: string representation
2637	// Invariants:
2638	// 1. String really contains _M_length + 1 characters: due to 21.3.4
2639	// must be kept null-terminated.
2640	// 2. _M_capacity >= _M_length
2641	// Allocated memory is always (_M_capacity + 1) sizeof(_CharT).*
2642	// 3. _M_refcount has three states:
2643	// -1: leaked, one reference, no ref-copies allowed, non-const.
2644	// 0: one reference, non-const.
2645	// n>0: n + 1 references, operations require a lock, const.
2646	// 4. All fields==0 is an empty string, given the extra storage
2647	// beyond-the-end for a null terminator; thus, the shared
2648	// empty string representation needs no constructor.
2649
2650	struct _Rep_base
2651	{
2652	size_type _M_length;
2653	size_type _M_capacity;
2654	_Atomic_word _M_refcount;
2655	};
2656
2657	struct _Rep : _Rep_base
2658	{
2659	// Types:
2660	typedef typename _Alloc::template rebind<char>::other _Raw_bytes_alloc;
2661
2662	// (Public) Data members:
2663
2664	// The maximum number of individual char_type elements of an
2665	// individual string is determined by _S_max_size. This is the
2666	// value that will be returned by max_size(). (Whereas npos
2667	// is the maximum number of bytes the allocator can allocate.)
2668	// If one was to divvy up the theoretical largest size string,
2669	// with a terminating character and m _CharT elements, it'd
2670	// look like this:
2671	// npos = sizeof(_Rep) + (m sizeof(_CharT)) + sizeof(_CharT)*
2672	// Solving for m:
2673	// m = ((npos - sizeof(_Rep))/sizeof(CharT)) - 1
2674	// In addition, this implementation quarters this amount.
2675	static const size_type _S_max_size;
2676	static const _CharT _S_terminal;
2677
2678	// The following storage is init'd to 0 by the linker, resulting
2679	// (carefully) in an empty string with one reference.
2680	static size_type _S_empty_rep_storage[];
2681
2682	static _Rep&
2683	_S_empty_rep() _GLIBCXX_NOEXCEPT
2684	{
2685	// NB: Mild hack to avoid strict-aliasing warnings. Note that
2686	// _S_empty_rep_storage is never modified and the punning should
2687	// be reasonably safe in this case.
2688	void* __p = reinterpret_cast<void*>(&_S_empty_rep_storage);
2689	return *reinterpret_cast<_Rep*>(__p);
2690	}
2691
2692	bool
2693	_M_is_leaked() const _GLIBCXX_NOEXCEPT
2694	{
2695	#if defined(__GTHREADS)
2696	// _M_refcount is mutated concurrently by _M_refcopy/_M_dispose,
2697	// so we need to use an atomic load. However, _M_is_leaked
2698	// predicate does not change concurrently (i.e. the string is either
2699	// leaked or not), so a relaxed load is enough.
2700	return __atomic_load_n(&this->_M_refcount, __ATOMIC_RELAXED) < `0`;
2701	#else
2702	return this->_M_refcount < `0`;
2703	#endif
2704	}
2705
2706	bool
2707	_M_is_shared() const _GLIBCXX_NOEXCEPT
2708	{
2709	#if defined(__GTHREADS)
2710	// _M_refcount is mutated concurrently by _M_refcopy/_M_dispose,
2711	// so we need to use an atomic load. Another thread can drop last
2712	// but one reference concurrently with this check, so we need this
2713	// load to be acquire to synchronize with release fetch_and_add in
2714	// _M_dispose.
2715	return __atomic_load_n(&this->_M_refcount, __ATOMIC_ACQUIRE) > `0`;
2716	#else
2717	return this->_M_refcount > `0`;
2718	#endif
2719	}
2720
2721	void
2722	_M_set_leaked() _GLIBCXX_NOEXCEPT
2723	{ this->_M_refcount = -`1`; }
2724
2725	void
2726	_M_set_sharable() _GLIBCXX_NOEXCEPT
2727	{ this->_M_refcount = `0`; }
2728
2729	void
2730	_M_set_length_and_sharable(size_type __n) _GLIBCXX_NOEXCEPT
2731	{
2732	#if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
2733	if (__builtin_expect(this != &_S_empty_rep(), false))
2734	#endif
2735	{
2736	this->_M_set_sharable(); // One reference.
2737	this->_M_length = __n;
2738	traits_type::assign(this->_M_refdata()[__n], _S_terminal);
2739	// grrr. (per 21.3.4)
2740	// You cannot leave those LWG people alone for a second.
2741	}
2742	}
2743
2744	_CharT*
2745	_M_refdata() throw()
2746	{ return reinterpret_cast<_CharT>(this* + `1`); }
2747
2748	_CharT*
2749	_M_grab(const _Alloc& __alloc1, const _Alloc& __alloc2)
2750	{
2751	return (!_M_is_leaked() && __alloc1 == __alloc2)
2752	? _M_refcopy() : _M_clone(__alloc1);
2753	}
2754
2755	// Create & Destroy
2756	static _Rep*
2757	_S_create(size_type, size_type, const _Alloc&);
2758
2759	void
2760	_M_dispose(const _Alloc& __a) _GLIBCXX_NOEXCEPT
2761	{
2762	#if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
2763	if (__builtin_expect(this != &_S_empty_rep(), false))
2764	#endif
2765	{
2766	// Be race-detector-friendly. For more info see bits/c++config.
2767	_GLIBCXX_SYNCHRONIZATION_HAPPENS_BEFORE(&this->_M_refcount);
2768	// Decrement of _M_refcount is acq_rel, because:
2769	// - all but last decrements need to release to synchronize with
2770	// the last decrement that will delete the object.
2771	// - the last decrement needs to acquire to synchronize with
2772	// all the previous decrements.
2773	// - last but one decrement needs to release to synchronize with
2774	// the acquire load in _M_is_shared that will conclude that
2775	// the object is not shared anymore.
2776	if (__gnu_cxx::__exchange_and_add_dispatch(&this->_M_refcount,
2777	-`1`) <= `0`)
2778	{
2779	_GLIBCXX_SYNCHRONIZATION_HAPPENS_AFTER(&this->_M_refcount);
2780	_M_destroy(__a);
2781	}
2782	}
2783	} // XXX MT
2784
2785	void
2786	_M_destroy(const _Alloc&) throw();
2787
2788	_CharT*
2789	_M_refcopy() throw()
2790	{
2791	#if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
2792	if (__builtin_expect(this != &_S_empty_rep(), false))
2793	#endif
2794	__gnu_cxx::__atomic_add_dispatch(&this->_M_refcount, `1`);
2795	return _M_refdata();
2796	} // XXX MT
2797
2798	_CharT*
2799	_M_clone(const _Alloc&, size_type __res = `0`);
2800	};
2801
2802	// Use empty-base optimization: http://www.cantrip.org/emptyopt.html
2803	struct _Alloc_hider : _Alloc
2804	{
2805	_Alloc_hider(_CharT* __dat, const _Alloc& __a) _GLIBCXX_NOEXCEPT
2806	: _Alloc(__a), _M_p(__dat) { }
2807
2808	_CharT* _M_p; // The actual data.
2809	};
2810
2811	public:
2812	// Data Members (public):
2813	// NB: This is an unsigned type, and thus represents the maximum
2814	// size that the allocator can hold.
2815	/// Value returned by various member functions when they fail.
2816	static const size_type npos = static_cast<size_type>(-`1`);
2817
2818	private:
2819	// Data Members (private):
2820	mutable _Alloc_hider _M_dataplus;
2821
2822	_CharT*
2823	_M_data() const _GLIBCXX_NOEXCEPT
2824	{ return _M_dataplus._M_p; }
2825
2826	_CharT*
2827	_M_data(_CharT* __p) _GLIBCXX_NOEXCEPT
2828	{ return (_M_dataplus._M_p = __p); }
2829
2830	_Rep*
2831	_M_rep() const _GLIBCXX_NOEXCEPT
2832	{ return &((reinterpret_cast<_Rep*> (_M_data()))[-`1`]); }
2833
2834	// For the internal use we have functions similar to `begin'/`end'
2835	// but they do not call _M_leak.
2836	iterator
2837	_M_ibegin() const _GLIBCXX_NOEXCEPT
2838	{ return iterator(_M_data()); }
2839
2840	iterator
2841	_M_iend() const _GLIBCXX_NOEXCEPT
2842	{ return iterator(_M_data() + this->size()); }
2843
2844	void
2845	_M_leak() // for use in begin() & non-const op[]
2846	{
2847	if (!_M_rep()->_M_is_leaked())
2848	_M_leak_hard();
2849	}
2850
2851	size_type
2852	_M_check(size_type __pos, const char* __s) const
2853	{
2854	if (__pos > this->size())
2855	__throw_out_of_range_fmt(__N("%s: __pos (which is %zu) > "
2856	"this->size() (which is %zu)"),
2857	__s, __pos, this->size());
2858	return __pos;
2859	}
2860
2861	void
2862	_M_check_length(size_type __n1, size_type __n2, const char* __s) const
2863	{
2864	if (this->max_size() - (this->size() - __n1) < __n2)
2865	__throw_length_error(__N(__s));
2866	}
2867
2868	// NB: _M_limit doesn't check for a bad __pos value.
2869	size_type
2870	_M_limit(size_type __pos, size_type __off) const _GLIBCXX_NOEXCEPT
2871	{
2872	const bool __testoff = __off < this->size() - __pos;
2873	return __testoff ? __off : this->size() - __pos;
2874	}
2875
2876	// True if _Rep and source do not overlap.
2877	bool
2878	_M_disjunct(const _CharT* __s) const _GLIBCXX_NOEXCEPT
2879	{
2880	return (less<const _CharT*>()(__s, _M_data())
2881	\|\| less<const _CharT>()(_M_data() + this*->size(), __s));
2882	}
2883
2884	// When __n = 1 way faster than the general multichar
2885	// traits_type::copy/move/assign.
2886	static void
2887	_M_copy(_CharT* __d, const _CharT* __s, size_type __n) _GLIBCXX_NOEXCEPT
2888	{
2889	if (__n == `1`)
2890	traits_type::assign(__d, __s);
2891	else
2892	traits_type::copy(__d, __s, __n);
2893	}
2894
2895	static void
2896	_M_move(_CharT* __d, const _CharT* __s, size_type __n) _GLIBCXX_NOEXCEPT
2897	{
2898	if (__n == `1`)
2899	traits_type::assign(__d, __s);
2900	else
2901	traits_type::move(__d, __s, __n);
2902	}
2903
2904	static void
2905	_M_assign(_CharT* __d, size_type __n, _CharT __c) _GLIBCXX_NOEXCEPT
2906	{
2907	if (__n == `1`)
2908	traits_type::assign(*__d, __c);
2909	else
2910	traits_type::assign(__d, __n, __c);
2911	}
2912
2913	// _S_copy_chars is a separate template to permit specialization
2914	// to optimize for the common case of pointers as iterators.
2915	template<class _Iterator>
2916	static void
2917	_S_copy_chars(_CharT* __p, _Iterator __k1, _Iterator __k2)
2918	{
2919	for (; __k1 != __k2; ++__k1, (void)++__p)
2920	traits_type::assign(__p, __k1); // These types are off.
2921	}
2922
2923	static void
2924	_S_copy_chars(_CharT* __p, iterator __k1, iterator __k2) _GLIBCXX_NOEXCEPT
2925	{ _S_copy_chars(__p, __k1.base(), __k2.base()); }
2926
2927	static void
2928	_S_copy_chars(_CharT* __p, const_iterator __k1, const_iterator __k2)
2929	_GLIBCXX_NOEXCEPT
2930	{ _S_copy_chars(__p, __k1.base(), __k2.base()); }
2931
2932	static void
2933	_S_copy_chars(_CharT* __p, _CharT* __k1, _CharT* __k2) _GLIBCXX_NOEXCEPT
2934	{ _M_copy(__p, __k1, __k2 - __k1); }
2935
2936	static void
2937	_S_copy_chars(_CharT* __p, const _CharT* __k1, const _CharT* __k2)
2938	_GLIBCXX_NOEXCEPT
2939	{ _M_copy(__p, __k1, __k2 - __k1); }
2940
2941	static int
2942	_S_compare(size_type __n1, size_type __n2) _GLIBCXX_NOEXCEPT
2943	{
2944	const difference_type __d = difference_type(__n1 - __n2);
2945
2946	if (__d > __gnu_cxx::__numeric_traits<int>::__max)
2947	return __gnu_cxx::__numeric_traits<int>::__max;
2948	else if (__d < __gnu_cxx::__numeric_traits<int>::__min)
2949	return __gnu_cxx::__numeric_traits<int>::__min;
2950	else
2951	return int(__d);
2952	}
2953
2954	void
2955	_M_mutate(size_type __pos, size_type __len1, size_type __len2);
2956
2957	void
2958	_M_leak_hard();
2959
2960	static _Rep&
2961	_S_empty_rep() _GLIBCXX_NOEXCEPT
2962	{ return _Rep::_S_empty_rep(); }
2963
2964	public:
2965	// Construct/copy/destroy:
2966	// NB: We overload ctors in some cases instead of using default
2967	// arguments, per 17.4.4.4 para. 2 item 2.
2968
2969	/**
2970	* @brief Default constructor creates an empty string.
2971	*/
2972	basic_string()
2973	#if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
2974	: _M_dataplus(_S_empty_rep()._M_refdata(), _Alloc()) { }
2975	#else
2976	: _M_dataplus(_S_construct(size_type(), _CharT(), _Alloc()), _Alloc()){ }
2977	#endif
2978
2979	/**
2980	* @brief Construct an empty string using allocator @a a.
2981	*/
2982	explicit
2983	basic_string(const _Alloc& __a);
2984
2985	// NB: per LWG issue 42, semantics different from IS:
2986	/**
2987	* @brief Construct string with copy of value of @a str.
2988	* @param __str Source string.
2989	*/
2990	basic_string(const basic_string& __str);
2991	/**
2992	* @brief Construct string as copy of a substring.
2993	* @param __str Source string.
2994	* @param __pos Index of first character to copy from.
2995	* @param __n Number of characters to copy (default remainder).
2996	*/
2997	basic_string(const basic_string& __str, size_type __pos,
2998	size_type __n = npos);
2999	/**
3000	* @brief Construct string as copy of a substring.
3001	* @param __str Source string.
3002	* @param __pos Index of first character to copy from.
3003	* @param __n Number of characters to copy.
3004	* @param __a Allocator to use.
3005	*/
3006	basic_string(const basic_string& __str, size_type __pos,
3007	size_type __n, const _Alloc& __a);
3008
3009	/**
3010	* @brief Construct string initialized by a character %array.
3011	* @param __s Source character %array.
3012	* @param __n Number of characters to copy.
3013	* @param __a Allocator to use (default is default allocator).
3014	*
3015	* NB: @a __s must have at least @a __n characters, '\\0'
3016	* has no special meaning.
3017	*/
3018	basic_string(const _CharT* __s, size_type __n,
3019	const _Alloc& __a = _Alloc());
3020	/**
3021	* @brief Construct string as copy of a C string.
3022	* @param __s Source C string.
3023	* @param __a Allocator to use (default is default allocator).
3024	*/
3025	basic_string(const _CharT* __s, const _Alloc& __a = _Alloc());
3026	/**
3027	* @brief Construct string as multiple characters.
3028	* @param __n Number of characters.
3029	* @param __c Character to use.
3030	* @param __a Allocator to use (default is default allocator).
3031	*/
3032	basic_string(size_type __n, _CharT __c, const _Alloc& __a = _Alloc());
3033
3034	#if __cplusplus >= 201103L
3035	/**
3036	* @brief Move construct string.
3037	* @param __str Source string.
3038	*
3039	* The newly-created string contains the exact contents of @a __str.
3040	* @a __str is a valid, but unspecified string.
3041	**/
3042	basic_string(basic_string&& __str)
3043	#if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
3044	noexcept // FIXME C++11: should always be noexcept.
3045	#endif
3046	: _M_dataplus(__str._M_dataplus)
3047	{
3048	#if _GLIBCXX_FULLY_DYNAMIC_STRING == 0
3049	__str._M_data(_S_empty_rep()._M_refdata());
3050	#else
3051	__str._M_data(_S_construct(size_type(), _CharT(), get_allocator()));
3052	#endif
3053	}
3054
3055	/**
3056	* @brief Construct string from an initializer %list.
3057	* @param __l std::initializer_list of characters.
3058	* @param __a Allocator to use (default is default allocator).
3059	*/
3060	basic_string(initializer_list<_CharT> __l, const _Alloc& __a = _Alloc());
3061	#endif // C++11
3062
3063	/**
3064	* @brief Construct string as copy of a range.
3065	* @param __beg Start of range.
3066	* @param __end End of range.
3067	* @param __a Allocator to use (default is default allocator).
3068	*/
3069	template<class _InputIterator>
3070	basic_string(_InputIterator __beg, _InputIterator __end,
3071	const _Alloc& __a = _Alloc());
3072
3073	/**
3074	* @brief Destroy the string instance.
3075	*/
3076	~basic_string() _GLIBCXX_NOEXCEPT
3077	{ _M_rep()->_M_dispose(this->get_allocator()); }
3078
3079	/**
3080	* @brief Assign the value of @a str to this string.
3081	* @param __str Source string.
3082	*/
3083	basic_string&
3084	operator=(const basic_string& __str)
3085	{ return this->assign(__str); }
3086
3087	/**
3088	* @brief Copy contents of @a s into this string.
3089	* @param __s Source null-terminated string.
3090	*/
3091	basic_string&
3092	operator=(const _CharT* __s)
3093	{ return this->assign(__s); }
3094
3095	/**
3096	* @brief Set value to string of length 1.
3097	* @param __c Source character.
3098	*
3099	* Assigning to a character makes this string length 1 and
3100	* (*this)[0] == @a c.
3101	*/
3102	basic_string&
3103	operator=(_CharT __c)
3104	{
3105	this->assign(`1`, __c);
3106	return *this;
3107	}
3108
3109	#if __cplusplus >= 201103L
3110	/**
3111	* @brief Move assign the value of @a str to this string.
3112	* @param __str Source string.
3113	*
3114	* The contents of @a str are moved into this string (without copying).
3115	* @a str is a valid, but unspecified string.
3116	**/
3117	// PR 58265, this should be noexcept.
3118	basic_string&
3119	operator=(basic_string&& __str)
3120	{
3121	// NB: DR 1204.
3122	this->swap(__str);
3123	return *this;
3124	}
3125
3126	/**
3127	* @brief Set value to string constructed from initializer %list.
3128	* @param __l std::initializer_list.
3129	*/
3130	basic_string&
3131	operator=(initializer_list<_CharT> __l)
3132	{
3133	this->assign(__l.begin(), __l.size());
3134	return *this;
3135	}
3136	#endif // C++11
3137
3138	// Iterators:
3139	/**
3140	* Returns a read/write iterator that points to the first character in
3141	* the %string. Unshares the string.
3142	*/
3143	iterator
3144	begin() // FIXME C++11: should be noexcept.
3145	{
3146	_M_leak();
3147	return iterator(_M_data());
3148	}
3149
3150	/**
3151	* Returns a read-only (constant) iterator that points to the first
3152	* character in the %string.
3153	*/
3154	const_iterator
3155	begin() const _GLIBCXX_NOEXCEPT
3156	{ return const_iterator(_M_data()); }
3157
3158	/**
3159	* Returns a read/write iterator that points one past the last
3160	* character in the %string. Unshares the string.
3161	*/
3162	iterator
3163	end() // FIXME C++11: should be noexcept.
3164	{
3165	_M_leak();
3166	return iterator(_M_data() + this->size());
3167	}
3168
3169	/**
3170	* Returns a read-only (constant) iterator that points one past the
3171	* last character in the %string.
3172	*/
3173	const_iterator
3174	end() const _GLIBCXX_NOEXCEPT
3175	{ return const_iterator(_M_data() + this->size()); }
3176
3177	/**
3178	* Returns a read/write reverse iterator that points to the last
3179	* character in the %string. Iteration is done in reverse element
3180	* order. Unshares the string.
3181	*/
3182	reverse_iterator
3183	rbegin() // FIXME C++11: should be noexcept.
3184	{ return reverse_iterator(this->end()); }
3185
3186	/**
3187	* Returns a read-only (constant) reverse iterator that points
3188	* to the last character in the %string. Iteration is done in
3189	* reverse element order.
3190	*/
3191	const_reverse_iterator
3192	rbegin() const _GLIBCXX_NOEXCEPT
3193	{ return const_reverse_iterator(this->end()); }
3194
3195	/**
3196	* Returns a read/write reverse iterator that points to one before the
3197	* first character in the %string. Iteration is done in reverse
3198	* element order. Unshares the string.
3199	*/
3200	reverse_iterator
3201	rend() // FIXME C++11: should be noexcept.
3202	{ return reverse_iterator(this->begin()); }
3203
3204	/**
3205	* Returns a read-only (constant) reverse iterator that points
3206	* to one before the first character in the %string. Iteration
3207	* is done in reverse element order.
3208	*/
3209	const_reverse_iterator
3210	rend() const _GLIBCXX_NOEXCEPT
3211	{ return const_reverse_iterator(this->begin()); }
3212
3213	#if __cplusplus >= 201103L
3214	/**
3215	* Returns a read-only (constant) iterator that points to the first
3216	* character in the %string.
3217	*/
3218	const_iterator
3219	cbegin() const noexcept
3220	{ return const_iterator(this->_M_data()); }
3221
3222	/**
3223	* Returns a read-only (constant) iterator that points one past the
3224	* last character in the %string.
3225	*/
3226	const_iterator
3227	cend() const noexcept
3228	{ return const_iterator(this->_M_data() + this->size()); }
3229
3230	/**
3231	* Returns a read-only (constant) reverse iterator that points
3232	* to the last character in the %string. Iteration is done in
3233	* reverse element order.
3234	*/
3235	const_reverse_iterator
3236	crbegin() const noexcept
3237	{ return const_reverse_iterator(this->end()); }
3238
3239	/**
3240	* Returns a read-only (constant) reverse iterator that points
3241	* to one before the first character in the %string. Iteration
3242	* is done in reverse element order.
3243	*/
3244	const_reverse_iterator
3245	crend() const noexcept
3246	{ return const_reverse_iterator(this->begin()); }
3247	#endif
3248
3249	public:
3250	// Capacity:
3251	/// Returns the number of characters in the string, not including any
3252	/// null-termination.
3253	size_type
3254	size() const _GLIBCXX_NOEXCEPT
3255	{ return _M_rep()->_M_length; }
3256
3257	/// Returns the number of characters in the string, not including any
3258	/// null-termination.
3259	size_type
3260	length() const _GLIBCXX_NOEXCEPT
3261	{ return _M_rep()->_M_length; }
3262
3263	/// Returns the size() of the largest possible %string.
3264	size_type
3265	max_size() const _GLIBCXX_NOEXCEPT
3266	{ return _Rep::_S_max_size; }
3267
3268	/**
3269	* @brief Resizes the %string to the specified number of characters.
3270	* @param __n Number of characters the %string should contain.
3271	* @param __c Character to fill any new elements.
3272	*
3273	* This function will %resize the %string to the specified
3274	* number of characters. If the number is smaller than the
3275	* %string's current size the %string is truncated, otherwise
3276	* the %string is extended and new elements are %set to @a __c.
3277	*/
3278	void
3279	resize(size_type __n, _CharT __c);
3280
3281	/**
3282	* @brief Resizes the %string to the specified number of characters.
3283	* @param __n Number of characters the %string should contain.
3284	*
3285	* This function will resize the %string to the specified length. If
3286	* the new size is smaller than the %string's current size the %string
3287	* is truncated, otherwise the %string is extended and new characters
3288	* are default-constructed. For basic types such as char, this means
3289	* setting them to 0.
3290	*/
3291	void
3292	resize(size_type __n)
3293	{ this->resize(__n, _CharT()); }
3294
3295	#if __cplusplus >= 201103L
3296	/// A non-binding request to reduce capacity() to size().
3297	void
3298	shrink_to_fit() _GLIBCXX_NOEXCEPT
3299	{
3300	#if __cpp_exceptions
3301	if (capacity() > size())
3302	{
3303	try
3304	{ reserve(`0`); }
3305	catch(...)
3306	{ }
3307	}
3308	#endif
3309	}
3310	#endif
3311
3312	/**
3313	* Returns the total number of characters that the %string can hold
3314	* before needing to allocate more memory.
3315	*/
3316	size_type
3317	capacity() const _GLIBCXX_NOEXCEPT
3318	{ return _M_rep()->_M_capacity; }
3319
3320	/**
3321	* @brief Attempt to preallocate enough memory for specified number of
3322	* characters.
3323	* @param __res_arg Number of characters required.
3324	* @throw std::length_error If @a __res_arg exceeds @c max_size().
3325	*
3326	* This function attempts to reserve enough memory for the
3327	* %string to hold the specified number of characters. If the
3328	* number requested is more than max_size(), length_error is
3329	* thrown.
3330	*
3331	* The advantage of this function is that if optimal code is a
3332	* necessity and the user can determine the string length that will be
3333	* required, the user can reserve the memory in %advance, and thus
3334	* prevent a possible reallocation of memory and copying of %string
3335	* data.
3336	*/
3337	void
3338	reserve(size_type __res_arg = `0`);
3339
3340	/**
3341	* Erases the string, making it empty.
3342	*/
3343	// PR 56166: this should not throw.
3344	void
3345	clear()
3346	{ _M_mutate(`0`, this->size(), `0`); }
3347
3348	/**
3349	* Returns true if the %string is empty. Equivalent to
3350	* <code>*this == ""</code>.
3351	*/
3352	bool
3353	empty() const _GLIBCXX_NOEXCEPT
3354	{ return this->size() == `0`; }
3355
3356	// Element access:
3357	/**
3358	* @brief Subscript access to the data contained in the %string.
3359	* @param __pos The index of the character to access.
3360	* @return Read-only (constant) reference to the character.
3361	*
3362	* This operator allows for easy, array-style, data access.
3363	* Note that data access with this operator is unchecked and
3364	* out_of_range lookups are not defined. (For checked lookups
3365	* see at().)
3366	*/
3367	const_reference
3368	operator[] (size_type __pos) const _GLIBCXX_NOEXCEPT
3369	{
3370	__glibcxx_assert(__pos <= size());
3371	return _M_data()[__pos];
3372	}
3373
3374	/**
3375	* @brief Subscript access to the data contained in the %string.
3376	* @param __pos The index of the character to access.
3377	* @return Read/write reference to the character.
3378	*
3379	* This operator allows for easy, array-style, data access.
3380	* Note that data access with this operator is unchecked and
3381	* out_of_range lookups are not defined. (For checked lookups
3382	* see at().) Unshares the string.
3383	*/
3384	reference
3385	operator[](size_type __pos)
3386	{
3387	// Allow pos == size() both in C++98 mode, as v3 extension,
3388	// and in C++11 mode.
3389	__glibcxx_assert(__pos <= size());
3390	// In pedantic mode be strict in C++98 mode.
3391	_GLIBCXX_DEBUG_PEDASSERT(__cplusplus >= `201103L` \|\| __pos < size());
3392	_M_leak();
3393	return _M_data()[__pos];
3394	}
3395
3396	/**
3397	* @brief Provides access to the data contained in the %string.
3398	* @param __n The index of the character to access.
3399	* @return Read-only (const) reference to the character.
3400	* @throw std::out_of_range If @a n is an invalid index.
3401	*
3402	* This function provides for safer data access. The parameter is
3403	* first checked that it is in the range of the string. The function
3404	* throws out_of_range if the check fails.
3405	*/
3406	const_reference
3407	at(size_type __n) const
3408	{
3409	if (__n >= this->size())
3410	__throw_out_of_range_fmt(__N("basic_string::at: __n "
3411	"(which is %zu) >= this->size() "
3412	"(which is %zu)"),
3413	__n, this->size());
3414	return _M_data()[__n];
3415	}
3416
3417	/**
3418	* @brief Provides access to the data contained in the %string.
3419	* @param __n The index of the character to access.
3420	* @return Read/write reference to the character.
3421	* @throw std::out_of_range If @a n is an invalid index.
3422	*
3423	* This function provides for safer data access. The parameter is
3424	* first checked that it is in the range of the string. The function
3425	* throws out_of_range if the check fails. Success results in
3426	* unsharing the string.
3427	*/
3428	reference
3429	at(size_type __n)
3430	{
3431	if (__n >= size())
3432	__throw_out_of_range_fmt(__N("basic_string::at: __n "
3433	"(which is %zu) >= this->size() "
3434	"(which is %zu)"),
3435	__n, this->size());
3436	_M_leak();
3437	return _M_data()[__n];
3438	}
3439
3440	#if __cplusplus >= 201103L
3441	/**
3442	* Returns a read/write reference to the data at the first
3443	* element of the %string.
3444	*/
3445	reference
3446	front()
3447	{
3448	__glibcxx_assert(!empty());
3449	return operator[](`0`);
3450	}
3451
3452	/**
3453	* Returns a read-only (constant) reference to the data at the first
3454	* element of the %string.
3455	*/
3456	const_reference
3457	front() const noexcept
3458	{
3459	__glibcxx_assert(!empty());
3460	return operator[](`0`);
3461	}
3462
3463	/**
3464	* Returns a read/write reference to the data at the last
3465	* element of the %string.
3466	*/
3467	reference
3468	back()
3469	{
3470	__glibcxx_assert(!empty());
3471	return operator[](this->size() - `1`);
3472	}
3473
3474	/**
3475	* Returns a read-only (constant) reference to the data at the
3476	* last element of the %string.
3477	*/
3478	const_reference
3479	back() const noexcept
3480	{
3481	__glibcxx_assert(!empty());
3482	return operator[](this->size() - `1`);
3483	}
3484	#endif
3485
3486	// Modifiers:
3487	/**
3488	* @brief Append a string to this string.
3489	* @param __str The string to append.
3490	* @return Reference to this string.
3491	*/
3492	basic_string&
3493	operator+=(const basic_string& __str)
3494	{ return this->append(__str); }
3495
3496	/**
3497	* @brief Append a C string.
3498	* @param __s The C string to append.
3499	* @return Reference to this string.
3500	*/
3501	basic_string&
3502	operator+=(const _CharT* __s)
3503	{ return this->append(__s); }
3504
3505	/**
3506	* @brief Append a character.
3507	* @param __c The character to append.
3508	* @return Reference to this string.
3509	*/
3510	basic_string&
3511	operator+=(_CharT __c)
3512	{
3513	this->push_back(__c);
3514	return *this;
3515	}
3516
3517	#if __cplusplus >= 201103L
3518	/**
3519	* @brief Append an initializer_list of characters.
3520	* @param __l The initializer_list of characters to be appended.
3521	* @return Reference to this string.
3522	*/
3523	basic_string&
3524	operator+=(initializer_list<_CharT> __l)
3525	{ return this->append(__l.begin(), __l.size()); }
3526	#endif // C++11
3527
3528	/**
3529	* @brief Append a string to this string.
3530	* @param __str The string to append.
3531	* @return Reference to this string.
3532	*/
3533	basic_string&
3534	append(const basic_string& __str);
3535
3536	/**
3537	* @brief Append a substring.
3538	* @param __str The string to append.
3539	* @param __pos Index of the first character of str to append.
3540	* @param __n The number of characters to append.
3541	* @return Reference to this string.
3542	* @throw std::out_of_range if @a __pos is not a valid index.
3543	*
3544	* This function appends @a __n characters from @a __str
3545	* starting at @a __pos to this string. If @a __n is is larger
3546	* than the number of available characters in @a __str, the
3547	* remainder of @a __str is appended.
3548	*/
3549	basic_string&
3550	append(const basic_string& __str, size_type __pos, size_type __n);
3551
3552	/**
3553	* @brief Append a C substring.
3554	* @param __s The C string to append.
3555	* @param __n The number of characters to append.
3556	* @return Reference to this string.
3557	*/
3558	basic_string&
3559	append(const _CharT* __s, size_type __n);
3560
3561	/**
3562	* @brief Append a C string.
3563	* @param __s The C string to append.
3564	* @return Reference to this string.
3565	*/
3566	basic_string&
3567	append(const _CharT* __s)
3568	{
3569	__glibcxx_requires_string(__s);
3570	return this->append(__s, traits_type::length(__s));
3571	}
3572
3573	/**
3574	* @brief Append multiple characters.
3575	* @param __n The number of characters to append.
3576	* @param __c The character to use.
3577	* @return Reference to this string.
3578	*
3579	* Appends __n copies of __c to this string.
3580	*/
3581	basic_string&
3582	append(size_type __n, _CharT __c);
3583
3584	#if __cplusplus >= 201103L
3585	/**
3586	* @brief Append an initializer_list of characters.
3587	* @param __l The initializer_list of characters to append.
3588	* @return Reference to this string.
3589	*/
3590	basic_string&
3591	append(initializer_list<_CharT> __l)
3592	{ return this->append(__l.begin(), __l.size()); }
3593	#endif // C++11
3594
3595	/**
3596	* @brief Append a range of characters.
3597	* @param __first Iterator referencing the first character to append.
3598	* @param __last Iterator marking the end of the range.
3599	* @return Reference to this string.
3600	*
3601	* Appends characters in the range [__first,__last) to this string.
3602	*/
3603	template<class _InputIterator>
3604	basic_string&
3605	append(_InputIterator __first, _InputIterator __last)
3606	{ return this->replace(_M_iend(), _M_iend(), __first, __last); }
3607
3608	/**
3609	* @brief Append a single character.
3610	* @param __c Character to append.
3611	*/
3612	void
3613	push_back(_CharT __c)
3614	{
3615	const size_type __len = `1` + this->size();
3616	if (__len > this->capacity() \|\| _M_rep()->_M_is_shared())
3617	this->reserve(__len);
3618	traits_type::assign(_M_data()[this->size()], __c);
3619	_M_rep()->_M_set_length_and_sharable(__len);
3620	}
3621
3622	/**
3623	* @brief Set value to contents of another string.
3624	* @param __str Source string to use.
3625	* @return Reference to this string.
3626	*/
3627	basic_string&
3628	assign(const basic_string& __str);
3629
3630	#if __cplusplus >= 201103L
3631	/**
3632	* @brief Set value to contents of another string.
3633	* @param __str Source string to use.
3634	* @return Reference to this string.
3635	*
3636	* This function sets this string to the exact contents of @a __str.
3637	* @a __str is a valid, but unspecified string.
3638	*/
3639	// PR 58265, this should be noexcept.
3640	basic_string&
3641	assign(basic_string&& __str)
3642	{
3643	this->swap(__str);
3644	return *this;
3645	}
3646	#endif // C++11
3647
3648	/**
3649	* @brief Set value to a substring of a string.
3650	* @param __str The string to use.
3651	* @param __pos Index of the first character of str.
3652	* @param __n Number of characters to use.
3653	* @return Reference to this string.
3654	* @throw std::out_of_range if @a pos is not a valid index.
3655	*
3656	* This function sets this string to the substring of @a __str
3657	* consisting of @a __n characters at @a __pos. If @a __n is
3658	* is larger than the number of available characters in @a
3659	* __str, the remainder of @a __str is used.
3660	*/
3661	basic_string&
3662	assign(const basic_string& __str, size_type __pos, size_type __n)
3663	{ return this->assign(__str._M_data()
3664	+ __str._M_check(__pos, "basic_string::assign"),
3665	__str._M_limit(__pos, __n)); }
3666
3667	/**
3668	* @brief Set value to a C substring.
3669	* @param __s The C string to use.
3670	* @param __n Number of characters to use.
3671	* @return Reference to this string.
3672	*
3673	* This function sets the value of this string to the first @a __n
3674	* characters of @a __s. If @a __n is is larger than the number of
3675	* available characters in @a __s, the remainder of @a __s is used.
3676	*/
3677	basic_string&
3678	assign(const _CharT* __s, size_type __n);
3679
3680	/**
3681	* @brief Set value to contents of a C string.
3682	* @param __s The C string to use.
3683	* @return Reference to this string.
3684	*
3685	* This function sets the value of this string to the value of @a __s.
3686	* The data is copied, so there is no dependence on @a __s once the
3687	* function returns.
3688	*/
3689	basic_string&
3690	assign(const _CharT* __s)
3691	{
3692	__glibcxx_requires_string(__s);
3693	return this->assign(__s, traits_type::length(__s));
3694	}
3695
3696	/**
3697	* @brief Set value to multiple characters.
3698	* @param __n Length of the resulting string.
3699	* @param __c The character to use.
3700	* @return Reference to this string.
3701	*
3702	* This function sets the value of this string to @a __n copies of
3703	* character @a __c.
3704	*/
3705	basic_string&
3706	assign(size_type __n, _CharT __c)
3707	{ return _M_replace_aux(size_type(`0`), this->size(), __n, __c); }
3708
3709	/**
3710	* @brief Set value to a range of characters.
3711	* @param __first Iterator referencing the first character to append.
3712	* @param __last Iterator marking the end of the range.
3713	* @return Reference to this string.
3714	*
3715	* Sets value of string to characters in the range [__first,__last).
3716	*/
3717	template<class _InputIterator>
3718	basic_string&
3719	assign(_InputIterator __first, _InputIterator __last)
3720	{ return this->replace(_M_ibegin(), _M_iend(), __first, __last); }
3721
3722	#if __cplusplus >= 201103L
3723	/**
3724	* @brief Set value to an initializer_list of characters.
3725	* @param __l The initializer_list of characters to assign.
3726	* @return Reference to this string.
3727	*/
3728	basic_string&
3729	assign(initializer_list<_CharT> __l)
3730	{ return this->assign(__l.begin(), __l.size()); }
3731	#endif // C++11
3732
3733	/**
3734	* @brief Insert multiple characters.
3735	* @param __p Iterator referencing location in string to insert at.
3736	* @param __n Number of characters to insert
3737	* @param __c The character to insert.
3738	* @throw std::length_error If new length exceeds @c max_size().
3739	*
3740	* Inserts @a __n copies of character @a __c starting at the
3741	* position referenced by iterator @a __p. If adding
3742	* characters causes the length to exceed max_size(),
3743	* length_error is thrown. The value of the string doesn't
3744	* change if an error is thrown.
3745	*/
3746	void
3747	insert(iterator __p, size_type __n, _CharT __c)
3748	{ this->replace(__p, __p, __n, __c); }
3749
3750	/**
3751	* @brief Insert a range of characters.
3752	* @param __p Iterator referencing location in string to insert at.
3753	* @param __beg Start of range.
3754	* @param __end End of range.
3755	* @throw std::length_error If new length exceeds @c max_size().
3756	*
3757	* Inserts characters in range [__beg,__end). If adding
3758	* characters causes the length to exceed max_size(),
3759	* length_error is thrown. The value of the string doesn't
3760	* change if an error is thrown.
3761	*/
3762	template<class _InputIterator>
3763	void
3764	insert(iterator __p, _InputIterator __beg, _InputIterator __end)
3765	{ this->replace(__p, __p, __beg, __end); }
3766
3767	#if __cplusplus >= 201103L
3768	/**
3769	* @brief Insert an initializer_list of characters.
3770	* @param __p Iterator referencing location in string to insert at.
3771	* @param __l The initializer_list of characters to insert.
3772	* @throw std::length_error If new length exceeds @c max_size().
3773	*/
3774	void
3775	insert(iterator __p, initializer_list<_CharT> __l)
3776	{
3777	_GLIBCXX_DEBUG_PEDASSERT(__p >= _M_ibegin() && __p <= _M_iend());
3778	this->insert(__p - _M_ibegin(), __l.begin(), __l.size());
3779	}
3780	#endif // C++11
3781
3782	/**
3783	* @brief Insert value of a string.
3784	* @param __pos1 Iterator referencing location in string to insert at.
3785	* @param __str The string to insert.
3786	* @return Reference to this string.
3787	* @throw std::length_error If new length exceeds @c max_size().
3788	*
3789	* Inserts value of @a __str starting at @a __pos1. If adding
3790	* characters causes the length to exceed max_size(),
3791	* length_error is thrown. The value of the string doesn't
3792	* change if an error is thrown.
3793	*/
3794	basic_string&
3795	insert(size_type __pos1, const basic_string& __str)
3796	{ return this->insert(__pos1, __str, size_type(`0`), __str.size()); }
3797
3798	/**
3799	* @brief Insert a substring.
3800	* @param __pos1 Iterator referencing location in string to insert at.
3801	* @param __str The string to insert.
3802	* @param __pos2 Start of characters in str to insert.
3803	* @param __n Number of characters to insert.
3804	* @return Reference to this string.
3805	* @throw std::length_error If new length exceeds @c max_size().
3806	* @throw std::out_of_range If @a pos1 > size() or
3807	* @a __pos2 > @a str.size().
3808	*
3809	* Starting at @a pos1, insert @a __n character of @a __str
3810	* beginning with @a __pos2. If adding characters causes the
3811	* length to exceed max_size(), length_error is thrown. If @a
3812	* __pos1 is beyond the end of this string or @a __pos2 is
3813	* beyond the end of @a __str, out_of_range is thrown. The
3814	* value of the string doesn't change if an error is thrown.
3815	*/
3816	basic_string&
3817	insert(size_type __pos1, const basic_string& __str,
3818	size_type __pos2, size_type __n)
3819	{ return this->insert(__pos1, __str._M_data()
3820	+ __str._M_check(__pos2, "basic_string::insert"),
3821	__str._M_limit(__pos2, __n)); }
3822
3823	/**
3824	* @brief Insert a C substring.
3825	* @param __pos Iterator referencing location in string to insert at.
3826	* @param __s The C string to insert.
3827	* @param __n The number of characters to insert.
3828	* @return Reference to this string.
3829	* @throw std::length_error If new length exceeds @c max_size().
3830	* @throw std::out_of_range If @a __pos is beyond the end of this
3831	* string.
3832	*
3833	* Inserts the first @a __n characters of @a __s starting at @a
3834	* __pos. If adding characters causes the length to exceed
3835	* max_size(), length_error is thrown. If @a __pos is beyond
3836	* end(), out_of_range is thrown. The value of the string
3837	* doesn't change if an error is thrown.
3838	*/
3839	basic_string&
3840	insert(size_type __pos, const _CharT* __s, size_type __n);
3841
3842	/**
3843	* @brief Insert a C string.
3844	* @param __pos Iterator referencing location in string to insert at.
3845	* @param __s The C string to insert.
3846	* @return Reference to this string.
3847	* @throw std::length_error If new length exceeds @c max_size().
3848	* @throw std::out_of_range If @a pos is beyond the end of this
3849	* string.
3850	*
3851	* Inserts the first @a n characters of @a __s starting at @a __pos. If
3852	* adding characters causes the length to exceed max_size(),
3853	* length_error is thrown. If @a __pos is beyond end(), out_of_range is
3854	* thrown. The value of the string doesn't change if an error is
3855	* thrown.
3856	*/
3857	basic_string&
3858	insert(size_type __pos, const _CharT* __s)
3859	{
3860	__glibcxx_requires_string(__s);
3861	return this->insert(__pos, __s, traits_type::length(__s));
3862	}
3863
3864	/**
3865	* @brief Insert multiple characters.
3866	* @param __pos Index in string to insert at.
3867	* @param __n Number of characters to insert
3868	* @param __c The character to insert.
3869	* @return Reference to this string.
3870	* @throw std::length_error If new length exceeds @c max_size().
3871	* @throw std::out_of_range If @a __pos is beyond the end of this
3872	* string.
3873	*
3874	* Inserts @a __n copies of character @a __c starting at index
3875	* @a __pos. If adding characters causes the length to exceed
3876	* max_size(), length_error is thrown. If @a __pos > length(),
3877	* out_of_range is thrown. The value of the string doesn't
3878	* change if an error is thrown.
3879	*/
3880	basic_string&
3881	insert(size_type __pos, size_type __n, _CharT __c)
3882	{ return _M_replace_aux(_M_check(__pos, "basic_string::insert"),
3883	size_type(`0`), __n, __c); }
3884
3885	/**
3886	* @brief Insert one character.
3887	* @param __p Iterator referencing position in string to insert at.
3888	* @param __c The character to insert.
3889	* @return Iterator referencing newly inserted char.
3890	* @throw std::length_error If new length exceeds @c max_size().
3891	*
3892	* Inserts character @a __c at position referenced by @a __p.
3893	* If adding character causes the length to exceed max_size(),
3894	* length_error is thrown. If @a __p is beyond end of string,
3895	* out_of_range is thrown. The value of the string doesn't
3896	* change if an error is thrown.
3897	*/
3898	iterator
3899	insert(iterator __p, _CharT __c)
3900	{
3901	_GLIBCXX_DEBUG_PEDASSERT(__p >= _M_ibegin() && __p <= _M_iend());
3902	const size_type __pos = __p - _M_ibegin();
3903	_M_replace_aux(__pos, size_type(`0`), size_type(`1`), __c);
3904	_M_rep()->_M_set_leaked();
3905	return iterator(_M_data() + __pos);
3906	}
3907
3908	/**
3909	* @brief Remove characters.
3910	* @param __pos Index of first character to remove (default 0).
3911	* @param __n Number of characters to remove (default remainder).
3912	* @return Reference to this string.
3913	* @throw std::out_of_range If @a pos is beyond the end of this
3914	* string.
3915	*
3916	* Removes @a __n characters from this string starting at @a
3917	* __pos. The length of the string is reduced by @a __n. If
3918	* there are < @a __n characters to remove, the remainder of
3919	* the string is truncated. If @a __p is beyond end of string,
3920	* out_of_range is thrown. The value of the string doesn't
3921	* change if an error is thrown.
3922	*/
3923	basic_string&
3924	erase(size_type __pos = `0`, size_type __n = npos)
3925	{
3926	_M_mutate(_M_check(__pos, "basic_string::erase"),
3927	_M_limit(__pos, __n), size_type(`0`));
3928	return *this;
3929	}
3930
3931	/**
3932	* @brief Remove one character.
3933	* @param __position Iterator referencing the character to remove.
3934	* @return iterator referencing same location after removal.
3935	*
3936	* Removes the character at @a __position from this string. The value
3937	* of the string doesn't change if an error is thrown.
3938	*/
3939	iterator
3940	erase(iterator __position)
3941	{
3942	_GLIBCXX_DEBUG_PEDASSERT(__position >= _M_ibegin()
3943	&& __position < _M_iend());
3944	const size_type __pos = __position - _M_ibegin();
3945	_M_mutate(__pos, size_type(`1`), size_type(`0`));
3946	_M_rep()->_M_set_leaked();
3947	return iterator(_M_data() + __pos);
3948	}
3949
3950	/**
3951	* @brief Remove a range of characters.
3952	* @param __first Iterator referencing the first character to remove.
3953	* @param __last Iterator referencing the end of the range.
3954	* @return Iterator referencing location of first after removal.
3955	*
3956	* Removes the characters in the range [first,last) from this string.
3957	* The value of the string doesn't change if an error is thrown.
3958	*/
3959	iterator
3960	erase(iterator __first, iterator __last);
3961
3962	#if __cplusplus >= 201103L
3963	/**
3964	* @brief Remove the last character.
3965	*
3966	* The string must be non-empty.
3967	*/
3968	void
3969	pop_back() // FIXME C++11: should be noexcept.
3970	{
3971	__glibcxx_assert(!empty());
3972	erase(size() - `1`, `1`);
3973	}
3974	#endif // C++11
3975
3976	/**
3977	* @brief Replace characters with value from another string.
3978	* @param __pos Index of first character to replace.
3979	* @param __n Number of characters to be replaced.
3980	* @param __str String to insert.
3981	* @return Reference to this string.
3982	* @throw std::out_of_range If @a pos is beyond the end of this
3983	* string.
3984	* @throw std::length_error If new length exceeds @c max_size().
3985	*
3986	* Removes the characters in the range [__pos,__pos+__n) from
3987	* this string. In place, the value of @a __str is inserted.
3988	* If @a __pos is beyond end of string, out_of_range is thrown.
3989	* If the length of the result exceeds max_size(), length_error
3990	* is thrown. The value of the string doesn't change if an
3991	* error is thrown.
3992	*/
3993	basic_string&
3994	replace(size_type __pos, size_type __n, const basic_string& __str)
3995	{ return this->replace(__pos, __n, __str._M_data(), __str.size()); }
3996
3997	/**
3998	* @brief Replace characters with value from another string.
3999	* @param __pos1 Index of first character to replace.
4000	* @param __n1 Number of characters to be replaced.
4001	* @param __str String to insert.
4002	* @param __pos2 Index of first character of str to use.
4003	* @param __n2 Number of characters from str to use.
4004	* @return Reference to this string.
4005	* @throw std::out_of_range If @a __pos1 > size() or @a __pos2 >
4006	* __str.size().
4007	* @throw std::length_error If new length exceeds @c max_size().
4008	*
4009	* Removes the characters in the range [__pos1,__pos1 + n) from this
4010	* string. In place, the value of @a __str is inserted. If @a __pos is
4011	* beyond end of string, out_of_range is thrown. If the length of the
4012	* result exceeds max_size(), length_error is thrown. The value of the
4013	* string doesn't change if an error is thrown.
4014	*/
4015	basic_string&
4016	replace(size_type __pos1, size_type __n1, const basic_string& __str,
4017	size_type __pos2, size_type __n2)
4018	{ return this->replace(__pos1, __n1, __str._M_data()
4019	+ __str._M_check(__pos2, "basic_string::replace"),
4020	__str._M_limit(__pos2, __n2)); }
4021
4022	/**
4023	* @brief Replace characters with value of a C substring.
4024	* @param __pos Index of first character to replace.
4025	* @param __n1 Number of characters to be replaced.
4026	* @param __s C string to insert.
4027	* @param __n2 Number of characters from @a s to use.
4028	* @return Reference to this string.
4029	* @throw std::out_of_range If @a pos1 > size().
4030	* @throw std::length_error If new length exceeds @c max_size().
4031	*
4032	* Removes the characters in the range [__pos,__pos + __n1)
4033	* from this string. In place, the first @a __n2 characters of
4034	* @a __s are inserted, or all of @a __s if @a __n2 is too large. If
4035	* @a __pos is beyond end of string, out_of_range is thrown. If
4036	* the length of result exceeds max_size(), length_error is
4037	* thrown. The value of the string doesn't change if an error
4038	* is thrown.
4039	*/
4040	basic_string&
4041	replace(size_type __pos, size_type __n1, const _CharT* __s,
4042	size_type __n2);
4043
4044	/**
4045	* @brief Replace characters with value of a C string.
4046	* @param __pos Index of first character to replace.
4047	* @param __n1 Number of characters to be replaced.
4048	* @param __s C string to insert.
4049	* @return Reference to this string.
4050	* @throw std::out_of_range If @a pos > size().
4051	* @throw std::length_error If new length exceeds @c max_size().
4052	*
4053	* Removes the characters in the range [__pos,__pos + __n1)
4054	* from this string. In place, the characters of @a __s are
4055	* inserted. If @a __pos is beyond end of string, out_of_range
4056	* is thrown. If the length of result exceeds max_size(),
4057	* length_error is thrown. The value of the string doesn't
4058	* change if an error is thrown.
4059	*/
4060	basic_string&
4061	replace(size_type __pos, size_type __n1, const _CharT* __s)
4062	{
4063	__glibcxx_requires_string(__s);
4064	return this->replace(__pos, __n1, __s, traits_type::length(__s));
4065	}
4066
4067	/**
4068	* @brief Replace characters with multiple characters.
4069	* @param __pos Index of first character to replace.
4070	* @param __n1 Number of characters to be replaced.
4071	* @param __n2 Number of characters to insert.
4072	* @param __c Character to insert.
4073	* @return Reference to this string.
4074	* @throw std::out_of_range If @a __pos > size().
4075	* @throw std::length_error If new length exceeds @c max_size().
4076	*
4077	* Removes the characters in the range [pos,pos + n1) from this
4078	* string. In place, @a __n2 copies of @a __c are inserted.
4079	* If @a __pos is beyond end of string, out_of_range is thrown.
4080	* If the length of result exceeds max_size(), length_error is
4081	* thrown. The value of the string doesn't change if an error
4082	* is thrown.
4083	*/
4084	basic_string&
4085	replace(size_type __pos, size_type __n1, size_type __n2, _CharT __c)
4086	{ return _M_replace_aux(_M_check(__pos, "basic_string::replace"),
4087	_M_limit(__pos, __n1), __n2, __c); }
4088
4089	/**
4090	* @brief Replace range of characters with string.
4091	* @param __i1 Iterator referencing start of range to replace.
4092	* @param __i2 Iterator referencing end of range to replace.
4093	* @param __str String value to insert.
4094	* @return Reference to this string.
4095	* @throw std::length_error If new length exceeds @c max_size().
4096	*
4097	* Removes the characters in the range [__i1,__i2). In place,
4098	* the value of @a __str is inserted. If the length of result
4099	* exceeds max_size(), length_error is thrown. The value of
4100	* the string doesn't change if an error is thrown.
4101	*/
4102	basic_string&
4103	replace(iterator __i1, iterator __i2, const basic_string& __str)
4104	{ return this->replace(__i1, __i2, __str._M_data(), __str.size()); }
4105
4106	/**
4107	* @brief Replace range of characters with C substring.
4108	* @param __i1 Iterator referencing start of range to replace.
4109	* @param __i2 Iterator referencing end of range to replace.
4110	* @param __s C string value to insert.
4111	* @param __n Number of characters from s to insert.
4112	* @return Reference to this string.
4113	* @throw std::length_error If new length exceeds @c max_size().
4114	*
4115	* Removes the characters in the range [__i1,__i2). In place,
4116	* the first @a __n characters of @a __s are inserted. If the
4117	* length of result exceeds max_size(), length_error is thrown.
4118	* The value of the string doesn't change if an error is
4119	* thrown.
4120	*/
4121	basic_string&
4122	replace(iterator __i1, iterator __i2, const _CharT* __s, size_type __n)
4123	{
4124	_GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
4125	&& __i2 <= _M_iend());
4126	return this->replace(__i1 - _M_ibegin(), __i2 - __i1, __s, __n);
4127	}
4128
4129	/**
4130	* @brief Replace range of characters with C string.
4131	* @param __i1 Iterator referencing start of range to replace.
4132	* @param __i2 Iterator referencing end of range to replace.
4133	* @param __s C string value to insert.
4134	* @return Reference to this string.
4135	* @throw std::length_error If new length exceeds @c max_size().
4136	*
4137	* Removes the characters in the range [__i1,__i2). In place,
4138	* the characters of @a __s are inserted. If the length of
4139	* result exceeds max_size(), length_error is thrown. The
4140	* value of the string doesn't change if an error is thrown.
4141	*/
4142	basic_string&
4143	replace(iterator __i1, iterator __i2, const _CharT* __s)
4144	{
4145	__glibcxx_requires_string(__s);
4146	return this->replace(__i1, __i2, __s, traits_type::length(__s));
4147	}
4148
4149	/**
4150	* @brief Replace range of characters with multiple characters
4151	* @param __i1 Iterator referencing start of range to replace.
4152	* @param __i2 Iterator referencing end of range to replace.
4153	* @param __n Number of characters to insert.
4154	* @param __c Character to insert.
4155	* @return Reference to this string.
4156	* @throw std::length_error If new length exceeds @c max_size().
4157	*
4158	* Removes the characters in the range [__i1,__i2). In place,
4159	* @a __n copies of @a __c are inserted. If the length of
4160	* result exceeds max_size(), length_error is thrown. The
4161	* value of the string doesn't change if an error is thrown.
4162	*/
4163	basic_string&
4164	replace(iterator __i1, iterator __i2, size_type __n, _CharT __c)
4165	{
4166	_GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
4167	&& __i2 <= _M_iend());
4168	return _M_replace_aux(__i1 - _M_ibegin(), __i2 - __i1, __n, __c);
4169	}
4170
4171	/**
4172	* @brief Replace range of characters with range.
4173	* @param __i1 Iterator referencing start of range to replace.
4174	* @param __i2 Iterator referencing end of range to replace.
4175	* @param __k1 Iterator referencing start of range to insert.
4176	* @param __k2 Iterator referencing end of range to insert.
4177	* @return Reference to this string.
4178	* @throw std::length_error If new length exceeds @c max_size().
4179	*
4180	* Removes the characters in the range [__i1,__i2). In place,
4181	* characters in the range [__k1,__k2) are inserted. If the
4182	* length of result exceeds max_size(), length_error is thrown.
4183	* The value of the string doesn't change if an error is
4184	* thrown.
4185	*/
4186	template<class _InputIterator>
4187	basic_string&
4188	replace(iterator __i1, iterator __i2,
4189	_InputIterator __k1, _InputIterator __k2)
4190	{
4191	_GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
4192	&& __i2 <= _M_iend());
4193	__glibcxx_requires_valid_range(__k1, __k2);
4194	typedef typename std::__is_integer<_InputIterator>::__type _Integral;
4195	return _M_replace_dispatch(__i1, __i2, __k1, __k2, _Integral());
4196	}
4197
4198	// Specializations for the common case of pointer and iterator:
4199	// useful to avoid the overhead of temporary buffering in _M_replace.
4200	basic_string&
4201	replace(iterator __i1, iterator __i2, _CharT* __k1, _CharT* __k2)
4202	{
4203	_GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
4204	&& __i2 <= _M_iend());
4205	__glibcxx_requires_valid_range(__k1, __k2);
4206	return this->replace(__i1 - _M_ibegin(), __i2 - __i1,
4207	__k1, __k2 - __k1);
4208	}
4209
4210	basic_string&
4211	replace(iterator __i1, iterator __i2,
4212	const _CharT* __k1, const _CharT* __k2)
4213	{
4214	_GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
4215	&& __i2 <= _M_iend());
4216	__glibcxx_requires_valid_range(__k1, __k2);
4217	return this->replace(__i1 - _M_ibegin(), __i2 - __i1,
4218	__k1, __k2 - __k1);
4219	}
4220
4221	basic_string&
4222	replace(iterator __i1, iterator __i2, iterator __k1, iterator __k2)
4223	{
4224	_GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
4225	&& __i2 <= _M_iend());
4226	__glibcxx_requires_valid_range(__k1, __k2);
4227	return this->replace(__i1 - _M_ibegin(), __i2 - __i1,
4228	__k1.base(), __k2 - __k1);
4229	}
4230
4231	basic_string&
4232	replace(iterator __i1, iterator __i2,
4233	const_iterator __k1, const_iterator __k2)
4234	{
4235	_GLIBCXX_DEBUG_PEDASSERT(_M_ibegin() <= __i1 && __i1 <= __i2
4236	&& __i2 <= _M_iend());
4237	__glibcxx_requires_valid_range(__k1, __k2);
4238	return this->replace(__i1 - _M_ibegin(), __i2 - __i1,
4239	__k1.base(), __k2 - __k1);
4240	}
4241
4242	#if __cplusplus >= 201103L
4243	/**
4244	* @brief Replace range of characters with initializer_list.
4245	* @param __i1 Iterator referencing start of range to replace.
4246	* @param __i2 Iterator referencing end of range to replace.
4247	* @param __l The initializer_list of characters to insert.
4248	* @return Reference to this string.
4249	* @throw std::length_error If new length exceeds @c max_size().
4250	*
4251	* Removes the characters in the range [__i1,__i2). In place,
4252	* characters in the range [__k1,__k2) are inserted. If the
4253	* length of result exceeds max_size(), length_error is thrown.
4254	* The value of the string doesn't change if an error is
4255	* thrown.
4256	*/
4257	basic_string& replace(iterator __i1, iterator __i2,
4258	initializer_list<_CharT> __l)
4259	{ return this->replace(__i1, __i2, __l.begin(), __l.end()); }
4260	#endif // C++11
4261
4262	private:
4263	template<class _Integer>
4264	basic_string&
4265	_M_replace_dispatch(iterator __i1, iterator __i2, _Integer __n,
4266	_Integer __val, __true_type)
4267	{ return _M_replace_aux(__i1 - _M_ibegin(), __i2 - __i1, __n, __val); }
4268
4269	template<class _InputIterator>
4270	basic_string&
4271	_M_replace_dispatch(iterator __i1, iterator __i2, _InputIterator __k1,
4272	_InputIterator __k2, __false_type);
4273
4274	basic_string&
4275	_M_replace_aux(size_type __pos1, size_type __n1, size_type __n2,
4276	_CharT __c);
4277
4278	basic_string&
4279	_M_replace_safe(size_type __pos1, size_type __n1, const _CharT* __s,
4280	size_type __n2);
4281
4282	// _S_construct_aux is used to implement the 21.3.1 para 15 which
4283	// requires special behaviour if _InIter is an integral type
4284	template<class _InIterator>
4285	static _CharT*
4286	_S_construct_aux(_InIterator __beg, _InIterator __end,
4287	const _Alloc& __a, __false_type)
4288	{
4289	typedef typename iterator_traits<_InIterator>::iterator_category _Tag;
4290	return _S_construct(__beg, __end, __a, _Tag());
4291	}
4292
4293	// _GLIBCXX_RESOLVE_LIB_DEFECTS
4294	// 438. Ambiguity in the "do the right thing" clause
4295	template<class _Integer>
4296	static _CharT*
4297	_S_construct_aux(_Integer __beg, _Integer __end,
4298	const _Alloc& __a, __true_type)
4299	{ return _S_construct_aux_2(static_cast<size_type>(__beg),
4300	__end, __a); }
4301
4302	static _CharT*
4303	_S_construct_aux_2(size_type __req, _CharT __c, const _Alloc& __a)
4304	{ return _S_construct(__req, __c, __a); }
4305
4306	template<class _InIterator>
4307	static _CharT*
4308	_S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a)
4309	{
4310	typedef typename std::__is_integer<_InIterator>::__type _Integral;
4311	return _S_construct_aux(__beg, __end, __a, _Integral());
4312	}
4313
4314	// For Input Iterators, used in istreambuf_iterators, etc.
4315	template<class _InIterator>
4316	static _CharT*
4317	_S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a,
4318	input_iterator_tag);
4319
4320	// For forward_iterators up to random_access_iterators, used for
4321	// string::iterator, _CharT, etc.*
4322	template<class _FwdIterator>
4323	static _CharT*
4324	_S_construct(_FwdIterator __beg, _FwdIterator __end, const _Alloc& __a,
4325	forward_iterator_tag);
4326
4327	static _CharT*
4328	_S_construct(size_type __req, _CharT __c, const _Alloc& __a);
4329
4330	public:
4331
4332	/**
4333	* @brief Copy substring into C string.
4334	* @param __s C string to copy value into.
4335	* @param __n Number of characters to copy.
4336	* @param __pos Index of first character to copy.
4337	* @return Number of characters actually copied
4338	* @throw std::out_of_range If __pos > size().
4339	*
4340	* Copies up to @a __n characters starting at @a __pos into the
4341	* C string @a __s. If @a __pos is %greater than size(),
4342	* out_of_range is thrown.
4343	*/
4344	size_type
4345	copy(_CharT* __s, size_type __n, size_type __pos = `0`) const;
4346
4347	/**
4348	* @brief Swap contents with another string.
4349	* @param __s String to swap with.
4350	*
4351	* Exchanges the contents of this string with that of @a __s in constant
4352	* time.
4353	*/
4354	// PR 58265, this should be noexcept.
4355	void
4356	swap(basic_string& __s);
4357
4358	// String operations:
4359	/**
4360	* @brief Return const pointer to null-terminated contents.
4361	*
4362	* This is a handle to internal data. Do not modify or dire things may
4363	* happen.
4364	*/
4365	const _CharT*
4366	c_str() const _GLIBCXX_NOEXCEPT
4367	{ return _M_data(); }
4368
4369	/**
4370	* @brief Return const pointer to contents.
4371	*
4372	* This is a handle to internal data. Do not modify or dire things may
4373	* happen.
4374	*/
4375	const _CharT*
4376	data() const _GLIBCXX_NOEXCEPT
4377	{ return _M_data(); }
4378
4379	/**
4380	* @brief Return copy of allocator used to construct this string.
4381	*/
4382	allocator_type
4383	get_allocator() const _GLIBCXX_NOEXCEPT
4384	{ return _M_dataplus; }
4385
4386	/**
4387	* @brief Find position of a C substring.
4388	* @param __s C string to locate.
4389	* @param __pos Index of character to search from.
4390	* @param __n Number of characters from @a s to search for.
4391	* @return Index of start of first occurrence.
4392	*
4393	* Starting from @a __pos, searches forward for the first @a
4394	* __n characters in @a __s within this string. If found,
4395	* returns the index where it begins. If not found, returns
4396	* npos.
4397	*/
4398	size_type
4399	find(const _CharT* __s, size_type __pos, size_type __n) const;
4400
4401	/**
4402	* @brief Find position of a string.
4403	* @param __str String to locate.
4404	* @param __pos Index of character to search from (default 0).
4405	* @return Index of start of first occurrence.
4406	*
4407	* Starting from @a __pos, searches forward for value of @a __str within
4408	* this string. If found, returns the index where it begins. If not
4409	* found, returns npos.
4410	*/
4411	size_type
4412	find(const basic_string& __str, size_type __pos = `0`) const
4413	_GLIBCXX_NOEXCEPT
4414	{ return this->find(__str.data(), __pos, __str.size()); }
4415
4416	/**
4417	* @brief Find position of a C string.
4418	* @param __s C string to locate.
4419	* @param __pos Index of character to search from (default 0).
4420	* @return Index of start of first occurrence.
4421	*
4422	* Starting from @a __pos, searches forward for the value of @a
4423	* __s within this string. If found, returns the index where
4424	* it begins. If not found, returns npos.
4425	*/
4426	size_type
4427	find(const _CharT* __s, size_type __pos = `0`) const
4428	{
4429	__glibcxx_requires_string(__s);
4430	return this->find(__s, __pos, traits_type::length(__s));
4431	}
4432
4433	/**
4434	* @brief Find position of a character.
4435	* @param __c Character to locate.
4436	* @param __pos Index of character to search from (default 0).
4437	* @return Index of first occurrence.
4438	*
4439	* Starting from @a __pos, searches forward for @a __c within
4440	* this string. If found, returns the index where it was
4441	* found. If not found, returns npos.
4442	*/
4443	size_type
4444	find(_CharT __c, size_type __pos = `0`) const _GLIBCXX_NOEXCEPT;
4445
4446	/**
4447	* @brief Find last position of a string.
4448	* @param __str String to locate.
4449	* @param __pos Index of character to search back from (default end).
4450	* @return Index of start of last occurrence.
4451	*
4452	* Starting from @a __pos, searches backward for value of @a
4453	* __str within this string. If found, returns the index where
4454	* it begins. If not found, returns npos.
4455	*/
4456	size_type
4457	rfind(const basic_string& __str, size_type __pos = npos) const
4458	_GLIBCXX_NOEXCEPT
4459	{ return this->rfind(__str.data(), __pos, __str.size()); }
4460
4461	/**
4462	* @brief Find last position of a C substring.
4463	* @param __s C string to locate.
4464	* @param __pos Index of character to search back from.
4465	* @param __n Number of characters from s to search for.
4466	* @return Index of start of last occurrence.
4467	*
4468	* Starting from @a __pos, searches backward for the first @a
4469	* __n characters in @a __s within this string. If found,
4470	* returns the index where it begins. If not found, returns
4471	* npos.
4472	*/
4473	size_type
4474	rfind(const _CharT* __s, size_type __pos, size_type __n) const;
4475
4476	/**
4477	* @brief Find last position of a C string.
4478	* @param __s C string to locate.
4479	* @param __pos Index of character to start search at (default end).
4480	* @return Index of start of last occurrence.
4481	*
4482	* Starting from @a __pos, searches backward for the value of
4483	* @a __s within this string. If found, returns the index
4484	* where it begins. If not found, returns npos.
4485	*/
4486	size_type
4487	rfind(const _CharT* __s, size_type __pos = npos) const
4488	{
4489	__glibcxx_requires_string(__s);
4490	return this->rfind(__s, __pos, traits_type::length(__s));
4491	}
4492
4493	/**
4494	* @brief Find last position of a character.
4495	* @param __c Character to locate.
4496	* @param __pos Index of character to search back from (default end).
4497	* @return Index of last occurrence.
4498	*
4499	* Starting from @a __pos, searches backward for @a __c within
4500	* this string. If found, returns the index where it was
4501	* found. If not found, returns npos.
4502	*/
4503	size_type
4504	rfind(_CharT __c, size_type __pos = npos) const _GLIBCXX_NOEXCEPT;
4505
4506	/**
4507	* @brief Find position of a character of string.
4508	* @param __str String containing characters to locate.
4509	* @param __pos Index of character to search from (default 0).
4510	* @return Index of first occurrence.
4511	*
4512	* Starting from @a __pos, searches forward for one of the
4513	* characters of @a __str within this string. If found,
4514	* returns the index where it was found. If not found, returns
4515	* npos.
4516	*/
4517	size_type
4518	find_first_of(const basic_string& __str, size_type __pos = `0`) const
4519	_GLIBCXX_NOEXCEPT
4520	{ return this->find_first_of(__str.data(), __pos, __str.size()); }
4521
4522	/**
4523	* @brief Find position of a character of C substring.
4524	* @param __s String containing characters to locate.
4525	* @param __pos Index of character to search from.
4526	* @param __n Number of characters from s to search for.
4527	* @return Index of first occurrence.
4528	*
4529	* Starting from @a __pos, searches forward for one of the
4530	* first @a __n characters of @a __s within this string. If
4531	* found, returns the index where it was found. If not found,
4532	* returns npos.
4533	*/
4534	size_type
4535	find_first_of(const _CharT* __s, size_type __pos, size_type __n) const;
4536
4537	/**
4538	* @brief Find position of a character of C string.
4539	* @param __s String containing characters to locate.
4540	* @param __pos Index of character to search from (default 0).
4541	* @return Index of first occurrence.
4542	*
4543	* Starting from @a __pos, searches forward for one of the
4544	* characters of @a __s within this string. If found, returns
4545	* the index where it was found. If not found, returns npos.
4546	*/
4547	size_type
4548	find_first_of(const _CharT* __s, size_type __pos = `0`) const
4549	{
4550	__glibcxx_requires_string(__s);
4551	return this->find_first_of(__s, __pos, traits_type::length(__s));
4552	}
4553
4554	/**
4555	* @brief Find position of a character.
4556	* @param __c Character to locate.
4557	* @param __pos Index of character to search from (default 0).
4558	* @return Index of first occurrence.
4559	*
4560	* Starting from @a __pos, searches forward for the character
4561	* @a __c within this string. If found, returns the index
4562	* where it was found. If not found, returns npos.
4563	*
4564	* Note: equivalent to find(__c, __pos).
4565	*/
4566	size_type
4567	find_first_of(_CharT __c, size_type __pos = `0`) const _GLIBCXX_NOEXCEPT
4568	{ return this->find(__c, __pos); }
4569
4570	/**
4571	* @brief Find last position of a character of string.
4572	* @param __str String containing characters to locate.
4573	* @param __pos Index of character to search back from (default end).
4574	* @return Index of last occurrence.
4575	*
4576	* Starting from @a __pos, searches backward for one of the
4577	* characters of @a __str within this string. If found,
4578	* returns the index where it was found. If not found, returns
4579	* npos.
4580	*/
4581	size_type
4582	find_last_of(const basic_string& __str, size_type __pos = npos) const
4583	_GLIBCXX_NOEXCEPT
4584	{ return this->find_last_of(__str.data(), __pos, __str.size()); }
4585
4586	/**
4587	* @brief Find last position of a character of C substring.
4588	* @param __s C string containing characters to locate.
4589	* @param __pos Index of character to search back from.
4590	* @param __n Number of characters from s to search for.
4591	* @return Index of last occurrence.
4592	*
4593	* Starting from @a __pos, searches backward for one of the
4594	* first @a __n characters of @a __s within this string. If
4595	* found, returns the index where it was found. If not found,
4596	* returns npos.
4597	*/
4598	size_type
4599	find_last_of(const _CharT* __s, size_type __pos, size_type __n) const;
4600
4601	/**
4602	* @brief Find last position of a character of C string.
4603	* @param __s C string containing characters to locate.
4604	* @param __pos Index of character to search back from (default end).
4605	* @return Index of last occurrence.
4606	*
4607	* Starting from @a __pos, searches backward for one of the
4608	* characters of @a __s within this string. If found, returns
4609	* the index where it was found. If not found, returns npos.
4610	*/
4611	size_type
4612	find_last_of(const _CharT* __s, size_type __pos = npos) const
4613	{
4614	__glibcxx_requires_string(__s);
4615	return this->find_last_of(__s, __pos, traits_type::length(__s));
4616	}
4617
4618	/**
4619	* @brief Find last position of a character.
4620	* @param __c Character to locate.
4621	* @param __pos Index of character to search back from (default end).
4622	* @return Index of last occurrence.
4623	*
4624	* Starting from @a __pos, searches backward for @a __c within
4625	* this string. If found, returns the index where it was
4626	* found. If not found, returns npos.
4627	*
4628	* Note: equivalent to rfind(__c, __pos).
4629	*/
4630	size_type
4631	find_last_of(_CharT __c, size_type __pos = npos) const _GLIBCXX_NOEXCEPT
4632	{ return this->rfind(__c, __pos); }
4633
4634	/**
4635	* @brief Find position of a character not in string.
4636	* @param __str String containing characters to avoid.
4637	* @param __pos Index of character to search from (default 0).
4638	* @return Index of first occurrence.
4639	*
4640	* Starting from @a __pos, searches forward for a character not contained
4641	* in @a __str within this string. If found, returns the index where it
4642	* was found. If not found, returns npos.
4643	*/
4644	size_type
4645	find_first_not_of(const basic_string& __str, size_type __pos = `0`) const
4646	_GLIBCXX_NOEXCEPT
4647	{ return this->find_first_not_of(__str.data(), __pos, __str.size()); }
4648
4649	/**
4650	* @brief Find position of a character not in C substring.
4651	* @param __s C string containing characters to avoid.
4652	* @param __pos Index of character to search from.
4653	* @param __n Number of characters from __s to consider.
4654	* @return Index of first occurrence.
4655	*
4656	* Starting from @a __pos, searches forward for a character not
4657	* contained in the first @a __n characters of @a __s within
4658	* this string. If found, returns the index where it was
4659	* found. If not found, returns npos.
4660	*/
4661	size_type
4662	find_first_not_of(const _CharT* __s, size_type __pos,
4663	size_type __n) const;
4664
4665	/**
4666	* @brief Find position of a character not in C string.
4667	* @param __s C string containing characters to avoid.
4668	* @param __pos Index of character to search from (default 0).
4669	* @return Index of first occurrence.
4670	*
4671	* Starting from @a __pos, searches forward for a character not
4672	* contained in @a __s within this string. If found, returns
4673	* the index where it was found. If not found, returns npos.
4674	*/
4675	size_type
4676	find_first_not_of(const _CharT* __s, size_type __pos = `0`) const
4677	{
4678	__glibcxx_requires_string(__s);
4679	return this->find_first_not_of(__s, __pos, traits_type::length(__s));
4680	}
4681
4682	/**
4683	* @brief Find position of a different character.
4684	* @param __c Character to avoid.
4685	* @param __pos Index of character to search from (default 0).
4686	* @return Index of first occurrence.
4687	*
4688	* Starting from @a __pos, searches forward for a character
4689	* other than @a __c within this string. If found, returns the
4690	* index where it was found. If not found, returns npos.
4691	*/
4692	size_type
4693	find_first_not_of(_CharT __c, size_type __pos = `0`) const
4694	_GLIBCXX_NOEXCEPT;
4695
4696	/**
4697	* @brief Find last position of a character not in string.
4698	* @param __str String containing characters to avoid.
4699	* @param __pos Index of character to search back from (default end).
4700	* @return Index of last occurrence.
4701	*
4702	* Starting from @a __pos, searches backward for a character
4703	* not contained in @a __str within this string. If found,
4704	* returns the index where it was found. If not found, returns
4705	* npos.
4706	*/
4707	size_type
4708	find_last_not_of(const basic_string& __str, size_type __pos = npos) const
4709	_GLIBCXX_NOEXCEPT
4710	{ return this->find_last_not_of(__str.data(), __pos, __str.size()); }
4711
4712	/**
4713	* @brief Find last position of a character not in C substring.
4714	* @param __s C string containing characters to avoid.
4715	* @param __pos Index of character to search back from.
4716	* @param __n Number of characters from s to consider.
4717	* @return Index of last occurrence.
4718	*
4719	* Starting from @a __pos, searches backward for a character not
4720	* contained in the first @a __n characters of @a __s within this string.
4721	* If found, returns the index where it was found. If not found,
4722	* returns npos.
4723	*/
4724	size_type
4725	find_last_not_of(const _CharT* __s, size_type __pos,
4726	size_type __n) const;
4727	/**
4728	* @brief Find last position of a character not in C string.
4729	* @param __s C string containing characters to avoid.
4730	* @param __pos Index of character to search back from (default end).
4731	* @return Index of last occurrence.
4732	*
4733	* Starting from @a __pos, searches backward for a character
4734	* not contained in @a __s within this string. If found,
4735	* returns the index where it was found. If not found, returns
4736	* npos.
4737	*/
4738	size_type
4739	find_last_not_of(const _CharT* __s, size_type __pos = npos) const
4740	{
4741	__glibcxx_requires_string(__s);
4742	return this->find_last_not_of(__s, __pos, traits_type::length(__s));
4743	}
4744
4745	/**
4746	* @brief Find last position of a different character.
4747	* @param __c Character to avoid.
4748	* @param __pos Index of character to search back from (default end).
4749	* @return Index of last occurrence.
4750	*
4751	* Starting from @a __pos, searches backward for a character other than
4752	* @a __c within this string. If found, returns the index where it was
4753	* found. If not found, returns npos.
4754	*/
4755	size_type
4756	find_last_not_of(_CharT __c, size_type __pos = npos) const
4757	_GLIBCXX_NOEXCEPT;
4758
4759	/**
4760	* @brief Get a substring.
4761	* @param __pos Index of first character (default 0).
4762	* @param __n Number of characters in substring (default remainder).
4763	* @return The new string.
4764	* @throw std::out_of_range If __pos > size().
4765	*
4766	* Construct and return a new string using the @a __n
4767	* characters starting at @a __pos. If the string is too
4768	* short, use the remainder of the characters. If @a __pos is
4769	* beyond the end of the string, out_of_range is thrown.
4770	*/
4771	basic_string
4772	substr(size_type __pos = `0`, size_type __n = npos) const
4773	{ return basic_string(*this,
4774	_M_check(__pos, "basic_string::substr"), __n); }
4775
4776	/**
4777	* @brief Compare to a string.
4778	* @param __str String to compare against.
4779	* @return Integer < 0, 0, or > 0.
4780	*
4781	* Returns an integer < 0 if this string is ordered before @a
4782	* __str, 0 if their values are equivalent, or > 0 if this
4783	* string is ordered after @a __str. Determines the effective
4784	* length rlen of the strings to compare as the smallest of
4785	* size() and str.size(). The function then compares the two
4786	* strings by calling traits::compare(data(), str.data(),rlen).
4787	* If the result of the comparison is nonzero returns it,
4788	* otherwise the shorter one is ordered first.
4789	*/
4790	int
4791	compare(const basic_string& __str) const
4792	{
4793	const size_type __size = this->size();
4794	const size_type __osize = __str.size();
4795	const size_type __len = std::min(__size, __osize);
4796
4797	int __r = traits_type::compare(_M_data(), __str.data(), __len);
4798	if (!__r)
4799	__r = _S_compare(__size, __osize);
4800	return __r;
4801	}
4802
4803	/**
4804	* @brief Compare substring to a string.
4805	* @param __pos Index of first character of substring.
4806	* @param __n Number of characters in substring.
4807	* @param __str String to compare against.
4808	* @return Integer < 0, 0, or > 0.
4809	*
4810	* Form the substring of this string from the @a __n characters
4811	* starting at @a __pos. Returns an integer < 0 if the
4812	* substring is ordered before @a __str, 0 if their values are
4813	* equivalent, or > 0 if the substring is ordered after @a
4814	* __str. Determines the effective length rlen of the strings
4815	* to compare as the smallest of the length of the substring
4816	* and @a __str.size(). The function then compares the two
4817	* strings by calling
4818	* traits::compare(substring.data(),str.data(),rlen). If the
4819	* result of the comparison is nonzero returns it, otherwise
4820	* the shorter one is ordered first.
4821	*/
4822	int
4823	compare(size_type __pos, size_type __n, const basic_string& __str) const;
4824
4825	/**
4826	* @brief Compare substring to a substring.
4827	* @param __pos1 Index of first character of substring.
4828	* @param __n1 Number of characters in substring.
4829	* @param __str String to compare against.
4830	* @param __pos2 Index of first character of substring of str.
4831	* @param __n2 Number of characters in substring of str.
4832	* @return Integer < 0, 0, or > 0.
4833	*
4834	* Form the substring of this string from the @a __n1
4835	* characters starting at @a __pos1. Form the substring of @a
4836	* __str from the @a __n2 characters starting at @a __pos2.
4837	* Returns an integer < 0 if this substring is ordered before
4838	* the substring of @a __str, 0 if their values are equivalent,
4839	* or > 0 if this substring is ordered after the substring of
4840	* @a __str. Determines the effective length rlen of the
4841	* strings to compare as the smallest of the lengths of the
4842	* substrings. The function then compares the two strings by
4843	* calling
4844	* traits::compare(substring.data(),str.substr(pos2,n2).data(),rlen).
4845	* If the result of the comparison is nonzero returns it,
4846	* otherwise the shorter one is ordered first.
4847	*/
4848	int
4849	compare(size_type __pos1, size_type __n1, const basic_string& __str,
4850	size_type __pos2, size_type __n2) const;
4851
4852	/**
4853	* @brief Compare to a C string.
4854	* @param __s C string to compare against.
4855	* @return Integer < 0, 0, or > 0.
4856	*
4857	* Returns an integer < 0 if this string is ordered before @a __s, 0 if
4858	* their values are equivalent, or > 0 if this string is ordered after
4859	* @a __s. Determines the effective length rlen of the strings to
4860	* compare as the smallest of size() and the length of a string
4861	* constructed from @a __s. The function then compares the two strings
4862	* by calling traits::compare(data(),s,rlen). If the result of the
4863	* comparison is nonzero returns it, otherwise the shorter one is
4864	* ordered first.
4865	*/
4866	int
4867	compare(const _CharT* __s) const;
4868
4869	// _GLIBCXX_RESOLVE_LIB_DEFECTS
4870	// 5 String::compare specification questionable
4871	/**
4872	* @brief Compare substring to a C string.
4873	* @param __pos Index of first character of substring.
4874	* @param __n1 Number of characters in substring.
4875	* @param __s C string to compare against.
4876	* @return Integer < 0, 0, or > 0.
4877	*
4878	* Form the substring of this string from the @a __n1
4879	* characters starting at @a pos. Returns an integer < 0 if
4880	* the substring is ordered before @a __s, 0 if their values
4881	* are equivalent, or > 0 if the substring is ordered after @a
4882	* __s. Determines the effective length rlen of the strings to
4883	* compare as the smallest of the length of the substring and
4884	* the length of a string constructed from @a __s. The
4885	* function then compares the two string by calling
4886	* traits::compare(substring.data(),__s,rlen). If the result of
4887	* the comparison is nonzero returns it, otherwise the shorter
4888	* one is ordered first.
4889	*/
4890	int
4891	compare(size_type __pos, size_type __n1, const _CharT* __s) const;
4892
4893	/**
4894	* @brief Compare substring against a character %array.
4895	* @param __pos Index of first character of substring.
4896	* @param __n1 Number of characters in substring.
4897	* @param __s character %array to compare against.
4898	* @param __n2 Number of characters of s.
4899	* @return Integer < 0, 0, or > 0.
4900	*
4901	* Form the substring of this string from the @a __n1
4902	* characters starting at @a __pos. Form a string from the
4903	* first @a __n2 characters of @a __s. Returns an integer < 0
4904	* if this substring is ordered before the string from @a __s,
4905	* 0 if their values are equivalent, or > 0 if this substring
4906	* is ordered after the string from @a __s. Determines the
4907	* effective length rlen of the strings to compare as the
4908	* smallest of the length of the substring and @a __n2. The
4909	* function then compares the two strings by calling
4910	* traits::compare(substring.data(),s,rlen). If the result of
4911	* the comparison is nonzero returns it, otherwise the shorter
4912	* one is ordered first.
4913	*
4914	* NB: s must have at least n2 characters, '\\0' has
4915	* no special meaning.
4916	*/
4917	int
4918	compare(size_type __pos, size_type __n1, const _CharT* __s,
4919	size_type __n2) const;
4920
4921	# ifdef _GLIBCXX_TM_TS_INTERNAL
4922	friend void
4923	::_txnal_cow_string_C1_for_exceptions(void* that, const char* s,
4924	void* exc);
4925	friend const char*
4926	::_txnal_cow_string_c_str(const void *that);
4927	friend void
4928	::_txnal_cow_string_D1(void *that);
4929	friend void
4930	::_txnal_cow_string_D1_commit(void *that);
4931	# endif
4932	};
4933	#endif // !_GLIBCXX_USE_CXX11_ABI
4934
4935	// operator+
4936	/**
4937	* @brief Concatenate two strings.
4938	* @param __lhs First string.
4939	* @param __rhs Last string.
4940	* @return New string with value of @a __lhs followed by @a __rhs.
4941	*/
4942	template<typename _CharT, typename _Traits, typename _Alloc>
4943	basic_string<_CharT, _Traits, _Alloc>
4944	operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
4945	const basic_string<_CharT, _Traits, _Alloc>& __rhs)
4946	{
4947	basic_string<_CharT, _Traits, _Alloc> __str(__lhs);
4948	__str.append(__rhs);
4949	return __str;
4950	}
4951
4952	/**
4953	* @brief Concatenate C string and string.
4954	* @param __lhs First string.
4955	* @param __rhs Last string.
4956	* @return New string with value of @a __lhs followed by @a __rhs.
4957	*/
4958	template<typename _CharT, typename _Traits, typename _Alloc>
4959	basic_string<_CharT,_Traits,_Alloc>
4960	operator+(const _CharT* __lhs,
4961	const basic_string<_CharT,_Traits,_Alloc>& __rhs);
4962
4963	/**
4964	* @brief Concatenate character and string.
4965	* @param __lhs First string.
4966	* @param __rhs Last string.
4967	* @return New string with @a __lhs followed by @a __rhs.
4968	*/
4969	template<typename _CharT, typename _Traits, typename _Alloc>
4970	basic_string<_CharT,_Traits,_Alloc>
4971	operator+(_CharT __lhs, const basic_string<_CharT,_Traits,_Alloc>& __rhs);
4972
4973	/**
4974	* @brief Concatenate string and C string.
4975	* @param __lhs First string.
4976	* @param __rhs Last string.
4977	* @return New string with @a __lhs followed by @a __rhs.
4978	*/
4979	template<typename _CharT, typename _Traits, typename _Alloc>
4980	inline basic_string<_CharT, _Traits, _Alloc>
4981	operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
4982	const _CharT* __rhs)
4983	{
4984	basic_string<_CharT, _Traits, _Alloc> __str(__lhs);
4985	__str.append(__rhs);
4986	return __str;
4987	}
4988
4989	/**
4990	* @brief Concatenate string and character.
4991	* @param __lhs First string.
4992	* @param __rhs Last string.
4993	* @return New string with @a __lhs followed by @a __rhs.
4994	*/
4995	template<typename _CharT, typename _Traits, typename _Alloc>
4996	inline basic_string<_CharT, _Traits, _Alloc>
4997	operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs, _CharT __rhs)
4998	{
4999	typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
5000	typedef typename __string_type::size_type __size_type;
5001	__string_type __str(__lhs);
5002	__str.append(__size_type(`1`), __rhs);
5003	return __str;
5004	}
5005
5006	#if __cplusplus >= 201103L
5007	template<typename _CharT, typename _Traits, typename _Alloc>
5008	inline basic_string<_CharT, _Traits, _Alloc>
5009	operator+(basic_string<_CharT, _Traits, _Alloc>&& __lhs,
5010	const basic_string<_CharT, _Traits, _Alloc>& __rhs)
5011	{ return std::move(__lhs.append(__rhs)); }
5012
5013	template<typename _CharT, typename _Traits, typename _Alloc>
5014	inline basic_string<_CharT, _Traits, _Alloc>
5015	operator+(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
5016	basic_string<_CharT, _Traits, _Alloc>&& __rhs)
5017	{ return std::move(__rhs.insert(`0`, __lhs)); }
5018
5019	template<typename _CharT, typename _Traits, typename _Alloc>
5020	inline basic_string<_CharT, _Traits, _Alloc>
5021	operator+(basic_string<_CharT, _Traits, _Alloc>&& __lhs,
5022	basic_string<_CharT, _Traits, _Alloc>&& __rhs)
5023	{
5024	const auto __size = __lhs.size() + __rhs.size();
5025	const bool __cond = (__size > __lhs.capacity()
5026	&& __size <= __rhs.capacity());
5027	return __cond ? std::move(__rhs.insert(`0`, __lhs))
5028	: std::move(__lhs.append(__rhs));
5029	}
5030
5031	template<typename _CharT, typename _Traits, typename _Alloc>
5032	inline basic_string<_CharT, _Traits, _Alloc>
5033	operator+(const _CharT* __lhs,
5034	basic_string<_CharT, _Traits, _Alloc>&& __rhs)
5035	{ return std::move(__rhs.insert(`0`, __lhs)); }
5036
5037	template<typename _CharT, typename _Traits, typename _Alloc>
5038	inline basic_string<_CharT, _Traits, _Alloc>
5039	operator+(_CharT __lhs,
5040	basic_string<_CharT, _Traits, _Alloc>&& __rhs)
5041	{ return std::move(__rhs.insert(`0`, `1`, __lhs)); }
5042
5043	template<typename _CharT, typename _Traits, typename _Alloc>
5044	inline basic_string<_CharT, _Traits, _Alloc>
5045	operator+(basic_string<_CharT, _Traits, _Alloc>&& __lhs,
5046	const _CharT* __rhs)
5047	{ return std::move(__lhs.append(__rhs)); }
5048
5049	template<typename _CharT, typename _Traits, typename _Alloc>
5050	inline basic_string<_CharT, _Traits, _Alloc>
5051	operator+(basic_string<_CharT, _Traits, _Alloc>&& __lhs,
5052	_CharT __rhs)
5053	{ return std::move(__lhs.append(`1`, __rhs)); }
5054	#endif
5055
5056	// operator ==
5057	/**
5058	* @brief Test equivalence of two strings.
5059	* @param __lhs First string.
5060	* @param __rhs Second string.
5061	* @return True if @a __lhs.compare(@a __rhs) == 0. False otherwise.
5062	*/
5063	template<typename _CharT, typename _Traits, typename _Alloc>
5064	inline bool
5065	operator==(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
5066	const basic_string<_CharT, _Traits, _Alloc>& __rhs)
5067	_GLIBCXX_NOEXCEPT
5068	{ return __lhs.compare(__rhs) == `0`; }
5069
5070	template<typename _CharT>
5071	inline
5072	typename __gnu_cxx::__enable_if<__is_char<_CharT>::__value, bool>::__type
5073	operator==(const basic_string<_CharT>& __lhs,
5074	const basic_string<_CharT>& __rhs) _GLIBCXX_NOEXCEPT
5075	{ return (__lhs.size() == __rhs.size()
5076	&& !std::char_traits<_CharT>::compare(__lhs.data(), __rhs.data(),
5077	__lhs.size())); }
5078
5079	/**
5080	* @brief Test equivalence of C string and string.
5081	* @param __lhs C string.
5082	* @param __rhs String.
5083	* @return True if @a __rhs.compare(@a __lhs) == 0. False otherwise.
5084	*/
5085	template<typename _CharT, typename _Traits, typename _Alloc>
5086	inline bool
5087	operator==(const _CharT* __lhs,
5088	const basic_string<_CharT, _Traits, _Alloc>& __rhs)
5089	{ return __rhs.compare(__lhs) == `0`; }
5090
5091	/**
5092	* @brief Test equivalence of string and C string.
5093	* @param __lhs String.
5094	* @param __rhs C string.
5095	* @return True if @a __lhs.compare(@a __rhs) == 0. False otherwise.
5096	*/
5097	template<typename _CharT, typename _Traits, typename _Alloc>
5098	inline bool
5099	operator==(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
5100	const _CharT* __rhs)
5101	{ return __lhs.compare(__rhs) == `0`; }
5102
5103	// operator !=
5104	/**
5105	* @brief Test difference of two strings.
5106	* @param __lhs First string.
5107	* @param __rhs Second string.
5108	* @return True if @a __lhs.compare(@a __rhs) != 0. False otherwise.
5109	*/
5110	template<typename _CharT, typename _Traits, typename _Alloc>
5111	inline bool
5112	operator!=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
5113	const basic_string<_CharT, _Traits, _Alloc>& __rhs)
5114	_GLIBCXX_NOEXCEPT
5115	{ return !(__lhs == __rhs); }
5116
5117	/**
5118	* @brief Test difference of C string and string.
5119	* @param __lhs C string.
5120	* @param __rhs String.
5121	* @return True if @a __rhs.compare(@a __lhs) != 0. False otherwise.
5122	*/
5123	template<typename _CharT, typename _Traits, typename _Alloc>
5124	inline bool
5125	operator!=(const _CharT* __lhs,
5126	const basic_string<_CharT, _Traits, _Alloc>& __rhs)
5127	{ return !(__lhs == __rhs); }
5128
5129	/**
5130	* @brief Test difference of string and C string.
5131	* @param __lhs String.
5132	* @param __rhs C string.
5133	* @return True if @a __lhs.compare(@a __rhs) != 0. False otherwise.
5134	*/
5135	template<typename _CharT, typename _Traits, typename _Alloc>
5136	inline bool
5137	operator!=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
5138	const _CharT* __rhs)
5139	{ return !(__lhs == __rhs); }
5140
5141	// operator <
5142	/**
5143	* @brief Test if string precedes string.
5144	* @param __lhs First string.
5145	* @param __rhs Second string.
5146	* @return True if @a __lhs precedes @a __rhs. False otherwise.
5147	*/
5148	template<typename _CharT, typename _Traits, typename _Alloc>
5149	inline bool
5150	operator<(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
5151	const basic_string<_CharT, _Traits, _Alloc>& __rhs)
5152	_GLIBCXX_NOEXCEPT
5153	{ return __lhs.compare(__rhs) < `0`; }
5154
5155	/**
5156	* @brief Test if string precedes C string.
5157	* @param __lhs String.
5158	* @param __rhs C string.
5159	* @return True if @a __lhs precedes @a __rhs. False otherwise.
5160	*/
5161	template<typename _CharT, typename _Traits, typename _Alloc>
5162	inline bool
5163	operator<(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
5164	const _CharT* __rhs)
5165	{ return __lhs.compare(__rhs) < `0`; }
5166
5167	/**
5168	* @brief Test if C string precedes string.
5169	* @param __lhs C string.
5170	* @param __rhs String.
5171	* @return True if @a __lhs precedes @a __rhs. False otherwise.
5172	*/
5173	template<typename _CharT, typename _Traits, typename _Alloc>
5174	inline bool
5175	operator<(const _CharT* __lhs,
5176	const basic_string<_CharT, _Traits, _Alloc>& __rhs)
5177	{ return __rhs.compare(__lhs) > `0`; }
5178
5179	// operator >
5180	/**
5181	* @brief Test if string follows string.
5182	* @param __lhs First string.
5183	* @param __rhs Second string.
5184	* @return True if @a __lhs follows @a __rhs. False otherwise.
5185	*/
5186	template<typename _CharT, typename _Traits, typename _Alloc>
5187	inline bool
5188	operator>(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
5189	const basic_string<_CharT, _Traits, _Alloc>& __rhs)
5190	_GLIBCXX_NOEXCEPT
5191	{ return __lhs.compare(__rhs) > `0`; }
5192
5193	/**
5194	* @brief Test if string follows C string.
5195	* @param __lhs String.
5196	* @param __rhs C string.
5197	* @return True if @a __lhs follows @a __rhs. False otherwise.
5198	*/
5199	template<typename _CharT, typename _Traits, typename _Alloc>
5200	inline bool
5201	operator>(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
5202	const _CharT* __rhs)
5203	{ return __lhs.compare(__rhs) > `0`; }
5204
5205	/**
5206	* @brief Test if C string follows string.
5207	* @param __lhs C string.
5208	* @param __rhs String.
5209	* @return True if @a __lhs follows @a __rhs. False otherwise.
5210	*/
5211	template<typename _CharT, typename _Traits, typename _Alloc>
5212	inline bool
5213	operator>(const _CharT* __lhs,
5214	const basic_string<_CharT, _Traits, _Alloc>& __rhs)
5215	{ return __rhs.compare(__lhs) < `0`; }
5216
5217	// operator <=
5218	/**
5219	* @brief Test if string doesn't follow string.
5220	* @param __lhs First string.
5221	* @param __rhs Second string.
5222	* @return True if @a __lhs doesn't follow @a __rhs. False otherwise.
5223	*/
5224	template<typename _CharT, typename _Traits, typename _Alloc>
5225	inline bool
5226	operator<=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
5227	const basic_string<_CharT, _Traits, _Alloc>& __rhs)
5228	_GLIBCXX_NOEXCEPT
5229	{ return __lhs.compare(__rhs) <= `0`; }
5230
5231	/**
5232	* @brief Test if string doesn't follow C string.
5233	* @param __lhs String.
5234	* @param __rhs C string.
5235	* @return True if @a __lhs doesn't follow @a __rhs. False otherwise.
5236	*/
5237	template<typename _CharT, typename _Traits, typename _Alloc>
5238	inline bool
5239	operator<=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
5240	const _CharT* __rhs)
5241	{ return __lhs.compare(__rhs) <= `0`; }
5242
5243	/**
5244	* @brief Test if C string doesn't follow string.
5245	* @param __lhs C string.
5246	* @param __rhs String.
5247	* @return True if @a __lhs doesn't follow @a __rhs. False otherwise.
5248	*/
5249	template<typename _CharT, typename _Traits, typename _Alloc>
5250	inline bool
5251	operator<=(const _CharT* __lhs,
5252	const basic_string<_CharT, _Traits, _Alloc>& __rhs)
5253	{ return __rhs.compare(__lhs) >= `0`; }
5254
5255	// operator >=
5256	/**
5257	* @brief Test if string doesn't precede string.
5258	* @param __lhs First string.
5259	* @param __rhs Second string.
5260	* @return True if @a __lhs doesn't precede @a __rhs. False otherwise.
5261	*/
5262	template<typename _CharT, typename _Traits, typename _Alloc>
5263	inline bool
5264	operator>=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
5265	const basic_string<_CharT, _Traits, _Alloc>& __rhs)
5266	_GLIBCXX_NOEXCEPT
5267	{ return __lhs.compare(__rhs) >= `0`; }
5268
5269	/**
5270	* @brief Test if string doesn't precede C string.
5271	* @param __lhs String.
5272	* @param __rhs C string.
5273	* @return True if @a __lhs doesn't precede @a __rhs. False otherwise.
5274	*/
5275	template<typename _CharT, typename _Traits, typename _Alloc>
5276	inline bool
5277	operator>=(const basic_string<_CharT, _Traits, _Alloc>& __lhs,
5278	const _CharT* __rhs)
5279	{ return __lhs.compare(__rhs) >= `0`; }
5280
5281	/**
5282	* @brief Test if C string doesn't precede string.
5283	* @param __lhs C string.
5284	* @param __rhs String.
5285	* @return True if @a __lhs doesn't precede @a __rhs. False otherwise.
5286	*/
5287	template<typename _CharT, typename _Traits, typename _Alloc>
5288	inline bool
5289	operator>=(const _CharT* __lhs,
5290	const basic_string<_CharT, _Traits, _Alloc>& __rhs)
5291	{ return __rhs.compare(__lhs) <= `0`; }
5292
5293	/**
5294	* @brief Swap contents of two strings.
5295	* @param __lhs First string.
5296	* @param __rhs Second string.
5297	*
5298	* Exchanges the contents of @a __lhs and @a __rhs in constant time.
5299	*/
5300	template<typename _CharT, typename _Traits, typename _Alloc>
5301	inline void
5302	swap(basic_string<_CharT, _Traits, _Alloc>& __lhs,
5303	basic_string<_CharT, _Traits, _Alloc>& __rhs)
5304	_GLIBCXX_NOEXCEPT_IF(noexcept(__lhs.swap(__rhs)))
5305	{ __lhs.swap(__rhs); }
5306
5307
5308	/**
5309	* @brief Read stream into a string.
5310	* @param __is Input stream.
5311	* @param __str Buffer to store into.
5312	* @return Reference to the input stream.
5313	*
5314	* Stores characters from @a __is into @a __str until whitespace is
5315	* found, the end of the stream is encountered, or str.max_size()
5316	* is reached. If is.width() is non-zero, that is the limit on the
5317	* number of characters stored into @a __str. Any previous
5318	* contents of @a __str are erased.
5319	*/
5320	template<typename _CharT, typename _Traits, typename _Alloc>
5321	basic_istream<_CharT, _Traits>&
5322	operator>>(basic_istream<_CharT, _Traits>& __is,
5323	basic_string<_CharT, _Traits, _Alloc>& __str);
5324
5325	template<>
5326	basic_istream<char>&
5327	operator>>(basic_istream<char>& __is, basic_string<char>& __str);
5328
5329	/**
5330	* @brief Write string to a stream.
5331	* @param __os Output stream.
5332	* @param __str String to write out.
5333	* @return Reference to the output stream.
5334	*
5335	* Output characters of @a __str into os following the same rules as for
5336	* writing a C string.
5337	*/
5338	template<typename _CharT, typename _Traits, typename _Alloc>
5339	inline basic_ostream<_CharT, _Traits>&
5340	operator<<(basic_ostream<_CharT, _Traits>& __os,
5341	const basic_string<_CharT, _Traits, _Alloc>& __str)
5342	{
5343	// _GLIBCXX_RESOLVE_LIB_DEFECTS
5344	// 586. string inserter not a formatted function
5345	return __ostream_insert(__os, __str.data(), __str.size());
5346	}
5347
5348	/**
5349	* @brief Read a line from stream into a string.
5350	* @param __is Input stream.
5351	* @param __str Buffer to store into.
5352	* @param __delim Character marking end of line.
5353	* @return Reference to the input stream.
5354	*
5355	* Stores characters from @a __is into @a __str until @a __delim is
5356	* found, the end of the stream is encountered, or str.max_size()
5357	* is reached. Any previous contents of @a __str are erased. If
5358	* @a __delim is encountered, it is extracted but not stored into
5359	* @a __str.
5360	*/
5361	template<typename _CharT, typename _Traits, typename _Alloc>
5362	basic_istream<_CharT, _Traits>&
5363	getline(basic_istream<_CharT, _Traits>& __is,
5364	basic_string<_CharT, _Traits, _Alloc>& __str, _CharT __delim);
5365
5366	/**
5367	* @brief Read a line from stream into a string.
5368	* @param __is Input stream.
5369	* @param __str Buffer to store into.
5370	* @return Reference to the input stream.
5371	*
5372	* Stores characters from is into @a __str until '\n' is
5373	* found, the end of the stream is encountered, or str.max_size()
5374	* is reached. Any previous contents of @a __str are erased. If
5375	* end of line is encountered, it is extracted but not stored into
5376	* @a __str.
5377	*/
5378	template<typename _CharT, typename _Traits, typename _Alloc>
5379	inline basic_istream<_CharT, _Traits>&
5380	getline(basic_istream<_CharT, _Traits>& __is,
5381	basic_string<_CharT, _Traits, _Alloc>& __str)
5382	{ return std::getline(__is, __str, __is.widen(`'\n'`)); }
5383
5384	#if __cplusplus >= 201103L
5385	/// Read a line from an rvalue stream into a string.
5386	template<typename _CharT, typename _Traits, typename _Alloc>
5387	inline basic_istream<_CharT, _Traits>&
5388	getline(basic_istream<_CharT, _Traits>&& __is,
5389	basic_string<_CharT, _Traits, _Alloc>& __str, _CharT __delim)
5390	{ return std::getline(__is, __str, __delim); }
5391
5392	/// Read a line from an rvalue stream into a string.
5393	template<typename _CharT, typename _Traits, typename _Alloc>
5394	inline basic_istream<_CharT, _Traits>&
5395	getline(basic_istream<_CharT, _Traits>&& __is,
5396	basic_string<_CharT, _Traits, _Alloc>& __str)
5397	{ return std::getline(__is, __str); }
5398	#endif
5399
5400	template<>
5401	basic_istream<char>&
5402	getline(basic_istream<char>& __in, basic_string<char>& __str,
5403	char __delim);
5404
5405	#ifdef _GLIBCXX_USE_WCHAR_T
5406	template<>
5407	basic_istream<wchar_t>&
5408	getline(basic_istream<wchar_t>& __in, basic_string<wchar_t>& __str,
5409	wchar_t __delim);
5410	#endif
5411
5412	_GLIBCXX_END_NAMESPACE_VERSION
5413	} // namespace
5414
5415	#if __cplusplus >= 201103L
5416
5417	#include <ext/string_conversions.h>
5418
5419	namespace std _GLIBCXX_VISIBILITY(default)
5420	{
5421	_GLIBCXX_BEGIN_NAMESPACE_VERSION
5422	_GLIBCXX_BEGIN_NAMESPACE_CXX11
5423
5424	#if _GLIBCXX_USE_C99_STDLIB
5425	// 21.4 Numeric Conversions [string.conversions].
5426	inline int
5427	stoi(const string& __str, size_t* __idx = `0`, int __base = `10`)
5428	{ return __gnu_cxx::__stoa<long, int>(&std::strtol, "stoi", __str.c_str(),
5429	__idx, __base); }
5430
5431	inline long
5432	stol(const string& __str, size_t* __idx = `0`, int __base = `10`)
5433	{ return __gnu_cxx::__stoa(&std::strtol, "stol", __str.c_str(),
5434	__idx, __base); }
5435
5436	inline unsigned long
5437	stoul(const string& __str, size_t* __idx = `0`, int __base = `10`)
5438	{ return __gnu_cxx::__stoa(&std::strtoul, "stoul", __str.c_str(),
5439	__idx, __base); }
5440
5441	inline long long
5442	stoll(const string& __str, size_t* __idx = `0`, int __base = `10`)
5443	{ return __gnu_cxx::__stoa(&std::strtoll, "stoll", __str.c_str(),
5444	__idx, __base); }
5445
5446	inline unsigned long long
5447	stoull(const string& __str, size_t* __idx = `0`, int __base = `10`)
5448	{ return __gnu_cxx::__stoa(&std::strtoull, "stoull", __str.c_str(),
5449	__idx, __base); }
5450
5451	// NB: strtof vs strtod.
5452	inline float
5453	stof(const string& __str, size_t* __idx = `0`)
5454	{ return __gnu_cxx::__stoa(&std::strtof, "stof", __str.c_str(), __idx); }
5455
5456	inline double
5457	stod(const string& __str, size_t* __idx = `0`)
5458	{ return __gnu_cxx::__stoa(&std::strtod, "stod", __str.c_str(), __idx); }
5459
5460	inline long double
5461	stold(const string& __str, size_t* __idx = `0`)
5462	{ return __gnu_cxx::__stoa(&std::strtold, "stold", __str.c_str(), __idx); }
5463	#endif // _GLIBCXX_USE_C99_STDLIB
5464
5465	#if _GLIBCXX_USE_C99_STDIO
5466	// NB: (v)snprintf vs sprintf.
5467
5468	// DR 1261.
5469	inline string
5470	to_string(int __val)
5471	{ return __gnu_cxx::__to_xstring<string>(&std::vsnprintf, `4` * sizeof(int),
5472	"%d", __val); }
5473
5474	inline string
5475	to_string(unsigned __val)
5476	{ return __gnu_cxx::__to_xstring<string>(&std::vsnprintf,
5477	`4` * sizeof(unsigned),
5478	"%u", __val); }
5479
5480	inline string
5481	to_string(long __val)
5482	{ return __gnu_cxx::__to_xstring<string>(&std::vsnprintf, `4` * sizeof(long),
5483	"%ld", __val); }
5484
5485	inline string
5486	to_string(unsigned long __val)
5487	{ return __gnu_cxx::__to_xstring<string>(&std::vsnprintf,
5488	`4` * sizeof(unsigned long),
5489	"%lu", __val); }
5490
5491	inline string
5492	to_string(long long __val)
5493	{ return __gnu_cxx::__to_xstring<string>(&std::vsnprintf,
5494	`4` * sizeof(long long),
5495	"%lld", __val); }
5496
5497	inline string
5498	to_string(unsigned long long __val)
5499	{ return __gnu_cxx::__to_xstring<string>(&std::vsnprintf,
5500	`4` * sizeof(unsigned long long),
5501	"%llu", __val); }
5502
5503	inline string
5504	to_string(float __val)
5505	{
5506	const int __n =
5507	__gnu_cxx::__numeric_traits<float>::__max_exponent10 + `20`;
5508	return __gnu_cxx::__to_xstring<string>(&std::vsnprintf, __n,
5509	"%f", __val);
5510	}
5511
5512	inline string
5513	to_string(double __val)
5514	{
5515	const int __n =
5516	__gnu_cxx::__numeric_traits<double>::__max_exponent10 + `20`;
5517	return __gnu_cxx::__to_xstring<string>(&std::vsnprintf, __n,
5518	"%f", __val);
5519	}
5520
5521	inline string
5522	to_string(long double __val)
5523	{
5524	const int __n =
5525	__gnu_cxx::__numeric_traits<long double>::__max_exponent10 + `20`;
5526	return __gnu_cxx::__to_xstring<string>(&std::vsnprintf, __n,
5527	"%Lf", __val);
5528	}
5529	#endif // _GLIBCXX_USE_C99_STDIO
5530
5531	#if defined(_GLIBCXX_USE_WCHAR_T) && _GLIBCXX_USE_C99_WCHAR
5532	inline int
5533	stoi(const wstring& __str, size_t* __idx = `0`, int __base = `10`)
5534	{ return __gnu_cxx::__stoa<long, int>(&std::wcstol, "stoi", __str.c_str(),
5535	__idx, __base); }
5536
5537	inline long
5538	stol(const wstring& __str, size_t* __idx = `0`, int __base = `10`)
5539	{ return __gnu_cxx::__stoa(&std::wcstol, "stol", __str.c_str(),
5540	__idx, __base); }
5541
5542	inline unsigned long
5543	stoul(const wstring& __str, size_t* __idx = `0`, int __base = `10`)
5544	{ return __gnu_cxx::__stoa(&std::wcstoul, "stoul", __str.c_str(),
5545	__idx, __base); }
5546
5547	inline long long
5548	stoll(const wstring& __str, size_t* __idx = `0`, int __base = `10`)
5549	{ return __gnu_cxx::__stoa(&std::wcstoll, "stoll", __str.c_str(),
5550	__idx, __base); }
5551
5552	inline unsigned long long
5553	stoull(const wstring& __str, size_t* __idx = `0`, int __base = `10`)
5554	{ return __gnu_cxx::__stoa(&std::wcstoull, "stoull", __str.c_str(),
5555	__idx, __base); }
5556
5557	// NB: wcstof vs wcstod.
5558	inline float
5559	stof(const wstring& __str, size_t* __idx = `0`)
5560	{ return __gnu_cxx::__stoa(&std::wcstof, "stof", __str.c_str(), __idx); }
5561
5562	inline double
5563	stod(const wstring& __str, size_t* __idx = `0`)
5564	{ return __gnu_cxx::__stoa(&std::wcstod, "stod", __str.c_str(), __idx); }
5565
5566	inline long double
5567	stold(const wstring& __str, size_t* __idx = `0`)
5568	{ return __gnu_cxx::__stoa(&std::wcstold, "stold", __str.c_str(), __idx); }
5569
5570	#ifndef _GLIBCXX_HAVE_BROKEN_VSWPRINTF
5571	// DR 1261.
5572	inline wstring
5573	to_wstring(int __val)
5574	{ return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf, `4` * sizeof(int),
5575	L"%d", __val); }
5576
5577	inline wstring
5578	to_wstring(unsigned __val)
5579	{ return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf,
5580	`4` * sizeof(unsigned),
5581	L"%u", __val); }
5582
5583	inline wstring
5584	to_wstring(long __val)
5585	{ return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf, `4` * sizeof(long),
5586	L"%ld", __val); }
5587
5588	inline wstring
5589	to_wstring(unsigned long __val)
5590	{ return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf,
5591	`4` * sizeof(unsigned long),
5592	L"%lu", __val); }
5593
5594	inline wstring
5595	to_wstring(long long __val)
5596	{ return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf,
5597	`4` * sizeof(long long),
5598	L"%lld", __val); }
5599
5600	inline wstring
5601	to_wstring(unsigned long long __val)
5602	{ return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf,
5603	`4` * sizeof(unsigned long long),
5604	L"%llu", __val); }
5605
5606	inline wstring
5607	to_wstring(float __val)
5608	{
5609	const int __n =
5610	__gnu_cxx::__numeric_traits<float>::__max_exponent10 + `20`;
5611	return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf, __n,
5612	L"%f", __val);
5613	}
5614
5615	inline wstring
5616	to_wstring(double __val)
5617	{
5618	const int __n =
5619	__gnu_cxx::__numeric_traits<double>::__max_exponent10 + `20`;
5620	return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf, __n,
5621	L"%f", __val);
5622	}
5623
5624	inline wstring
5625	to_wstring(long double __val)
5626	{
5627	const int __n =
5628	__gnu_cxx::__numeric_traits<long double>::__max_exponent10 + `20`;
5629	return __gnu_cxx::__to_xstring<wstring>(&std::vswprintf, __n,
5630	L"%Lf", __val);
5631	}
5632	#endif // _GLIBCXX_HAVE_BROKEN_VSWPRINTF
5633	#endif // _GLIBCXX_USE_WCHAR_T && _GLIBCXX_USE_C99_WCHAR
5634
5635	_GLIBCXX_END_NAMESPACE_CXX11
5636	_GLIBCXX_END_NAMESPACE_VERSION
5637	} // namespace
5638
5639	#endif /* C++11 */
5640
5641	#if __cplusplus >= 201103L
5642
5643	#include <bits/functional_hash.h>
5644
5645	namespace std _GLIBCXX_VISIBILITY(default)
5646	{
5647	_GLIBCXX_BEGIN_NAMESPACE_VERSION
5648
5649	// DR 1182.
5650
5651	#ifndef _GLIBCXX_COMPATIBILITY_CXX0X
5652	/// std::hash specialization for string.
5653	template<>
5654	struct hash<string>
5655	: public __hash_base<size_t, string>
5656	{
5657	size_t
5658	operator()(const string& __s) const noexcept
5659	{ return std::_Hash_impl::hash(__s.data(), __s.length()); }
5660	};
5661
5662	template<>
5663	struct __is_fast_hash<hash<string>> : std::false_type
5664	{ };
5665
5666	#ifdef _GLIBCXX_USE_WCHAR_T
5667	/// std::hash specialization for wstring.
5668	template<>
5669	struct hash<wstring>
5670	: public __hash_base<size_t, wstring>
5671	{
5672	size_t
5673	operator()(const wstring& __s) const noexcept
5674	{ return std::_Hash_impl::hash(__s.data(),
5675	__s.length() * sizeof(wchar_t)); }
5676	};
5677
5678	template<>
5679	struct __is_fast_hash<hash<wstring>> : std::false_type
5680	{ };
5681	#endif
5682	#endif /* _GLIBCXX_COMPATIBILITY_CXX0X */
5683
5684	#ifdef _GLIBCXX_USE_C99_STDINT_TR1
5685	/// std::hash specialization for u16string.
5686	template<>
5687	struct hash<u16string>
5688	: public __hash_base<size_t, u16string>
5689	{
5690	size_t
5691	operator()(const u16string& __s) const noexcept
5692	{ return std::_Hash_impl::hash(__s.data(),
5693	__s.length() * sizeof(char16_t)); }
5694	};
5695
5696	template<>
5697	struct __is_fast_hash<hash<u16string>> : std::false_type
5698	{ };
5699
5700	/// std::hash specialization for u32string.
5701	template<>
5702	struct hash<u32string>
5703	: public __hash_base<size_t, u32string>
5704	{
5705	size_t
5706	operator()(const u32string& __s) const noexcept
5707	{ return std::_Hash_impl::hash(__s.data(),
5708	__s.length() * sizeof(char32_t)); }
5709	};
5710
5711	template<>
5712	struct __is_fast_hash<hash<u32string>> : std::false_type
5713	{ };
5714	#endif
5715
5716	_GLIBCXX_END_NAMESPACE_VERSION
5717
5718	#if __cplusplus > 201103L
5719
5720	#define __cpp_lib_string_udls 201304
5721
5722	inline namespace literals
5723	{
5724	inline namespace string_literals
5725	{
5726	_GLIBCXX_BEGIN_NAMESPACE_VERSION
5727
5728	_GLIBCXX_DEFAULT_ABI_TAG
5729	inline basic_string<char>
5730	operator""s(const char* __str, size_t __len)
5731	{ return basic_string<char>{__str, __len}; }
5732
5733	#ifdef _GLIBCXX_USE_WCHAR_T
5734	_GLIBCXX_DEFAULT_ABI_TAG
5735	inline basic_string<wchar_t>
5736	operator""s(const wchar_t* __str, size_t __len)
5737	{ return basic_string<wchar_t>{__str, __len}; }
5738	#endif
5739
5740	#ifdef _GLIBCXX_USE_C99_STDINT_TR1
5741	_GLIBCXX_DEFAULT_ABI_TAG
5742	inline basic_string<char16_t>
5743	operator""s(const char16_t* __str, size_t __len)
5744	{ return basic_string<char16_t>{__str, __len}; }
5745
5746	_GLIBCXX_DEFAULT_ABI_TAG
5747	inline basic_string<char32_t>
5748	operator""s(const char32_t* __str, size_t __len)
5749	{ return basic_string<char32_t>{__str, __len}; }
5750	#endif
5751
5752	_GLIBCXX_END_NAMESPACE_VERSION
5753	} // inline namespace string_literals
5754	} // inline namespace literals
5755
5756	#endif // __cplusplus > 201103L
5757
5758	} // namespace std
5759
5760	#endif // C++11
5761
5762	#endif /* _BASIC_STRING_H */
5763

Browse the source code of include/c++/6/bits/basic_string.h