/usr/include/boost/algorithm/string/detail/classification.hpp

Bug Summary

File:	usr/include/boost/algorithm/string/detail/classification.hpp
Warning:	line 137, column 25 Potential memory leak

Annotated Source Code

Press '?' to see keyboard shortcuts

Show analyzer invocation

clang -cc1 -cc1 -triple x86_64-redhat-linux-gnu -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name database_connection.cc -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -mrelocation-model pic -pic-level 2 -fhalf-no-semantic-interposition -mframe-pointer=all -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -fdebug-compilation-dir=/home/fedora/workspace/kea-dev/clang-static-analyzer/build/meson-private/tmpvcj5ffy2 -fcoverage-compilation-dir=/home/fedora/workspace/kea-dev/clang-static-analyzer/build/meson-private/tmpvcj5ffy2 -resource-dir /usr/bin/../lib/clang/20 -I src/lib/database/libkea-database.so.87.0.0.p -I src/lib/database -I ../../../src/lib/database -I . -I ../../.. -I src -I ../../../src -I src/bin -I ../../../src/bin -I src/lib -I ../../../src/lib -I /usr/include -D _GLIBCXX_ASSERTIONS=1 -D _FILE_OFFSET_BITS=64 -D BOOST_SYSTEM_DYN_LINK=1 -D BOOST_ALL_NO_LIB -internal-isystem /usr/bin/../lib/gcc/x86_64-redhat-linux/15/../../../../include/c++/15 -internal-isystem /usr/bin/../lib/gcc/x86_64-redhat-linux/15/../../../../include/c++/15/x86_64-redhat-linux -internal-isystem /usr/bin/../lib/gcc/x86_64-redhat-linux/15/../../../../include/c++/15/backward -internal-isystem /usr/bin/../lib/clang/20/include -internal-isystem /usr/local/include -internal-isystem /usr/bin/../lib/gcc/x86_64-redhat-linux/15/../../../../x86_64-redhat-linux/include -internal-externc-isystem /include -internal-externc-isystem /usr/include -O0 -Wwrite-strings -Wno-missing-field-initializers -fdeprecated-macro -ferror-limit 19 -fgnuc-version=4.2.1 -fskip-odr-check-in-gmf -fcxx-exceptions -fexceptions -fcolor-diagnostics -analyzer-output=html -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /home/fedora/workspace/kea-dev/clang-static-analyzer/build/meson-logs/scanbuild/2025-08-29-131339-9173-1 -x c++ ../../../src/lib/database/database_connection.cc

../../../src/lib/database/database_connection.cc

→

1// Copyright (C) 2015-2025 Internet Systems Consortium, Inc. ("ISC")
2//
3// This Source Code Form is subject to the terms of the Mozilla Public
4// License, v. 2.0. If a copy of the MPL was not distributed with this
5// file, You can obtain one at http://mozilla.org/MPL/2.0/.

7#include <config.h>

9#include <cc/cfg_to_element.h>
10#include <cc/default_credentials.h>
11#include <database/database_connection.h>
12#include <database/db_exceptions.h>
13#include <database/db_log.h>
14#include <database/db_messages.h>
15#include <exceptions/exceptions.h>
16#include <util/str.h>

18#include <boost/algorithm/string.hpp>
19#include <vector>

21using namespace isc::asiolink;
22using namespace isc::data;
23using namespace isc::util;
24using namespace std;

