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

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