26namespace isc {
27namespace db {

29const time_t DatabaseConnection::MAX_DB_TIME = 2147483647;

31std::string
32DatabaseConnection::getParameter(const std::string& name) const {
  ParameterMap::const_iterator param = parameters_.find(name);
  if (param == parameters_.end()) {
      isc_throw(BadValue, "Parameter " << name << " not found")do { std::ostringstream oss__; oss__ << "Parameter " <<
 name << " not found"; throw BadValue("../../../src/lib/database/database_connection.cc"
, 35, oss__.str().c_str()); } while (1);
  }
  return (param->second);
38}

40DatabaseConnection::ParameterMap
41DatabaseConnection::parse(const std::string& dbaccess) {
  DatabaseConnection::ParameterMap mapped_tokens;
  std::string dba = dbaccess;

  if (!dba.empty()) {
2
←
Assuming the condition is true→
3
←
Taking true branch→
      try {
          vector<string> tokens;

          // Handle the special case of a password which is enclosed in apostrophes.
          // Such password may include whitespace.
          std::string password_prefix = "password='";
          auto password_pos = dba.find(password_prefix);
          if (password_pos != string::npos) {
4
←
Assuming 'password_pos' is equal to 'npos'→
5
←
Taking false branch→
              // Password starts with apostrophe, so let's find ending apostrophe.
              auto password_end_pos = dba.find('\'', password_pos + password_prefix.length());
              if (password_end_pos == string::npos) {
                  // No ending apostrophe. This is wrong.
                  isc_throw(InvalidParameter, "Apostrophe (') expected at the end of password")do { std::ostringstream oss__; oss__ << "Apostrophe (') expected at the end of password"
; throw InvalidParameter("../../../src/lib/database/database_connection.cc"
, 58, oss__.str().c_str()); } while (1);
              }
              // Extract the password value. It starts after the password=' prefix and ends
              // at the position of ending apostrophe.
              auto password = dba.substr(password_pos + password_prefix.length(),
                                         password_end_pos - password_pos - password_prefix.length());
              // Refuse default passwords.
              DefaultCredentials::check(password);
              mapped_tokens.insert(make_pair("password", password));

              // We need to erase the password from the access string because the generic
              // algorithm parsing other parameters requires that there are no whitespaces
              // within the parameter values.
              dba.erase(password_pos, password_prefix.length() + password.length() + 2);
              // Leading or trailing whitespace may remain after the password removal.
              dba = util::str::trim(dba);
              // If the password was the only parameter in the access string, there is
              // nothing more to do.
              if (dba.empty()) {
                  return (mapped_tokens);
              }
          }

          // We need to pass a string to is_any_of, not just char*. Otherwise
          // there are cryptic warnings on Debian6 running g++ 4.4 in
          // /usr/include/c++/4.4/bits/stl_algo.h:2178 "array subscript is above
          // array bounds"
          boost::split(tokens, dba, boost::is_any_of(string("\t ")));
6
←
Calling 'split<std::vector<std::basic_string<char>>, std::basic_string<char> &, boost::algorithm::detail::is_any_ofF<char>>'→
          for (auto const& token : tokens) {
              size_t pos = token.find("=");
              if (pos != string::npos) {
                  string name = token.substr(0, pos);
                  string value = token.substr(pos + 1);
                  mapped_tokens.insert(make_pair(name, value));
              } else {
                  isc_throw(InvalidParameter, "Cannot parse " << tokendo { std::ostringstream oss__; oss__ << "Cannot parse "
 << token << ", expected format is name=value"; throw
 InvalidParameter("../../../src/lib/database/database_connection.cc"
, 94, oss__.str().c_str()); } while (1)
                            << ", expected format is name=value")do { std::ostringstream oss__; oss__ << "Cannot parse "
 << token << ", expected format is name=value"; throw
 InvalidParameter("../../../src/lib/database/database_connection.cc"
, 94, oss__.str().c_str()); } while (1);
              }
          }
      } catch (const std::exception& ex) {
          // We'd obscure the password if we could parse the access string.
          DB_LOG_ERROR(DB_INVALID_ACCESS).arg(dbaccess);
          throw;
      }
  }

  return (mapped_tokens);
105}

107std::string
108DatabaseConnection::redactedAccessString(const ParameterMap& parameters) {
  // Reconstruct the access string: start of with an empty string, then
  // work through all the parameters in the original string and add them.
  std::string access;
  for (auto const& i : parameters) {

      // Separate second and subsequent tokens are preceded by a space.
      if (!access.empty()) {
          access += " ";
      }

      // Append name of parameter...
      access += i.first;
      access += "=";

      // ... and the value, except in the case of the password, where a
      // redacted value is appended.
      if (i.first == std::string("password")) {
          access += "*****";
      } else {
          access += i.second;
      }
  }

  return (access);
133}

135bool
136DatabaseConnection::configuredReadOnly() const {
  std::string readonly_value = "false";
  try {
      readonly_value = getParameter("readonly");
      boost::algorithm::to_lower(readonly_value);
  } catch (...) {
      // Parameter "readonly" hasn't been specified so we simply use
      // the default value of "false".
  }

  if ((readonly_value != "false") && (readonly_value != "true")) {
      isc_throw(DbInvalidReadOnly, "invalid value '" << readonly_valuedo { std::ostringstream oss__; oss__ << "invalid value '"
 << readonly_value << "' specified for boolean parameter 'readonly'"
; throw DbInvalidReadOnly("../../../src/lib/database/database_connection.cc"
, 148, oss__.str().c_str()); } while (1)
                << "' specified for boolean parameter 'readonly'")do { std::ostringstream oss__; oss__ << "invalid value '"
 << readonly_value << "' specified for boolean parameter 'readonly'"
; throw DbInvalidReadOnly("../../../src/lib/database/database_connection.cc"
, 148, oss__.str().c_str()); } while (1);
  }

  return (readonly_value == "true");
152}

154void
155DatabaseConnection::makeReconnectCtl(const std::string& timer_name, unsigned int id) {
  string type = "unknown";
  unsigned int retries = 0;
  unsigned int interval = 0;

  // Assumes that parsing ensures only valid values are present
  try {
      type = getParameter("type");
  } catch (...) {
      // Wasn't specified so we'll use default of "unknown".
  }

  std::string parm_str;
  try {
      parm_str = getParameter("max-reconnect-tries");
      retries = boost::lexical_cast<unsigned int>(parm_str);
  } catch (...) {
      // Wasn't specified so we'll use default of 0;
  }

  try {
      parm_str = getParameter("reconnect-wait-time");
      interval = boost::lexical_cast<unsigned int>(parm_str);
  } catch (...) {
      // Wasn't specified so we'll use default of 0;
  }

  OnFailAction action = OnFailAction::STOP_RETRY_EXIT;
  try {
      parm_str = getParameter("on-fail");
      action = ReconnectCtl::onFailActionFromText(parm_str);
  } catch (...) {
      // Wasn't specified so we'll use default of "stop-retry-exit";
  }

  reconnect_ctl_ = boost::make_shared<ReconnectCtl>(type, timer_name, retries,
                                                    interval, action, id);
192}

194bool
195DatabaseConnection::invokeDbLostCallback(const ReconnectCtlPtr& db_reconnect_ctl) {
  if (DatabaseConnection::db_lost_callback_) {
      return (DatabaseConnection::db_lost_callback_(db_reconnect_ctl));
  }

  return (false);
201}

203bool
204DatabaseConnection::invokeDbRecoveredCallback(const ReconnectCtlPtr& db_reconnect_ctl) {
  if (DatabaseConnection::db_recovered_callback_) {
      return (DatabaseConnection::db_recovered_callback_(db_reconnect_ctl));
  }

  return (false);
210}

212bool
213DatabaseConnection::invokeDbFailedCallback(const ReconnectCtlPtr& db_reconnect_ctl) {
  if (DatabaseConnection::db_failed_callback_) {
      return (DatabaseConnection::db_failed_callback_(db_reconnect_ctl));
  }

  return (false);
219}

221isc::data::ElementPtr
222DatabaseConnection::toElement(const ParameterMap& params) {
  isc::data::ElementPtr result = isc::data::Element::createMap();

  for (auto const& param : params) {
      std::string keyword = param.first;
      std::string value = param.second;

      if ((keyword == "lfc-interval") ||
          (keyword == "connect-timeout") ||
          (keyword == "read-timeout") ||
          (keyword == "write-timeout") ||
          (keyword == "tcp-user-timeout") ||
          (keyword == "reconnect-wait-time") ||
          (keyword == "max-reconnect-tries") ||
          (keyword == "port") ||
          (keyword == "max-row-errors")) {
          // integer parameters
          int64_t int_value;
          try {
              int_value = boost::lexical_cast<int64_t>(value);
              result->set(keyword, isc::data::Element::create(int_value));
          } catch (...) {
              LOG_ERROR(database_logger, DATABASE_TO_JSON_INTEGER_ERROR)if (!(database_logger).isErrorEnabled()) { } else (database_logger
).error((DATABASE_TO_JSON_INTEGER_ERROR))
                  .arg(keyword).arg(value);
          }
      } else if ((keyword == "persist") ||
                 (keyword == "readonly") ||
                 (keyword == "retry-on-startup")) {
          if (value == "true") {
              result->set(keyword, isc::data::Element::create(true));
          } else if (value == "false") {
              result->set(keyword, isc::data::Element::create(false));
          } else {
              LOG_ERROR(database_logger, DATABASE_TO_JSON_BOOLEAN_ERROR)if (!(database_logger).isErrorEnabled()) { } else (database_logger
).error((DATABASE_TO_JSON_BOOLEAN_ERROR))
                  .arg(keyword).arg(value);
          }
      } else if ((keyword == "type") ||
                 (keyword == "user") ||
                 (keyword == "password") ||
                 (keyword == "host") ||
                 (keyword == "name") ||
                 (keyword == "on-fail") ||
                 (keyword == "trust-anchor") ||
                 (keyword == "cert-file") ||
                 (keyword == "key-file") ||
                 (keyword == "ssl-mode") ||
                 (keyword == "cipher-list")) {
          result->set(keyword, isc::data::Element::create(value));
      } else {
          LOG_ERROR(database_logger, DATABASE_TO_JSON_UNKNOWN_TYPE_ERROR)if (!(database_logger).isErrorEnabled()) { } else (database_logger
).error((DATABASE_TO_JSON_UNKNOWN_TYPE_ERROR))
                  .arg(keyword).arg(value);
      }
  }

  return (result);
277}

279isc::data::ElementPtr
280DatabaseConnection::toElementDbAccessString(const std::string& dbaccess) {
  ParameterMap params = parse(dbaccess);
1
Calling 'DatabaseConnection::parse'→
  return (toElement(params));
283}

285DbCallback DatabaseConnection::db_lost_callback_ = 0;
286DbCallback DatabaseConnection::db_recovered_callback_ = 0;
287DbCallback DatabaseConnection::db_failed_callback_ = 0;
288bool DatabaseConnection::retry_ = false;
289IOServicePtr DatabaseConnection::io_service_ = IOServicePtr();

291bool DatabaseConnection::test_mode_ = false;

293}  // namespace db
294}  // namespace isc

←

/usr/bin/../lib/gcc/x86_64-redhat-linux/15/../../../../include/c++/15/bits/basic_string.h

→

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

←

/usr/include/boost/algorithm/string/split.hpp

→

1//  Boost string_algo library split.hpp header file  ---------------------------//

3//  Copyright Pavol Droba 2002-2006.
4//
5// Distributed under the Boost Software License, Version 1.0.
6//    (See accompanying file LICENSE_1_0.txt or copy at
7//          http://www.boost.org/LICENSE_1_0.txt)

9//  See http://www.boost.org/ for updates, documentation, and revision history.

11#ifndef BOOST_STRING_SPLIT_HPP
12#define BOOST_STRING_SPLIT_HPP

14#include <boost/algorithm/string/config.hpp>

16#include <boost/algorithm/string/iter_find.hpp>
17#include <boost/algorithm/string/finder.hpp>
18#include <boost/algorithm/string/compare.hpp>

20/*! \file
  Defines basic split algorithms. 
  Split algorithms can be used to divide a string
  into several parts according to given criteria.
  
  Each part is copied and added as a new element to the
  output container.
  Thus the result container must be able to hold copies
  of the matches (in a compatible structure like std::string) or
  a reference to it (e.g. using the iterator range class).
  Examples of such a container are \c std::vector<std::string>
  or \c std::list<boost::iterator_range<std::string::iterator>>
32*/

34namespace boost {
  namespace algorithm {

37//  find_all  ------------------------------------------------------------//

      //! Find all algorithm
      /*!
          This algorithm finds all occurrences of the search string
          in the input.
          
          Each part is copied and added as a new element to the
          output container.
          Thus the result container must be able to hold copies
          of the matches (in a compatible structure like std::string) or
          a reference to it (e.g. using the iterator range class).
          Examples of such a container are \c std::vector<std::string>
          or \c std::list<boost::iterator_range<std::string::iterator>>

          \param Result A container that can hold copies of references to the substrings
          \param Input A container which will be searched.
          \param Search A substring to be searched for.
          \return A reference the result

          \note Prior content of the result will be overwritten.

          \note This function provides the strong exception-safety guarantee
      */
      template< typename SequenceSequenceT, typename Range1T, typename Range2T >
      inline SequenceSequenceT& find_all(
          SequenceSequenceT& Result,
64#if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
          Range1T&& Input,
66#else
          Range1T& Input,
68#endif
          const Range2T& Search)
      {
          return ::boost::algorithm::iter_find(
              Result,
              Input,
              ::boost::algorithm::first_finder(Search) );        
      }

      //! Find all algorithm ( case insensitive ) 
      /*!
          This algorithm finds all occurrences of the search string
          in the input. 
          Each part is copied and added as a new element to the
          output container. Thus the result container must be able to hold copies
          of the matches (in a compatible structure like std::string) or
          a reference to it (e.g. using the iterator range class).
          Examples of such a container are \c std::vector<std::string>
          or \c std::list<boost::iterator_range<std::string::iterator>>

          Searching is case insensitive.

          \param Result A container that can hold copies of references to the substrings
          \param Input A container which will be searched.
          \param Search A substring to be searched for.
          \param Loc A locale used for case insensitive comparison
          \return A reference the result

          \note Prior content of the result will be overwritten.

          \note This function provides the strong exception-safety guarantee
      */
      template< typename SequenceSequenceT, typename Range1T, typename Range2T >
      inline SequenceSequenceT& ifind_all(
          SequenceSequenceT& Result,
103#if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
          Range1T&& Input,
105#else
          Range1T& Input,
107#endif
          const Range2T& Search,
          const std::locale& Loc=std::locale() )
      {
          return ::boost::algorithm::iter_find(
              Result,
              Input,
              ::boost::algorithm::first_finder(Search, is_iequal(Loc) ) );        
      }


118//  tokenize  -------------------------------------------------------------//

      //! Split algorithm
      /*! 
          Tokenize expression. This function is equivalent to C strtok. Input
          sequence is split into tokens, separated by separators. Separators 
          are given by means of the predicate.

          Each part is copied and added as a new element to the
          output container.
          Thus the result container must be able to hold copies
          of the matches (in a compatible structure like std::string) or
          a reference to it (e.g. using the iterator range class).
          Examples of such a container are \c std::vector<std::string>
          or \c std::list<boost::iterator_range<std::string::iterator>>
  
          \param Result A container that can hold copies of references to the substrings          
          \param Input A container which will be searched.
          \param Pred A predicate to identify separators. This predicate is 
              supposed to return true if a given element is a separator.
          \param eCompress If eCompress argument is set to token_compress_on, adjacent 
              separators are merged together. Otherwise, every two separators
              delimit a token.
          \return A reference the result

          \note Prior content of the result will be overwritten.

          \note This function provides the strong exception-safety guarantee
      */
      template< typename SequenceSequenceT, typename RangeT, typename PredicateT >
      inline SequenceSequenceT& split(
          SequenceSequenceT& Result,
150#if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
          RangeT&& Input,
152#else
          RangeT& Input,
154#endif
          PredicateT Pred,
          token_compress_mode_type eCompress=token_compress_off )
      {
          return ::boost::algorithm::iter_split(
              Result,
              Input,
              ::boost::algorithm::token_finder( Pred, eCompress ) );         
7
←
Calling 'token_finder<boost::algorithm::detail::is_any_ofF<char>>'→
14
←
Returned allocated memory→
15
←
Calling '~is_any_ofF'→
      }

  } // namespace algorithm

  // pull names to the boost namespace
  using algorithm::find_all;
  using algorithm::ifind_all;
  using algorithm::split;    

171} // namespace boost


174#endif  // BOOST_STRING_SPLIT_HPP


←

/usr/include/boost/algorithm/string/finder.hpp

→

1//  Boost string_algo library finder.hpp header file  ---------------------------//

3//  Copyright Pavol Droba 2002-2006.
4//
5// Distributed under the Boost Software License, Version 1.0.
6//    (See accompanying file LICENSE_1_0.txt or copy at
7//          http://www.boost.org/LICENSE_1_0.txt)

9//  See http://www.boost.org/ for updates, documentation, and revision history.

11#ifndef BOOST_STRING_FINDER_HPP
12#define BOOST_STRING_FINDER_HPP

14#include <boost/algorithm/string/config.hpp>

16#include <boost/range/iterator_range_core.hpp>
17#include <boost/range/begin.hpp>
18#include <boost/range/end.hpp>
19#include <boost/range/iterator.hpp>
20#include <boost/range/const_iterator.hpp>

22#include <boost/algorithm/string/constants.hpp>
23#include <boost/algorithm/string/detail/finder.hpp>
24#include <boost/algorithm/string/compare.hpp>

26/*! \file
  Defines Finder generators. Finder object is a functor which is able to 
  find a substring matching a specific criteria in the input.
  Finders are used as a pluggable components for replace, find 
  and split facilities. This header contains generator functions 
  for finders provided in this library.
32*/

34namespace boost {
  namespace algorithm {

37//  Finder generators ------------------------------------------//
      
      //! "First" finder 
      /*!
          Construct the \c first_finder. The finder searches for the first
          occurrence of the string in a given input.
          The result is given as an \c iterator_range delimiting the match.

          \param Search A substring to be searched for.
          \return An instance of the \c first_finder object
      */
      template<typename RangeT>
      inline detail::first_finderF<
          BOOST_STRING_TYPENAMEtypename range_const_iterator<RangeT>::type,
          is_equal>
      first_finder( const RangeT& Search )
      {
          return 
              detail::first_finderF<
                  BOOST_STRING_TYPENAMEtypename 
                      range_const_iterator<RangeT>::type,
                      is_equal>( ::boost::as_literal(Search), is_equal() ) ;
      }

      //! "First" finder
      /*!
          \overload
      */
      template<typename RangeT,typename PredicateT>
      inline detail::first_finderF<
          BOOST_STRING_TYPENAMEtypename range_const_iterator<RangeT>::type,
          PredicateT>
      first_finder( 
          const RangeT& Search, PredicateT Comp )
      {
          return 
              detail::first_finderF<
                  BOOST_STRING_TYPENAMEtypename 
                      range_const_iterator<RangeT>::type,
                  PredicateT>( ::boost::as_literal(Search), Comp );
      }

      //! "Last" finder
      /*!
          Construct the \c last_finder. The finder searches for the last
          occurrence of the string in a given input.
          The result is given as an \c iterator_range delimiting the match.

          \param Search A substring to be searched for.
          \return An instance of the \c last_finder object
      */
      template<typename RangeT>
      inline detail::last_finderF<
          BOOST_STRING_TYPENAMEtypename range_const_iterator<RangeT>::type,
          is_equal>
      last_finder( const RangeT& Search )
      {
          return 
              detail::last_finderF<
                  BOOST_STRING_TYPENAMEtypename 
                      range_const_iterator<RangeT>::type,
                  is_equal>( ::boost::as_literal(Search), is_equal() );
      }
      //! "Last" finder
      /*!
          \overload
      */
      template<typename RangeT, typename PredicateT>
      inline detail::last_finderF<
          BOOST_STRING_TYPENAMEtypename range_const_iterator<RangeT>::type,
          PredicateT>
      last_finder( const RangeT& Search, PredicateT Comp )
      {
          return 
              detail::last_finderF<
                  BOOST_STRING_TYPENAMEtypename 
                      range_const_iterator<RangeT>::type,
                  PredicateT>( ::boost::as_literal(Search), Comp ) ;
      }

      //! "Nth" finder
      /*!
          Construct the \c nth_finder. The finder searches for the n-th (zero-indexed)
          occurrence of the string in a given input.
          The result is given as an \c iterator_range delimiting the match.

          \param Search A substring to be searched for.
          \param Nth An index of the match to be find
          \return An instance of the \c nth_finder object
      */
      template<typename RangeT>
      inline detail::nth_finderF<
          BOOST_STRING_TYPENAMEtypename range_const_iterator<RangeT>::type,
          is_equal>
      nth_finder( 
          const RangeT& Search, 
          int Nth)
      {
          return 
              detail::nth_finderF<
                  BOOST_STRING_TYPENAMEtypename 
                      range_const_iterator<RangeT>::type,
                  is_equal>( ::boost::as_literal(Search), Nth, is_equal() ) ;
      }
      //! "Nth" finder
      /*!
          \overload
      */
      template<typename RangeT, typename PredicateT>
      inline detail::nth_finderF<
          BOOST_STRING_TYPENAMEtypename range_const_iterator<RangeT>::type,
          PredicateT>
      nth_finder( 
          const RangeT& Search, 
          int Nth, 
          PredicateT Comp )
      {
          return 
              detail::nth_finderF<
                  BOOST_STRING_TYPENAMEtypename 
                      range_const_iterator<RangeT>::type,
                  PredicateT>( ::boost::as_literal(Search), Nth, Comp );
      }

      //! "Head" finder
      /*!
          Construct the \c head_finder. The finder returns a head of a given
          input. The head is a prefix of a string up to n elements in
          size. If an input has less then n elements, whole input is 
          considered a head.
          The result is given as an \c iterator_range delimiting the match.

          \param N The size of the head
          \return An instance of the \c head_finder object
      */
      inline detail::head_finderF
      head_finder( int N )
      {
          return detail::head_finderF(N);
      }
      
      //! "Tail" finder
      /*!
          Construct the \c tail_finder. The finder returns a tail of a given
          input. The tail is a suffix of a string up to n elements in
          size. If an input has less then n elements, whole input is 
          considered a head.
          The result is given as an \c iterator_range delimiting the match.

          \param N The size of the head
          \return An instance of the \c tail_finder object
      */
      inline detail::tail_finderF
      tail_finder( int N )
      {
          return detail::tail_finderF(N);
      }

      //! "Token" finder
      /*!
          Construct the \c token_finder. The finder searches for a token 
          specified by a predicate. It is similar to std::find_if 
          algorithm, with an exception that it return a range of
          instead of a single iterator.

          If "compress token mode" is enabled, adjacent matching tokens are 
          concatenated into one match. Thus the finder can be used to 
          search for continuous segments of characters satisfying the 
          given predicate.

          The result is given as an \c iterator_range delimiting the match.

          \param Pred An element selection predicate
          \param eCompress Compress flag
          \return An instance of the \c token_finder object
      */
      template< typename PredicateT >
      inline detail::token_finderF<PredicateT>
      token_finder( 
          PredicateT Pred, 
          token_compress_mode_type eCompress=token_compress_off )
      {
          return detail::token_finderF<PredicateT>( Pred, eCompress );
8
←
Calling constructor for 'token_finderF<boost::algorithm::detail::is_any_ofF<char>>'→
13
←
Returning from constructor for 'token_finderF<boost::algorithm::detail::is_any_ofF<char>>'→
      }

      //! "Range" finder
      /*!
          Construct the \c range_finder. The finder does not perform 
          any operation. It simply returns the given range for 
          any input. 

          \param Begin Beginning of the range
          \param End End of the range
          \return An instance of the \c range_finger object
      */
      template< typename ForwardIteratorT >
      inline detail::range_finderF<ForwardIteratorT>
      range_finder(
          ForwardIteratorT Begin,
          ForwardIteratorT End )
      {
          return detail::range_finderF<ForwardIteratorT>( Begin, End );
      }

      //! "Range" finder
      /*!       
          \overload
      */
      template< typename ForwardIteratorT >
      inline detail::range_finderF<ForwardIteratorT>
      range_finder( iterator_range<ForwardIteratorT> Range )
      {
          return detail::range_finderF<ForwardIteratorT>( Range );
      }

  } // namespace algorithm

  // pull the names to the boost namespace
  using algorithm::first_finder;
  using algorithm::last_finder;
  using algorithm::nth_finder;
  using algorithm::head_finder;
  using algorithm::tail_finder;
  using algorithm::token_finder;
  using algorithm::range_finder;

263} // namespace boost


266#endif  // BOOST_STRING_FINDER_HPP

←

/usr/include/boost/algorithm/string/detail/finder.hpp

→

1//  Boost string_algo library finder.hpp header file  ---------------------------//

3//  Copyright Pavol Droba 2002-2006.
4//
5// Distributed under the Boost Software License, Version 1.0.
6//    (See accompanying file LICENSE_1_0.txt or copy at
7//          http://www.boost.org/LICENSE_1_0.txt)

9//  See http://www.boost.org/ for updates, documentation, and revision history.

11#ifndef BOOST_STRING_FINDER_DETAIL_HPP
12#define BOOST_STRING_FINDER_DETAIL_HPP

14#include <boost/algorithm/string/config.hpp>
15#include <boost/algorithm/string/constants.hpp>
16#include <iterator>

18#include <boost/range/iterator_range_core.hpp>
19#include <boost/range/begin.hpp>
20#include <boost/range/end.hpp>
21#include <boost/range/empty.hpp>
22#include <boost/range/as_literal.hpp>

24namespace boost {
  namespace algorithm {
      namespace detail {


29//  find first functor -----------------------------------------------//

          // find a subsequence in the sequence ( functor )
          /*
              Returns a pair <begin,end> marking the subsequence in the sequence.
              If the find fails, functor returns <End,End>
          */
          template<typename SearchIteratorT,typename PredicateT>
          struct first_finderF
          {
              typedef SearchIteratorT search_iterator_type;

              // Construction
              template< typename SearchT >
              first_finderF( const SearchT& Search, PredicateT Comp ) :
                  m_Search(::boost::begin(Search), ::boost::end(Search)), m_Comp(Comp) {}
              first_finderF(
                      search_iterator_type SearchBegin,
                      search_iterator_type SearchEnd,
                      PredicateT Comp ) :
                  m_Search(SearchBegin, SearchEnd), m_Comp(Comp) {}

              // Operation
              template< typename ForwardIteratorT >
              iterator_range<ForwardIteratorT>
              operator()(
                  ForwardIteratorT Begin,
                  ForwardIteratorT End ) const
              {
                  typedef iterator_range<ForwardIteratorT> result_type;
                  typedef ForwardIteratorT input_iterator_type;

                  // Outer loop
                  for(input_iterator_type OuterIt=Begin;
                      OuterIt!=End;
                      ++OuterIt)
                  {
                      // Sanity check
                      if( boost::empty(m_Search) )
                          return result_type( End, End );

                      input_iterator_type InnerIt=OuterIt;
                      search_iterator_type SubstrIt=m_Search.begin();
                      for(;
                          InnerIt!=End && SubstrIt!=m_Search.end();
                          ++InnerIt,++SubstrIt)
                      {
                          if( !( m_Comp(*InnerIt,*SubstrIt) ) )
                              break;
                      }

                      // Substring matching succeeded
                      if ( SubstrIt==m_Search.end() )
                          return result_type( OuterIt, InnerIt );
                  }

                  return result_type( End, End );
              }

          private:
              iterator_range<search_iterator_type> m_Search;
              PredicateT m_Comp;
          };

93//  find last functor -----------------------------------------------//

          // find the last match a subsequence in the sequence ( functor )
          /*
              Returns a pair <begin,end> marking the subsequence in the sequence.
              If the find fails, returns <End,End>
          */
          template<typename SearchIteratorT, typename PredicateT>
          struct last_finderF
          {
              typedef SearchIteratorT search_iterator_type;
              typedef first_finderF<
                  search_iterator_type,
                  PredicateT> first_finder_type;

              // Construction
              template< typename SearchT >
              last_finderF( const SearchT& Search, PredicateT Comp ) :
                  m_Search(::boost::begin(Search), ::boost::end(Search)), m_Comp(Comp) {}
              last_finderF(
                      search_iterator_type SearchBegin,
                      search_iterator_type SearchEnd,
                      PredicateT Comp ) :
                  m_Search(SearchBegin, SearchEnd), m_Comp(Comp) {}

              // Operation
              template< typename ForwardIteratorT >
              iterator_range<ForwardIteratorT>
              operator()(
                  ForwardIteratorT Begin,
                  ForwardIteratorT End ) const
              {
                  typedef iterator_range<ForwardIteratorT> result_type;

                  if( boost::empty(m_Search) )
                      return result_type( End, End );

                  typedef BOOST_STRING_TYPENAMEtypename
                      std::iterator_traits<ForwardIteratorT>::iterator_category category;

                  return findit( Begin, End, category() );
              }

          private:
              // forward iterator
              template< typename ForwardIteratorT >
              iterator_range<ForwardIteratorT>
              findit(
                  ForwardIteratorT Begin,
                  ForwardIteratorT End,
                  std::forward_iterator_tag ) const
              {
                  typedef iterator_range<ForwardIteratorT> result_type;

                  first_finder_type first_finder(
                      m_Search.begin(), m_Search.end(), m_Comp );

                  result_type M=first_finder( Begin, End );
                  result_type Last=M;

                  while( M )
                  {
                      Last=M;
                      M=first_finder( ::boost::end(M), End );
                  }

                  return Last;
              }

              // bidirectional iterator
              template< typename ForwardIteratorT >
              iterator_range<ForwardIteratorT>
              findit(
                  ForwardIteratorT Begin,
                  ForwardIteratorT End,
                  std::bidirectional_iterator_tag ) const
              {
                  typedef iterator_range<ForwardIteratorT> result_type;
                  typedef ForwardIteratorT input_iterator_type;

                  // Outer loop
                  for(input_iterator_type OuterIt=End;
                      OuterIt!=Begin; )
                  {
                      input_iterator_type OuterIt2=--OuterIt;

                      input_iterator_type InnerIt=OuterIt2;
                      search_iterator_type SubstrIt=m_Search.begin();
                      for(;
                          InnerIt!=End && SubstrIt!=m_Search.end();
                          ++InnerIt,++SubstrIt)
                      {
                          if( !( m_Comp(*InnerIt,*SubstrIt) ) )
                              break;
                      }

                      // Substring matching succeeded
                      if( SubstrIt==m_Search.end() )
                          return result_type( OuterIt2, InnerIt );
                  }

                  return result_type( End, End );
              }

          private:
              iterator_range<search_iterator_type> m_Search;
              PredicateT m_Comp;
          };

202//  find n-th functor -----------------------------------------------//

          // find the n-th match of a subsequence in the sequence ( functor )
          /*
              Returns a pair <begin,end> marking the subsequence in the sequence.
              If the find fails, returns <End,End>
          */
          template<typename SearchIteratorT, typename PredicateT>
          struct nth_finderF
          {
              typedef SearchIteratorT search_iterator_type;
              typedef first_finderF<
                  search_iterator_type,
                  PredicateT> first_finder_type;
              typedef last_finderF<
                  search_iterator_type,
                  PredicateT> last_finder_type;

              // Construction
              template< typename SearchT >
              nth_finderF(
                      const SearchT& Search,
                      int Nth,
                      PredicateT Comp) :
                  m_Search(::boost::begin(Search), ::boost::end(Search)),
                  m_Nth(Nth),
                  m_Comp(Comp) {}
              nth_finderF(
                      search_iterator_type SearchBegin,
                      search_iterator_type SearchEnd,
                      int Nth,
                      PredicateT Comp) :
                  m_Search(SearchBegin, SearchEnd),
                  m_Nth(Nth),
                  m_Comp(Comp) {}

              // Operation
              template< typename ForwardIteratorT >
              iterator_range<ForwardIteratorT>
              operator()(
                  ForwardIteratorT Begin,
                  ForwardIteratorT End ) const
              {
                  if(m_Nth>=0)
                  {
                      return find_forward(Begin, End, m_Nth);
                  }
                  else
                  {
                      return find_backward(Begin, End, -m_Nth);
                  }

              }

          private:
              // Implementation helpers
              template< typename ForwardIteratorT >
              iterator_range<ForwardIteratorT>
              find_forward(
                  ForwardIteratorT Begin,
                  ForwardIteratorT End,
                  unsigned int N) const
              {
                  typedef iterator_range<ForwardIteratorT> result_type;

                  // Sanity check
                  if( boost::empty(m_Search) )
                      return result_type( End, End );

                  // Instantiate find functor
                  first_finder_type first_finder(
                      m_Search.begin(), m_Search.end(), m_Comp );

                  result_type M( Begin, Begin );

                  for( unsigned int n=0; n<=N; ++n )
                  {
                      // find next match
                      M=first_finder( ::boost::end(M), End );

                      if ( !M )
                      {
                          // Subsequence not found, return
                          return M;
                      }
                  }

                  return M;
              }

              template< typename ForwardIteratorT >
              iterator_range<ForwardIteratorT>
              find_backward(
                  ForwardIteratorT Begin,
                  ForwardIteratorT End,
                  unsigned int N) const
              {
                  typedef iterator_range<ForwardIteratorT> result_type;

                  // Sanity check
                  if( boost::empty(m_Search) )
                      return result_type( End, End );

                  // Instantiate find functor
                  last_finder_type last_finder(
                      m_Search.begin(), m_Search.end(), m_Comp );

                  result_type M( End, End );

                  for( unsigned int n=1; n<=N; ++n )
                  {
                      // find next match
                      M=last_finder( Begin, ::boost::begin(M) );

                      if ( !M )
                      {
                          // Subsequence not found, return
                          return M;
                      }
                  }

                  return M;
              }


          private:
              iterator_range<search_iterator_type> m_Search;
              int m_Nth;
              PredicateT m_Comp;
          };

333//  find head/tail implementation helpers ---------------------------//

          template<typename ForwardIteratorT>
              iterator_range<ForwardIteratorT>
          find_head_impl(
              ForwardIteratorT Begin,
              ForwardIteratorT End,
              unsigned int N,
              std::forward_iterator_tag )
          {
              typedef ForwardIteratorT input_iterator_type;
              typedef iterator_range<ForwardIteratorT> result_type;

              input_iterator_type It=Begin;
              for( unsigned int Index=0; Index<N && It!=End; ++Index,++It )
                  ;

              return result_type( Begin, It );
          }

          template< typename ForwardIteratorT >
              iterator_range<ForwardIteratorT>
          find_head_impl(
              ForwardIteratorT Begin,
              ForwardIteratorT End,
              unsigned int N,
              std::random_access_iterator_tag )
          {
              typedef iterator_range<ForwardIteratorT> result_type;

              if ( (End<=Begin) || ( static_cast<unsigned int>(End-Begin) < N ) )
                  return result_type( Begin, End );

              return result_type(Begin,Begin+N);
          }

          // Find head implementation
          template<typename ForwardIteratorT>
              iterator_range<ForwardIteratorT>
          find_head_impl(
              ForwardIteratorT Begin,
              ForwardIteratorT End,
              unsigned int N )
          {
              typedef BOOST_STRING_TYPENAMEtypename
                  std::iterator_traits<ForwardIteratorT>::iterator_category category;

              return ::boost::algorithm::detail::find_head_impl( Begin, End, N, category() );
          }

          template< typename ForwardIteratorT >
              iterator_range<ForwardIteratorT>
          find_tail_impl(
              ForwardIteratorT Begin,
              ForwardIteratorT End,
              unsigned int N,
              std::forward_iterator_tag )
          {
              typedef ForwardIteratorT input_iterator_type;
              typedef iterator_range<ForwardIteratorT> result_type;

              unsigned int Index=0;
              input_iterator_type It=Begin;
              input_iterator_type It2=Begin;

              // Advance It2 by N increments
              for( Index=0; Index<N && It2!=End; ++Index,++It2 )
                  ;

              // Advance It, It2 to the end
              for(; It2!=End; ++It,++It2 )
              	;

              return result_type( It, It2 );
          }

          template< typename ForwardIteratorT >
              iterator_range<ForwardIteratorT>
          find_tail_impl(
              ForwardIteratorT Begin,
              ForwardIteratorT End,
              unsigned int N,
              std::bidirectional_iterator_tag )
          {
              typedef ForwardIteratorT input_iterator_type;
              typedef iterator_range<ForwardIteratorT> result_type;

              input_iterator_type It=End;
              for( unsigned int Index=0; Index<N && It!=Begin; ++Index,--It )
                  ;

              return result_type( It, End );
          }

          template< typename ForwardIteratorT >
              iterator_range<ForwardIteratorT>
          find_tail_impl(
              ForwardIteratorT Begin,
              ForwardIteratorT End,
              unsigned int N,
              std::random_access_iterator_tag )
          {
              typedef iterator_range<ForwardIteratorT> result_type;

              if ( (End<=Begin) || ( static_cast<unsigned int>(End-Begin) < N ) )
                  return result_type( Begin, End );

              return result_type( End-N, End );
          }

                      // Operation
          template< typename ForwardIteratorT >
          iterator_range<ForwardIteratorT>
          find_tail_impl(
              ForwardIteratorT Begin,
              ForwardIteratorT End,
              unsigned int N )
          {
              typedef BOOST_STRING_TYPENAMEtypename
                  std::iterator_traits<ForwardIteratorT>::iterator_category category;

              return ::boost::algorithm::detail::find_tail_impl( Begin, End, N, category() );
          }



459//  find head functor -----------------------------------------------//


          // find a head in the sequence ( functor )
          /*
              This functor find a head of the specified range. For
              a specified N, the head is a subsequence of N starting
              elements of the range.
          */
          struct head_finderF
          {
              // Construction
              head_finderF( int N ) : m_N(N) {}

              // Operation
              template< typename ForwardIteratorT >
              iterator_range<ForwardIteratorT>
              operator()(
                  ForwardIteratorT Begin,
                  ForwardIteratorT End ) const
              {
                  if(m_N>=0)
                  {
                      return ::boost::algorithm::detail::find_head_impl( Begin, End, m_N );
                  }
                  else
                  {
                      iterator_range<ForwardIteratorT> Res=
                          ::boost::algorithm::detail::find_tail_impl( Begin, End, -m_N );

                      return ::boost::make_iterator_range(Begin, Res.begin());
                  }
              }

          private:
              int m_N;
          };

497//  find tail functor -----------------------------------------------//


          // find a tail in the sequence ( functor )
          /*
              This functor find a tail of the specified range. For
              a specified N, the head is a subsequence of N starting
              elements of the range.
          */
          struct tail_finderF
          {
              // Construction
              tail_finderF( int N ) : m_N(N) {}

              // Operation
              template< typename ForwardIteratorT >
              iterator_range<ForwardIteratorT>
              operator()(
                  ForwardIteratorT Begin,
                  ForwardIteratorT End ) const
              {
                  if(m_N>=0)
                  {
                      return ::boost::algorithm::detail::find_tail_impl( Begin, End, m_N );
                  }
                  else
                  {
                      iterator_range<ForwardIteratorT> Res=
                          ::boost::algorithm::detail::find_head_impl( Begin, End, -m_N );

                      return ::boost::make_iterator_range(Res.end(), End);
                  }
              }

          private:
              int m_N;
          };

535//  find token functor -----------------------------------------------//

          // find a token in a sequence ( functor )
          /*
              This find functor finds a token specified be a predicate
              in a sequence. It is equivalent of std::find algorithm,
              with an exception that it return range instead of a single
              iterator.

              If bCompress is set to true, adjacent matching tokens are
              concatenated into one match.
          */
          template< typename PredicateT >
          struct token_finderF
          {
              // Construction
              token_finderF(
                  PredicateT Pred,
                  token_compress_mode_type eCompress=token_compress_off ) :
                      m_Pred(Pred), m_eCompress(eCompress) {}
9
←
Calling copy constructor for 'is_any_ofF<char>'→
12
←
Returning from copy constructor for 'is_any_ofF<char>'→

              // Operation
              template< typename ForwardIteratorT >
              iterator_range<ForwardIteratorT>
              operator()(
                  ForwardIteratorT Begin,
                  ForwardIteratorT End ) const
              {
                  typedef iterator_range<ForwardIteratorT> result_type;

                  ForwardIteratorT It=std::find_if( Begin, End, m_Pred );

                  if( It==End )
                  {
                      return result_type( End, End );
                  }
                  else
                  {
                      ForwardIteratorT It2=It;

                      if( m_eCompress==token_compress_on )
                      {
                          // Find first non-matching character
                          while( It2!=End && m_Pred(*It2) ) ++It2;
                      }
                      else
                      {
                          // Advance by one position
                          ++It2;
                      }

                      return result_type( It, It2 );
                  }
              }

          private:
              PredicateT m_Pred;
              token_compress_mode_type m_eCompress;
          };

595//  find range functor -----------------------------------------------//

          // find a range in the sequence ( functor )
          /*
              This functor actually does not perform any find operation.
              It always returns given iterator range as a result.
          */
          template<typename ForwardIterator1T>
          struct range_finderF
          {
              typedef ForwardIterator1T input_iterator_type;
              typedef iterator_range<input_iterator_type> result_type;

              // Construction
              range_finderF(
                  input_iterator_type Begin,
                  input_iterator_type End ) : m_Range(Begin, End) {}

              range_finderF(const iterator_range<input_iterator_type>& Range) :
                  m_Range(Range) {}

              // Operation
              template< typename ForwardIterator2T >
              iterator_range<ForwardIterator2T>
              operator()(
                  ForwardIterator2T,
                  ForwardIterator2T ) const
              {
623#if BOOST_WORKAROUND( __MWERKS__, <= 0x3003 )((1 + 0 == 0) && (__MWERKS__ != 0) && (1 % ((
 (__MWERKS__ <= 0x3003) ) + 1))) 
                  return iterator_range<const ForwardIterator2T>(this->m_Range);
625#else
                  return m_Range;
627#endif
              }

          private:
              iterator_range<input_iterator_type> m_Range;
          };


      } // namespace detail
  } // namespace algorithm
637} // namespace boost

639#endif  // BOOST_STRING_FINDER_DETAIL_HPP

←

/usr/include/boost/algorithm/string/detail/classification.hpp

1//  Boost string_algo library classification.hpp header file  ---------------------------//

3//  Copyright Pavol Droba 2002-2003.
4// 
5// Distributed under the Boost Software License, Version 1.0.
6//    (See accompanying file LICENSE_1_0.txt or copy at
7//          http://www.boost.org/LICENSE_1_0.txt)

9//  See http://www.boost.org/ for updates, documentation, and revision history.

11#ifndef BOOST_STRING_CLASSIFICATION_DETAIL_HPP
12#define BOOST_STRING_CLASSIFICATION_DETAIL_HPP

14#include <boost/algorithm/string/config.hpp>
15#include <algorithm>
16#include <cstring>
17#include <functional>
18#include <locale>

20#include <boost/range/begin.hpp>
21#include <boost/range/distance.hpp>
22#include <boost/range/end.hpp>

24#include <boost/algorithm/string/predicate_facade.hpp>
25#include <boost/type_traits/remove_const.hpp>

27namespace boost {
  namespace algorithm {
      namespace detail {

31//  classification functors -----------------------------------------------//

 // is_classified functor
          struct is_classifiedF :
              public predicate_facade<is_classifiedF>
          {
              // Boost.ResultOf support
              typedef bool result_type;

              // Constructor from a locale
              is_classifiedF(std::ctype_base::mask Type, std::locale const & Loc = std::locale()) :
                  m_Type(Type), m_Locale(Loc) {}
              // Operation
              template<typename CharT>
              bool operator()( CharT Ch ) const
              {
                  return std::use_facet< std::ctype<CharT> >(m_Locale).is( m_Type, Ch );
              }

              #if defined(BOOST_BORLANDC) && (BOOST_BORLANDC >= 0x560) && (BOOST_BORLANDC <= 0x582) && !defined(_USE_OLD_RW_STL)
                  template<>
                  bool operator()( char const Ch ) const
                  {
                      return std::use_facet< std::ctype<char> >(m_Locale).is( m_Type, Ch );
                  }
              #endif

          private:
              std::ctype_base::mask m_Type;
              std::locale m_Locale;
          };


          // is_any_of functor
          /*
              returns true if the value is from the specified set
          */
          template<typename CharT>
          struct is_any_ofF :
              public predicate_facade<is_any_ofF<CharT> >
          {
          private:
              // set cannot operate on const value-type
              typedef typename ::boost::remove_const<CharT>::type set_value_type;

          public:     
              // Boost.ResultOf support
              typedef bool result_type;

              // Constructor
              template<typename RangeT>
              is_any_ofF( const RangeT& Range ) : m_Size(0)
              {
                  // Prepare storage
                  m_Storage.m_dynSet=0;

                  std::size_t Size=::boost::distance(Range);
                  m_Size=Size;
                  set_value_type* Storage=0;

                  if(use_fixed_storage(m_Size))
                  {
                      // Use fixed storage
                      Storage=&m_Storage.m_fixSet[0];
                  }
                  else
                  {
                      // Use dynamic storage
                      m_Storage.m_dynSet=new set_value_type[m_Size];
                      Storage=m_Storage.m_dynSet;
                  }

                  // Use fixed storage
                  ::std::copy(::boost::begin(Range), ::boost::end(Range), Storage);
                  ::std::sort(Storage, Storage+m_Size);
              }

              // Copy constructor
              is_any_ofF(const is_any_ofF& Other) : m_Size(Other.m_Size)
              {
                  // Prepare storage
                  m_Storage.m_dynSet=0;               
                  const set_value_type* SrcStorage=0;
                  set_value_type* DestStorage=0;

                  if(use_fixed_storage(m_Size))
10
←
Taking false branch→
                  {
                      // Use fixed storage
                      DestStorage=&m_Storage.m_fixSet[0];
                      SrcStorage=&Other.m_Storage.m_fixSet[0];
                  }
                  else
                  {
                      // Use dynamic storage
                      m_Storage.m_dynSet=new set_value_type[m_Size];
11
←
Memory is allocated→
                      DestStorage=m_Storage.m_dynSet;
                      SrcStorage=Other.m_Storage.m_dynSet;
                  }

                  // Use fixed storage
                  ::std::memcpy(DestStorage, SrcStorage, sizeof(set_value_type)*m_Size);
              }

              // Destructor
              ~is_any_ofF()
              {
                  if(!use_fixed_storage(m_Size) && m_Storage.m_dynSet!=0)
16
←
Potential memory leak
                  {
                      delete [] m_Storage.m_dynSet;
                  }
              }

              // Assignment
              is_any_ofF& operator=(const is_any_ofF& Other)
              {
                  // Handle self assignment
                  if(this==&Other) return *this;

                  // Prepare storage             
                  const set_value_type* SrcStorage;
                  set_value_type* DestStorage;

                  if(use_fixed_storage(Other.m_Size))
                  {
                      // Use fixed storage
                      DestStorage=&m_Storage.m_fixSet[0];
                      SrcStorage=&Other.m_Storage.m_fixSet[0];

                      // Delete old storage if was present
                      if(!use_fixed_storage(m_Size) && m_Storage.m_dynSet!=0)
                      {
                          delete [] m_Storage.m_dynSet;
                      }

                      // Set new size
                      m_Size=Other.m_Size;
                  }
                  else
                  {
                      // Other uses dynamic storage
                      SrcStorage=Other.m_Storage.m_dynSet;

                      // Check what kind of storage are we using right now
                      if(use_fixed_storage(m_Size))
                      {
                          // Using fixed storage, allocate new
                          set_value_type* pTemp=new set_value_type[Other.m_Size];
                          DestStorage=pTemp;
                          m_Storage.m_dynSet=pTemp;
                          m_Size=Other.m_Size;
                      }
                      else
                      {
                          // Using dynamic storage, check if can reuse
                          if(m_Storage.m_dynSet!=0 && m_Size>=Other.m_Size && m_Size<Other.m_Size*2)
                          {
                              // Reuse the current storage
                              DestStorage=m_Storage.m_dynSet;
                              m_Size=Other.m_Size;
                          }
                          else
                          {
                              // Allocate the new one
                              set_value_type* pTemp=new set_value_type[Other.m_Size];
                              DestStorage=pTemp;
                      
                              // Delete old storage if necessary
                              if(m_Storage.m_dynSet!=0)
                              {
                                  delete [] m_Storage.m_dynSet;
                              }
                              // Store the new storage
                              m_Storage.m_dynSet=pTemp;
                              // Set new size
                              m_Size=Other.m_Size;
                          }
                      }
                  }

                  // Copy the data
                  ::std::memcpy(DestStorage, SrcStorage, sizeof(set_value_type)*m_Size);

                  return *this;
              }

              // Operation
              template<typename Char2T>
              bool operator()( Char2T Ch ) const
              {
                  const set_value_type* Storage=
                      (use_fixed_storage(m_Size))
                      ? &m_Storage.m_fixSet[0]
                      : m_Storage.m_dynSet;

                  return ::std::binary_search(Storage, Storage+m_Size, Ch);
              }
          private:
              // check if the size is eligible for fixed storage
              static bool use_fixed_storage(std::size_t size)
              {
                  return size<=sizeof(set_value_type*)*2;
              }


          private:
              // storage
              // The actual used storage is selected on the type
              union
              {
                  set_value_type* m_dynSet;
                  set_value_type m_fixSet[sizeof(set_value_type*)*2];
              } 
              m_Storage;
      
              // storage size
              ::std::size_t m_Size;
          };

          // is_from_range functor
          /*
              returns true if the value is from the specified range.
              (i.e. x>=From && x>=To)
          */
          template<typename CharT>
          struct is_from_rangeF :
              public predicate_facade< is_from_rangeF<CharT> >
          {
              // Boost.ResultOf support
              typedef bool result_type;

              // Constructor
              is_from_rangeF( CharT From, CharT To ) : m_From(From), m_To(To) {}

              // Operation
              template<typename Char2T>
              bool operator()( Char2T Ch ) const
              {
                  return ( m_From <= Ch ) && ( Ch <= m_To );
              }

          private:
              CharT m_From;
              CharT m_To;
          };

          // class_and composition predicate
          template<typename Pred1T, typename Pred2T>
          struct pred_andF :
              public predicate_facade< pred_andF<Pred1T,Pred2T> >
          {
          public:

              // Boost.ResultOf support
              typedef bool result_type;

              // Constructor
              pred_andF( Pred1T Pred1, Pred2T Pred2 ) :
                  m_Pred1(Pred1), m_Pred2(Pred2) {}

              // Operation
              template<typename CharT>
              bool operator()( CharT Ch ) const
              {
                  return m_Pred1(Ch) && m_Pred2(Ch);
              }

          private:
              Pred1T m_Pred1;
              Pred2T m_Pred2;
          };

          // class_or composition predicate
          template<typename Pred1T, typename Pred2T>
          struct pred_orF :
              public predicate_facade< pred_orF<Pred1T,Pred2T> >
          {
          public:
              // Boost.ResultOf support
              typedef bool result_type;

              // Constructor
              pred_orF( Pred1T Pred1, Pred2T Pred2 ) :
                  m_Pred1(Pred1), m_Pred2(Pred2) {}

              // Operation
              template<typename CharT>
              bool operator()( CharT Ch ) const
              {
                  return m_Pred1(Ch) || m_Pred2(Ch);
              }

          private:
              Pred1T m_Pred1;
              Pred2T m_Pred2;
          };

          // class_not composition predicate
          template< typename PredT >
          struct pred_notF :
              public predicate_facade< pred_notF<PredT> >
          {
          public:
              // Boost.ResultOf support
              typedef bool result_type;

              // Constructor
              pred_notF( PredT Pred ) : m_Pred(Pred) {}

              // Operation
              template<typename CharT>
              bool operator()( CharT Ch ) const
              {
                  return !m_Pred(Ch);
              }

          private:
              PredT m_Pred;
          };

      } // namespace detail
  } // namespace algorithm
352} // namespace boost


355#endif  // BOOST_STRING_CLASSIFICATION_DETAIL_HPP