ocrm.bsky.social
the game where you go into mines and start crafting! but for consoles (forked directly from smartcmd's github)
1//////////////////////////////////////////////////////////////////////////////
2//
3// (C) Copyright Ion Gaztanaga 2005-2012. Distributed under the Boost
4// Software License, Version 1.0. (See accompanying file
5// LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6//
7// See http://www.boost.org/libs/container for documentation.
8//
9//////////////////////////////////////////////////////////////////////////////
10// Copyright (c) 1996,1997
11// Silicon Graphics Computer Systems, Inc.
12//
13// Permission to use, copy, modify, distribute and sell this software
14// and its documentation for any purpose is hereby granted without fee,
15// provided that the above copyright notice appear in all copies and
16// that both that copyright notice and this permission notice appear
17// in supporting documentation. Silicon Graphics makes no
18// representations about the suitability of this software for any
19// purpose. It is provided "as is" without express or implied warranty.
20//
21//
22// Copyright (c) 1994
23// Hewlett-Packard Company
24//
25// Permission to use, copy, modify, distribute and sell this software
26// and its documentation for any purpose is hereby granted without fee,
27// provided that the above copyright notice appear in all copies and
28// that both that copyright notice and this permission notice appear
29// in supporting documentation. Hewlett-Packard Company makes no
30// representations about the suitability of this software for any
31// purpose. It is provided "as is" without express or implied warranty.
32
33#ifndef BOOST_CONTAINER_STRING_HPP
34#define BOOST_CONTAINER_STRING_HPP
35
36#include <boost/container/detail/config_begin.hpp>
37#include <boost/container/detail/workaround.hpp>
38
39#include <boost/container/detail/workaround.hpp>
40#include <boost/container/container_fwd.hpp>
41#include <boost/container/detail/utilities.hpp>
42#include <boost/container/detail/iterators.hpp>
43#include <boost/container/detail/algorithms.hpp>
44#include <boost/container/detail/version_type.hpp>
45#include <boost/container/detail/allocation_type.hpp>
46#include <boost/container/allocator_traits.hpp>
47#include <boost/container/detail/allocator_version_traits.hpp>
48#include <boost/container/detail/mpl.hpp>
49#include <boost/move/utility.hpp>
50#include <boost/static_assert.hpp>
51#include <boost/functional/hash.hpp>
52#include <boost/intrusive/pointer_traits.hpp>
53#include <boost/detail/no_exceptions_support.hpp>
54
55#include <functional>
56#include <string>
57#include <stdexcept>
58#include <utility>
59#include <iterator>
60#include <memory>
61#include <algorithm>
62#include <iosfwd>
63#include <istream>
64#include <ostream>
65#include <ios>
66#include <locale>
67#include <cstddef>
68#include <climits>
69#include <boost/container/detail/type_traits.hpp>
70#include <boost/detail/no_exceptions_support.hpp>
71#include <boost/type_traits/has_trivial_destructor.hpp>
72#include <boost/aligned_storage.hpp>
73
74namespace boost {
75namespace container {
76
77/// @cond
78namespace container_detail {
79// ------------------------------------------------------------
80// Class basic_string_base.
81
82// basic_string_base is a helper class that makes it it easier to write
83// an exception-safe version of basic_string. The constructor allocates,
84// but does not initialize, a block of memory. The destructor
85// deallocates, but does not destroy elements within, a block of
86// memory. The destructor assumes that the memory either is the internal buffer,
87// or else points to a block of memory that was allocated using string_base's
88// allocator and whose size is this->m_storage.
89template <class Allocator>
90class basic_string_base
91{
92 BOOST_MOVABLE_BUT_NOT_COPYABLE(basic_string_base)
93
94 typedef allocator_traits<Allocator> allocator_traits_type;
95 public:
96 typedef Allocator allocator_type;
97 typedef allocator_type stored_allocator_type;
98 typedef typename allocator_traits_type::pointer pointer;
99 typedef typename allocator_traits_type::value_type value_type;
100 typedef typename allocator_traits_type::size_type size_type;
101 typedef ::boost::intrusive::pointer_traits<pointer> pointer_traits;
102
103 basic_string_base()
104 : members_()
105 { init(); }
106
107 basic_string_base(const allocator_type& a)
108 : members_(a)
109 { init(); }
110
111 basic_string_base(const allocator_type& a, size_type n)
112 : members_(a)
113 {
114 this->init();
115 this->allocate_initial_block(n);
116 }
117
118 basic_string_base(BOOST_RV_REF(basic_string_base) b)
119 : members_(boost::move(b.alloc()))
120 {
121 this->init();
122 this->swap_data(b);
123 }
124
125 ~basic_string_base()
126 {
127 if(!this->is_short()){
128 this->deallocate_block();
129 this->is_short(true);
130 }
131 }
132
133 private:
134
135 //This is the structure controlling a long string
136 struct long_t
137 {
138 size_type is_short : 1;
139 size_type length : (sizeof(size_type)*CHAR_BIT - 1);
140 size_type storage;
141 pointer start;
142
143 long_t()
144 {}
145
146 long_t(const long_t &other)
147 {
148 this->is_short = other.is_short;
149 length = other.length;
150 storage = other.storage;
151 start = other.start;
152 }
153
154 long_t &operator =(const long_t &other)
155 {
156 this->is_short = other.is_short;
157 length = other.length;
158 storage = other.storage;
159 start = other.start;
160 return *this;
161 }
162 };
163
164 //This type is the first part of the structure controlling a short string
165 //The "data" member stores
166 struct short_header
167 {
168 unsigned char is_short : 1;
169 unsigned char length : (CHAR_BIT - 1);
170 };
171
172 //This type has the same alignment and size as long_t but it's POD
173 //so, unlike long_t, it can be placed in a union
174
175 typedef typename boost::aligned_storage< sizeof(long_t),
176 container_detail::alignment_of<long_t>::value>::type long_raw_t;
177
178 protected:
179 static const size_type MinInternalBufferChars = 8;
180 static const size_type AlignmentOfValueType =
181 alignment_of<value_type>::value;
182 static const size_type ShortDataOffset =
183 container_detail::ct_rounded_size<sizeof(short_header), AlignmentOfValueType>::value;
184 static const size_type ZeroCostInternalBufferChars =
185 (sizeof(long_t) - ShortDataOffset)/sizeof(value_type);
186 static const size_type UnalignedFinalInternalBufferChars =
187 (ZeroCostInternalBufferChars > MinInternalBufferChars) ?
188 ZeroCostInternalBufferChars : MinInternalBufferChars;
189
190 struct short_t
191 {
192 short_header h;
193 value_type data[UnalignedFinalInternalBufferChars];
194 };
195
196 union repr_t
197 {
198 long_raw_t r;
199 short_t s;
200
201 const short_t &short_repr() const
202 { return s; }
203
204 const long_t &long_repr() const
205 { return *static_cast<const long_t*>(static_cast<const void*>(&r)); }
206
207 short_t &short_repr()
208 { return s; }
209
210 long_t &long_repr()
211 { return *static_cast<long_t*>(static_cast<void*>(&r)); }
212 };
213
214 struct members_holder
215 : public Allocator
216 {
217 members_holder()
218 : Allocator()
219 {}
220
221 template<class AllocatorConvertible>
222 explicit members_holder(BOOST_FWD_REF(AllocatorConvertible) a)
223 : Allocator(boost::forward<AllocatorConvertible>(a))
224 {}
225
226 repr_t m_repr;
227 } members_;
228
229 const Allocator &alloc() const
230 { return members_; }
231
232 Allocator &alloc()
233 { return members_; }
234
235 static const size_type InternalBufferChars = (sizeof(repr_t) - ShortDataOffset)/sizeof(value_type);
236
237 private:
238
239 static const size_type MinAllocation = InternalBufferChars*2;
240
241 protected:
242 bool is_short() const
243 { return static_cast<bool>(this->members_.m_repr.s.h.is_short != 0); }
244
245 void is_short(bool yes)
246 {
247 const bool was_short = this->is_short();
248 if(yes && !was_short){
249 allocator_traits_type::destroy
250 ( this->alloc()
251 , static_cast<long_t*>(static_cast<void*>(&this->members_.m_repr.r))
252 );
253 this->members_.m_repr.s.h.is_short = true;
254 }
255 else if(!yes && was_short){
256 allocator_traits_type::construct
257 ( this->alloc()
258 , static_cast<long_t*>(static_cast<void*>(&this->members_.m_repr.r))
259 );
260 this->members_.m_repr.s.h.is_short = false;
261 }
262 }
263
264 private:
265 void init()
266 {
267 this->members_.m_repr.s.h.is_short = 1;
268 this->members_.m_repr.s.h.length = 0;
269 }
270
271 protected:
272
273 typedef container_detail::integral_constant<unsigned, 1> allocator_v1;
274 typedef container_detail::integral_constant<unsigned, 2> allocator_v2;
275 typedef container_detail::integral_constant<unsigned,
276 boost::container::container_detail::version<Allocator>::value> alloc_version;
277
278 std::pair<pointer, bool>
279 allocation_command(allocation_type command,
280 size_type limit_size,
281 size_type preferred_size,
282 size_type &received_size, pointer reuse = 0)
283 {
284 if(this->is_short() && (command & (expand_fwd | expand_bwd)) ){
285 reuse = pointer();
286 command &= ~(expand_fwd | expand_bwd);
287 }
288 return container_detail::allocator_version_traits<Allocator>::allocation_command
289 (this->alloc(), command, limit_size, preferred_size, received_size, reuse);
290 }
291
292 size_type next_capacity(size_type additional_objects) const
293 { return get_next_capacity(allocator_traits_type::max_size(this->alloc()), this->priv_storage(), additional_objects); }
294
295 void deallocate(pointer p, size_type n)
296 {
297 if (p && (n > InternalBufferChars))
298 this->alloc().deallocate(p, n);
299 }
300
301 void construct(pointer p, const value_type &value = value_type())
302 {
303 allocator_traits_type::construct
304 ( this->alloc()
305 , container_detail::to_raw_pointer(p)
306 , value
307 );
308 }
309
310 void destroy(pointer p, size_type n)
311 {
312 value_type *raw_p = container_detail::to_raw_pointer(p);
313 for(; n--; ++raw_p){
314 allocator_traits_type::destroy( this->alloc(), raw_p);
315 }
316 }
317
318 void destroy(pointer p)
319 {
320 allocator_traits_type::destroy
321 ( this->alloc()
322 , container_detail::to_raw_pointer(p)
323 );
324 }
325
326 void allocate_initial_block(size_type n)
327 {
328 if (n <= this->max_size()) {
329 if(n > InternalBufferChars){
330 size_type new_cap = this->next_capacity(n);
331 pointer p = this->allocation_command(allocate_new, n, new_cap, new_cap).first;
332 this->is_short(false);
333 this->priv_long_addr(p);
334 this->priv_long_size(0);
335 this->priv_storage(new_cap);
336 }
337 }
338 else
339 throw_length_error();
340 }
341
342 void deallocate_block()
343 { this->deallocate(this->priv_addr(), this->priv_storage()); }
344
345 size_type max_size() const
346 { return allocator_traits_type::max_size(this->alloc()) - 1; }
347
348 // Helper functions for exception handling.
349 void throw_length_error() const
350 { throw(std::length_error("basic_string")); }
351
352 void throw_out_of_range() const
353 { throw(std::out_of_range("basic_string")); }
354
355 protected:
356 size_type priv_capacity() const
357 { return this->priv_storage() - 1; }
358
359 pointer priv_short_addr() const
360 { return pointer_traits::pointer_to(const_cast<value_type&>(this->members_.m_repr.short_repr().data[0])); }
361
362 pointer priv_long_addr() const
363 { return this->members_.m_repr.long_repr().start; }
364
365 pointer priv_addr() const
366 {
367 return this->is_short()
368 ? priv_short_addr()
369 : priv_long_addr()
370 ;
371 }
372
373 pointer priv_end_addr() const
374 {
375 return this->is_short()
376 ? this->priv_short_addr() + this->priv_short_size()
377 : this->priv_long_addr() + this->priv_long_size()
378 ;
379 }
380
381 void priv_long_addr(pointer addr)
382 { this->members_.m_repr.long_repr().start = addr; }
383
384 size_type priv_storage() const
385 { return this->is_short() ? priv_short_storage() : priv_long_storage(); }
386
387 size_type priv_short_storage() const
388 { return InternalBufferChars; }
389
390 size_type priv_long_storage() const
391 { return this->members_.m_repr.long_repr().storage; }
392
393 void priv_storage(size_type storage)
394 {
395 if(!this->is_short())
396 this->priv_long_storage(storage);
397 }
398
399 void priv_long_storage(size_type storage)
400 {
401 this->members_.m_repr.long_repr().storage = storage;
402 }
403
404 size_type priv_size() const
405 { return this->is_short() ? this->priv_short_size() : this->priv_long_size(); }
406
407 size_type priv_short_size() const
408 { return this->members_.m_repr.short_repr().h.length; }
409
410 size_type priv_long_size() const
411 { return this->members_.m_repr.long_repr().length; }
412
413 void priv_size(size_type sz)
414 {
415 if(this->is_short())
416 this->priv_short_size(sz);
417 else
418 this->priv_long_size(sz);
419 }
420
421 void priv_short_size(size_type sz)
422 {
423 this->members_.m_repr.s.h.length = (unsigned char)sz;
424 }
425
426 void priv_long_size(size_type sz)
427 {
428 this->members_.m_repr.long_repr().length = sz;
429 }
430
431 void swap_data(basic_string_base& other)
432 {
433 if(this->is_short()){
434 if(other.is_short()){
435 container_detail::do_swap(this->members_.m_repr, other.members_.m_repr);
436 }
437 else{
438 short_t short_backup(this->members_.m_repr.short_repr());
439 long_t long_backup (other.members_.m_repr.long_repr());
440 other.members_.m_repr.long_repr().~long_t();
441 ::new(&this->members_.m_repr.long_repr()) long_t;
442 this->members_.m_repr.long_repr() = long_backup;
443 other.members_.m_repr.short_repr() = short_backup;
444 }
445 }
446 else{
447 if(other.is_short()){
448 short_t short_backup(other.members_.m_repr.short_repr());
449 long_t long_backup (this->members_.m_repr.long_repr());
450 this->members_.m_repr.long_repr().~long_t();
451 ::new(&other.members_.m_repr.long_repr()) long_t;
452 other.members_.m_repr.long_repr() = long_backup;
453 this->members_.m_repr.short_repr() = short_backup;
454 }
455 else{
456 container_detail::do_swap(this->members_.m_repr.long_repr(), other.members_.m_repr.long_repr());
457 }
458 }
459 }
460};
461
462} //namespace container_detail {
463
464/// @endcond
465
466//! The basic_string class represents a Sequence of characters. It contains all the
467//! usual operations of a Sequence, and, additionally, it contains standard string
468//! operations such as search and concatenation.
469//!
470//! The basic_string class is parameterized by character type, and by that type's
471//! Character Traits.
472//!
473//! This class has performance characteristics very much like vector<>, meaning,
474//! for example, that it does not perform reference-count or copy-on-write, and that
475//! concatenation of two strings is an O(N) operation.
476//!
477//! Some of basic_string's member functions use an unusual method of specifying positions
478//! and ranges. In addition to the conventional method using iterators, many of
479//! basic_string's member functions use a single value pos of type size_type to represent a
480//! position (in which case the position is begin() + pos, and many of basic_string's
481//! member functions use two values, pos and n, to represent a range. In that case pos is
482//! the beginning of the range and n is its size. That is, the range is
483//! [begin() + pos, begin() + pos + n).
484//!
485//! Note that the C++ standard does not specify the complexity of basic_string operations.
486//! In this implementation, basic_string has performance characteristics very similar to
487//! those of vector: access to a single character is O(1), while copy and concatenation
488//! are O(N).
489//!
490//! In this implementation, begin(),
491//! end(), rbegin(), rend(), operator[], c_str(), and data() do not invalidate iterators.
492//! In this implementation, iterators are only invalidated by member functions that
493//! explicitly change the string's contents.
494#ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
495template <class CharT, class Traits = std::char_traits<CharT>, class Allocator = std::allocator<CharT> >
496#else
497template <class CharT, class Traits, class Allocator>
498#endif
499class basic_string
500 : private container_detail::basic_string_base<Allocator>
501{
502 /// @cond
503 private:
504 typedef allocator_traits<Allocator> allocator_traits_type;
505 BOOST_COPYABLE_AND_MOVABLE(basic_string)
506 typedef container_detail::basic_string_base<Allocator> base_t;
507 static const typename base_t::size_type InternalBufferChars = base_t::InternalBufferChars;
508
509 protected:
510 // Allocator helper class to use a char_traits as a function object.
511
512 template <class Tr>
513 struct Eq_traits
514 : public std::binary_function<typename Tr::char_type,
515 typename Tr::char_type,
516 bool>
517 {
518 bool operator()(const typename Tr::char_type& x,
519 const typename Tr::char_type& y) const
520 { return Tr::eq(x, y); }
521 };
522
523 template <class Tr>
524 struct Not_within_traits
525 : public std::unary_function<typename Tr::char_type, bool>
526 {
527 typedef const typename Tr::char_type* Pointer;
528 const Pointer m_first;
529 const Pointer m_last;
530
531 Not_within_traits(Pointer f, Pointer l)
532 : m_first(f), m_last(l) {}
533
534 bool operator()(const typename Tr::char_type& x) const
535 {
536 return std::find_if(m_first, m_last,
537 std::bind1st(Eq_traits<Tr>(), x)) == m_last;
538 }
539 };
540 /// @endcond
541
542 public:
543 //////////////////////////////////////////////
544 //
545 // types
546 //
547 //////////////////////////////////////////////
548 typedef Traits traits_type;
549 typedef CharT value_type;
550 typedef typename ::boost::container::allocator_traits<Allocator>::pointer pointer;
551 typedef typename ::boost::container::allocator_traits<Allocator>::const_pointer const_pointer;
552 typedef typename ::boost::container::allocator_traits<Allocator>::reference reference;
553 typedef typename ::boost::container::allocator_traits<Allocator>::const_reference const_reference;
554 typedef typename ::boost::container::allocator_traits<Allocator>::size_type size_type;
555 typedef typename ::boost::container::allocator_traits<Allocator>::difference_type difference_type;
556 typedef Allocator allocator_type;
557 typedef BOOST_CONTAINER_IMPDEF(allocator_type) stored_allocator_type;
558 typedef BOOST_CONTAINER_IMPDEF(pointer) iterator;
559 typedef BOOST_CONTAINER_IMPDEF(const_pointer) const_iterator;
560 typedef BOOST_CONTAINER_IMPDEF(std::reverse_iterator<iterator>) reverse_iterator;
561 typedef BOOST_CONTAINER_IMPDEF(std::reverse_iterator<const_iterator>) const_reverse_iterator;
562 static const size_type npos = size_type(-1);
563
564 /// @cond
565 private:
566 typedef constant_iterator<CharT, difference_type> cvalue_iterator;
567 typedef typename base_t::allocator_v1 allocator_v1;
568 typedef typename base_t::allocator_v2 allocator_v2;
569 typedef typename base_t::alloc_version alloc_version;
570 typedef ::boost::intrusive::pointer_traits<pointer> pointer_traits;
571 /// @endcond
572
573 public: // Constructor, destructor, assignment.
574 //////////////////////////////////////////////
575 //
576 // construct/copy/destroy
577 //
578 //////////////////////////////////////////////
579 /// @cond
580 struct reserve_t {};
581
582 basic_string(reserve_t, size_type n,
583 const allocator_type& a = allocator_type())
584 //Select allocator as in copy constructor as reserve_t-based constructors
585 //are two step copies optimized for capacity
586 : base_t( allocator_traits_type::select_on_container_copy_construction(a)
587 , n + 1)
588 { this->priv_terminate_string(); }
589
590 /// @endcond
591
592 //! <b>Effects</b>: Default constructs a basic_string.
593 //!
594 //! <b>Throws</b>: If allocator_type's default constructor throws.
595 basic_string()
596 : base_t()
597 { this->priv_terminate_string(); }
598
599
600 //! <b>Effects</b>: Constructs a basic_string taking the allocator as parameter.
601 //!
602 //! <b>Throws</b>: Nothing
603 explicit basic_string(const allocator_type& a) BOOST_CONTAINER_NOEXCEPT
604 : base_t(a)
605 { this->priv_terminate_string(); }
606
607 //! <b>Effects</b>: Copy constructs a basic_string.
608 //!
609 //! <b>Postcondition</b>: x == *this.
610 //!
611 //! <b>Throws</b>: If allocator_type's default constructor throws.
612 basic_string(const basic_string& s)
613 : base_t(allocator_traits_type::select_on_container_copy_construction(s.alloc()))
614 {
615 this->priv_terminate_string();
616 this->assign(s.begin(), s.end());
617 }
618
619 //! <b>Effects</b>: Move constructor. Moves s's resources to *this.
620 //!
621 //! <b>Throws</b>: Nothing.
622 //!
623 //! <b>Complexity</b>: Constant.
624 basic_string(BOOST_RV_REF(basic_string) s) BOOST_CONTAINER_NOEXCEPT
625 : base_t(boost::move((base_t&)s))
626 {}
627
628 //! <b>Effects</b>: Copy constructs a basic_string using the specified allocator.
629 //!
630 //! <b>Postcondition</b>: x == *this.
631 //!
632 //! <b>Throws</b>: If allocation throws.
633 basic_string(const basic_string& s, const allocator_type &a)
634 : base_t(a)
635 {
636 this->priv_terminate_string();
637 this->assign(s.begin(), s.end());
638 }
639
640 //! <b>Effects</b>: Move constructor using the specified allocator.
641 //! Moves s's resources to *this.
642 //!
643 //! <b>Throws</b>: If allocation throws.
644 //!
645 //! <b>Complexity</b>: Constant if a == s.get_allocator(), linear otherwise.
646 basic_string(BOOST_RV_REF(basic_string) s, const allocator_type &a)
647 : base_t(a)
648 {
649 this->priv_terminate_string();
650 if(a == this->alloc()){
651 this->swap_data(s);
652 }
653 else{
654 this->assign(s.begin(), s.end());
655 }
656 }
657
658 //! <b>Effects</b>: Constructs a basic_string taking the allocator as parameter,
659 //! and is initialized by a specific number of characters of the s string.
660 basic_string(const basic_string& s, size_type pos, size_type n = npos,
661 const allocator_type& a = allocator_type())
662 : base_t(a)
663 {
664 this->priv_terminate_string();
665 if (pos > s.size())
666 this->throw_out_of_range();
667 else
668 this->assign
669 (s.begin() + pos, s.begin() + pos + container_detail::min_value(n, s.size() - pos));
670 }
671
672 //! <b>Effects</b>: Constructs a basic_string taking the allocator as parameter,
673 //! and is initialized by a specific number of characters of the s c-string.
674 basic_string(const CharT* s, size_type n, const allocator_type& a = allocator_type())
675 : base_t(a)
676 {
677 this->priv_terminate_string();
678 this->assign(s, s + n);
679 }
680
681 //! <b>Effects</b>: Constructs a basic_string taking the allocator as parameter,
682 //! and is initialized by the null-terminated s c-string.
683 basic_string(const CharT* s, const allocator_type& a = allocator_type())
684 : base_t(a)
685 {
686 this->priv_terminate_string();
687 this->assign(s, s + Traits::length(s));
688 }
689
690 //! <b>Effects</b>: Constructs a basic_string taking the allocator as parameter,
691 //! and is initialized by n copies of c.
692 basic_string(size_type n, CharT c, const allocator_type& a = allocator_type())
693 : base_t(a)
694 {
695 this->priv_terminate_string();
696 this->assign(n, c);
697 }
698
699 //! <b>Effects</b>: Constructs a basic_string taking the allocator as parameter,
700 //! and a range of iterators.
701 template <class InputIterator>
702 basic_string(InputIterator f, InputIterator l, const allocator_type& a = allocator_type())
703 : base_t(a)
704 {
705 this->priv_terminate_string();
706 this->assign(f, l);
707 }
708
709 //! <b>Effects</b>: Destroys the basic_string. All used memory is deallocated.
710 //!
711 //! <b>Throws</b>: Nothing.
712 //!
713 //! <b>Complexity</b>: Constant.
714 ~basic_string() BOOST_CONTAINER_NOEXCEPT
715 {}
716
717 //! <b>Effects</b>: Copy constructs a string.
718 //!
719 //! <b>Postcondition</b>: x == *this.
720 //!
721 //! <b>Complexity</b>: Linear to the elements x contains.
722 basic_string& operator=(BOOST_COPY_ASSIGN_REF(basic_string) x)
723 {
724 if (&x != this){
725 allocator_type &this_alloc = this->alloc();
726 const allocator_type &x_alloc = x.alloc();
727 container_detail::bool_<allocator_traits_type::
728 propagate_on_container_copy_assignment::value> flag;
729 if(flag && this_alloc != x_alloc){
730 if(!this->is_short()){
731 this->deallocate_block();
732 this->is_short(true);
733 Traits::assign(*this->priv_addr(), CharT(0));
734 this->priv_short_size(0);
735 }
736 }
737 container_detail::assign_alloc(this->alloc(), x.alloc(), flag);
738 this->assign(x.begin(), x.end());
739 }
740 return *this;
741 }
742
743 //! <b>Effects</b>: Move constructor. Moves mx's resources to *this.
744 //!
745 //! <b>Throws</b>: If allocator_type's copy constructor throws.
746 //!
747 //! <b>Complexity</b>: Constant.
748 basic_string& operator=(BOOST_RV_REF(basic_string) x) BOOST_CONTAINER_NOEXCEPT
749 {
750 if (&x != this){
751 allocator_type &this_alloc = this->alloc();
752 allocator_type &x_alloc = x.alloc();
753 //If allocators are equal we can just swap pointers
754 if(this_alloc == x_alloc){
755 //Destroy objects but retain memory in case x reuses it in the future
756 this->clear();
757 this->swap_data(x);
758 //Move allocator if needed
759 container_detail::bool_<allocator_traits_type::
760 propagate_on_container_move_assignment::value> flag;
761 container_detail::move_alloc(this_alloc, x_alloc, flag);
762 }
763 //If unequal allocators, then do a one by one move
764 else{
765 this->assign( x.begin(), x.end());
766 }
767 }
768 return *this;
769 }
770
771 //! <b>Effects</b>: Assignment from a null-terminated c-string.
772 basic_string& operator=(const CharT* s)
773 { return this->assign(s, s + Traits::length(s)); }
774
775 //! <b>Effects</b>: Assignment from character.
776 basic_string& operator=(CharT c)
777 { return this->assign(static_cast<size_type>(1), c); }
778
779 //! <b>Effects</b>: Returns a copy of the internal allocator.
780 //!
781 //! <b>Throws</b>: If allocator's copy constructor throws.
782 //!
783 //! <b>Complexity</b>: Constant.
784 allocator_type get_allocator() const BOOST_CONTAINER_NOEXCEPT
785 { return this->alloc(); }
786
787 //! <b>Effects</b>: Returns a reference to the internal allocator.
788 //!
789 //! <b>Throws</b>: Nothing
790 //!
791 //! <b>Complexity</b>: Constant.
792 //!
793 //! <b>Note</b>: Non-standard extension.
794 stored_allocator_type &get_stored_allocator() BOOST_CONTAINER_NOEXCEPT
795 { return this->alloc(); }
796
797 //! <b>Effects</b>: Returns a reference to the internal allocator.
798 //!
799 //! <b>Throws</b>: Nothing
800 //!
801 //! <b>Complexity</b>: Constant.
802 //!
803 //! <b>Note</b>: Non-standard extension.
804 const stored_allocator_type &get_stored_allocator() const BOOST_CONTAINER_NOEXCEPT
805 { return this->alloc(); }
806
807 //////////////////////////////////////////////
808 //
809 // iterators
810 //
811 //////////////////////////////////////////////
812
813 //! <b>Effects</b>: Returns an iterator to the first element contained in the vector.
814 //!
815 //! <b>Throws</b>: Nothing.
816 //!
817 //! <b>Complexity</b>: Constant.
818 iterator begin() BOOST_CONTAINER_NOEXCEPT
819 { return this->priv_addr(); }
820
821 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the vector.
822 //!
823 //! <b>Throws</b>: Nothing.
824 //!
825 //! <b>Complexity</b>: Constant.
826 const_iterator begin() const BOOST_CONTAINER_NOEXCEPT
827 { return this->priv_addr(); }
828
829 //! <b>Effects</b>: Returns an iterator to the end of the vector.
830 //!
831 //! <b>Throws</b>: Nothing.
832 //!
833 //! <b>Complexity</b>: Constant.
834 iterator end() BOOST_CONTAINER_NOEXCEPT
835 { return this->priv_end_addr(); }
836
837 //! <b>Effects</b>: Returns a const_iterator to the end of the vector.
838 //!
839 //! <b>Throws</b>: Nothing.
840 //!
841 //! <b>Complexity</b>: Constant.
842 const_iterator end() const BOOST_CONTAINER_NOEXCEPT
843 { return this->priv_end_addr(); }
844
845 //! <b>Effects</b>: Returns a reverse_iterator pointing to the beginning
846 //! of the reversed vector.
847 //!
848 //! <b>Throws</b>: Nothing.
849 //!
850 //! <b>Complexity</b>: Constant.
851 reverse_iterator rbegin() BOOST_CONTAINER_NOEXCEPT
852 { return reverse_iterator(this->priv_end_addr()); }
853
854 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
855 //! of the reversed vector.
856 //!
857 //! <b>Throws</b>: Nothing.
858 //!
859 //! <b>Complexity</b>: Constant.
860 const_reverse_iterator rbegin() const BOOST_CONTAINER_NOEXCEPT
861 { return this->crbegin(); }
862
863 //! <b>Effects</b>: Returns a reverse_iterator pointing to the end
864 //! of the reversed vector.
865 //!
866 //! <b>Throws</b>: Nothing.
867 //!
868 //! <b>Complexity</b>: Constant.
869 reverse_iterator rend() BOOST_CONTAINER_NOEXCEPT
870 { return reverse_iterator(this->priv_addr()); }
871
872 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
873 //! of the reversed vector.
874 //!
875 //! <b>Throws</b>: Nothing.
876 //!
877 //! <b>Complexity</b>: Constant.
878 const_reverse_iterator rend() const BOOST_CONTAINER_NOEXCEPT
879 { return this->crend(); }
880
881 //! <b>Effects</b>: Returns a const_iterator to the first element contained in the vector.
882 //!
883 //! <b>Throws</b>: Nothing.
884 //!
885 //! <b>Complexity</b>: Constant.
886 const_iterator cbegin() const BOOST_CONTAINER_NOEXCEPT
887 { return this->priv_addr(); }
888
889 //! <b>Effects</b>: Returns a const_iterator to the end of the vector.
890 //!
891 //! <b>Throws</b>: Nothing.
892 //!
893 //! <b>Complexity</b>: Constant.
894 const_iterator cend() const BOOST_CONTAINER_NOEXCEPT
895 { return this->priv_end_addr(); }
896
897 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
898 //! of the reversed vector.
899 //!
900 //! <b>Throws</b>: Nothing.
901 //!
902 //! <b>Complexity</b>: Constant.
903 const_reverse_iterator crbegin() const BOOST_CONTAINER_NOEXCEPT
904 { return const_reverse_iterator(this->priv_end_addr()); }
905
906 //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
907 //! of the reversed vector.
908 //!
909 //! <b>Throws</b>: Nothing.
910 //!
911 //! <b>Complexity</b>: Constant.
912 const_reverse_iterator crend() const BOOST_CONTAINER_NOEXCEPT
913 { return const_reverse_iterator(this->priv_addr()); }
914
915 //////////////////////////////////////////////
916 //
917 // capacity
918 //
919 //////////////////////////////////////////////
920
921 //! <b>Effects</b>: Returns true if the vector contains no elements.
922 //!
923 //! <b>Throws</b>: Nothing.
924 //!
925 //! <b>Complexity</b>: Constant.
926 bool empty() const BOOST_CONTAINER_NOEXCEPT
927 { return !this->priv_size(); }
928
929 //! <b>Effects</b>: Returns the number of the elements contained in the vector.
930 //!
931 //! <b>Throws</b>: Nothing.
932 //!
933 //! <b>Complexity</b>: Constant.
934 size_type size() const BOOST_CONTAINER_NOEXCEPT
935 { return this->priv_size(); }
936
937 //! <b>Effects</b>: Returns the number of the elements contained in the vector.
938 //!
939 //! <b>Throws</b>: Nothing.
940 //!
941 //! <b>Complexity</b>: Constant.
942 size_type length() const BOOST_CONTAINER_NOEXCEPT
943 { return this->size(); }
944
945 //! <b>Effects</b>: Returns the largest possible size of the vector.
946 //!
947 //! <b>Throws</b>: Nothing.
948 //!
949 //! <b>Complexity</b>: Constant.
950 size_type max_size() const BOOST_CONTAINER_NOEXCEPT
951 { return base_t::max_size(); }
952
953 //! <b>Effects</b>: Inserts or erases elements at the end such that
954 //! the size becomes n. New elements are copy constructed from x.
955 //!
956 //! <b>Throws</b>: If memory allocation throws
957 //!
958 //! <b>Complexity</b>: Linear to the difference between size() and new_size.
959 void resize(size_type n, CharT c)
960 {
961 if (n <= this->size())
962 this->erase(this->begin() + n, this->end());
963 else
964 this->append(n - this->size(), c);
965 }
966
967 //! <b>Effects</b>: Inserts or erases elements at the end such that
968 //! the size becomes n. New elements are default constructed.
969 //!
970 //! <b>Throws</b>: If memory allocation throws
971 //!
972 //! <b>Complexity</b>: Linear to the difference between size() and new_size.
973 void resize(size_type n)
974 { resize(n, CharT()); }
975
976 //! <b>Effects</b>: Number of elements for which memory has been allocated.
977 //! capacity() is always greater than or equal to size().
978 //!
979 //! <b>Throws</b>: Nothing.
980 //!
981 //! <b>Complexity</b>: Constant.
982 size_type capacity() const BOOST_CONTAINER_NOEXCEPT
983 { return this->priv_capacity(); }
984
985 //! <b>Effects</b>: If n is less than or equal to capacity(), this call has no
986 //! effect. Otherwise, it is a request for allocation of additional memory.
987 //! If the request is successful, then capacity() is greater than or equal to
988 //! n; otherwise, capacity() is unchanged. In either case, size() is unchanged.
989 //!
990 //! <b>Throws</b>: If memory allocation allocation throws
991 void reserve(size_type res_arg)
992 {
993 if (res_arg > this->max_size()){
994 this->throw_length_error();
995 }
996
997 if (this->capacity() < res_arg){
998 size_type n = container_detail::max_value(res_arg, this->size()) + 1;
999 size_type new_cap = this->next_capacity(n);
1000 pointer new_start = this->allocation_command
1001 (allocate_new, n, new_cap, new_cap).first;
1002 size_type new_length = 0;
1003
1004 const pointer addr = this->priv_addr();
1005 new_length += priv_uninitialized_copy
1006 (addr, addr + this->priv_size(), new_start);
1007 this->priv_construct_null(new_start + new_length);
1008 this->deallocate_block();
1009 this->is_short(false);
1010 this->priv_long_addr(new_start);
1011 this->priv_long_size(new_length);
1012 this->priv_storage(new_cap);
1013 }
1014 }
1015
1016 //! <b>Effects</b>: Tries to deallocate the excess of memory created
1017 //! with previous allocations. The size of the string is unchanged
1018 //!
1019 //! <b>Throws</b>: Nothing
1020 //!
1021 //! <b>Complexity</b>: Linear to size().
1022 void shrink_to_fit()
1023 {
1024 //Check if shrinking is possible
1025 if(this->priv_storage() > InternalBufferChars){
1026 //Check if we should pass from dynamically allocated buffer
1027 //to the internal storage
1028 if(this->priv_size() < InternalBufferChars){
1029 //Dynamically allocated buffer attributes
1030 pointer long_addr = this->priv_long_addr();
1031 size_type long_storage = this->priv_long_storage();
1032 size_type long_size = this->priv_long_size();
1033 //Shrink from allocated buffer to the internal one, including trailing null
1034 Traits::copy( container_detail::to_raw_pointer(this->priv_short_addr())
1035 , container_detail::to_raw_pointer(long_addr)
1036 , long_size+1);
1037 this->is_short(true);
1038 this->alloc().deallocate(long_addr, long_storage);
1039 }
1040 else{
1041 //Shrinking in dynamic buffer
1042 this->priv_shrink_to_fit_dynamic_buffer(alloc_version());
1043 }
1044 }
1045 }
1046
1047 //////////////////////////////////////////////
1048 //
1049 // element access
1050 //
1051 //////////////////////////////////////////////
1052
1053 //! <b>Requires</b>: size() > n.
1054 //!
1055 //! <b>Effects</b>: Returns a reference to the nth element
1056 //! from the beginning of the container.
1057 //!
1058 //! <b>Throws</b>: Nothing.
1059 //!
1060 //! <b>Complexity</b>: Constant.
1061 reference operator[](size_type n) BOOST_CONTAINER_NOEXCEPT
1062 { return *(this->priv_addr() + n); }
1063
1064 //! <b>Requires</b>: size() > n.
1065 //!
1066 //! <b>Effects</b>: Returns a const reference to the nth element
1067 //! from the beginning of the container.
1068 //!
1069 //! <b>Throws</b>: Nothing.
1070 //!
1071 //! <b>Complexity</b>: Constant.
1072 const_reference operator[](size_type n) const BOOST_CONTAINER_NOEXCEPT
1073 { return *(this->priv_addr() + n); }
1074
1075 //! <b>Requires</b>: size() > n.
1076 //!
1077 //! <b>Effects</b>: Returns a reference to the nth element
1078 //! from the beginning of the container.
1079 //!
1080 //! <b>Throws</b>: std::range_error if n >= size()
1081 //!
1082 //! <b>Complexity</b>: Constant.
1083 reference at(size_type n)
1084 {
1085 if (n >= this->size())
1086 this->throw_out_of_range();
1087 return *(this->priv_addr() + n);
1088 }
1089
1090 //! <b>Requires</b>: size() > n.
1091 //!
1092 //! <b>Effects</b>: Returns a const reference to the nth element
1093 //! from the beginning of the container.
1094 //!
1095 //! <b>Throws</b>: std::range_error if n >= size()
1096 //!
1097 //! <b>Complexity</b>: Constant.
1098 const_reference at(size_type n) const {
1099 if (n >= this->size())
1100 this->throw_out_of_range();
1101 return *(this->priv_addr() + n);
1102 }
1103
1104 //////////////////////////////////////////////
1105 //
1106 // modifiers
1107 //
1108 //////////////////////////////////////////////
1109
1110 //! <b>Effects</b>: Calls append(str.data, str.size()).
1111 //!
1112 //! <b>Returns</b>: *this
1113 basic_string& operator+=(const basic_string& s)
1114 { return this->append(s); }
1115
1116 //! <b>Effects</b>: Calls append(s).
1117 //!
1118 //! <b>Returns</b>: *this
1119 basic_string& operator+=(const CharT* s)
1120 { return this->append(s); }
1121
1122 //! <b>Effects</b>: Calls append(1, c).
1123 //!
1124 //! <b>Returns</b>: *this
1125 basic_string& operator+=(CharT c)
1126 { this->push_back(c); return *this; }
1127
1128 //! <b>Effects</b>: Calls append(str.data(), str.size()).
1129 //!
1130 //! <b>Returns</b>: *this
1131 basic_string& append(const basic_string& s)
1132 { return this->append(s.begin(), s.end()); }
1133
1134 //! <b>Requires</b>: pos <= str.size()
1135 //!
1136 //! <b>Effects</b>: Determines the effective length rlen of the string to append
1137 //! as the smaller of n and str.size() - pos and calls append(str.data() + pos, rlen).
1138 //!
1139 //! <b>Throws</b>: If memory allocation throws and out_of_range if pos > str.size()
1140 //!
1141 //! <b>Returns</b>: *this
1142 basic_string& append(const basic_string& s, size_type pos, size_type n)
1143 {
1144 if (pos > s.size())
1145 this->throw_out_of_range();
1146 return this->append(s.begin() + pos,
1147 s.begin() + pos + container_detail::min_value(n, s.size() - pos));
1148 }
1149
1150 //! <b>Requires</b>: s points to an array of at least n elements of CharT.
1151 //!
1152 //! <b>Effects</b>: The function replaces the string controlled by *this with
1153 //! a string of length size() + n whose irst size() elements are a copy of the
1154 //! original string controlled by *this and whose remaining
1155 //! elements are a copy of the initial n elements of s.
1156 //!
1157 //! <b>Throws</b>: If memory allocation throws length_error if size() + n > max_size().
1158 //!
1159 //! <b>Returns</b>: *this
1160 basic_string& append(const CharT* s, size_type n)
1161 { return this->append(s, s + n); }
1162
1163 //! <b>Requires</b>: s points to an array of at least traits::length(s) + 1 elements of CharT.
1164 //!
1165 //! <b>Effects</b>: Calls append(s, traits::length(s)).
1166 //!
1167 //! <b>Returns</b>: *this
1168 basic_string& append(const CharT* s)
1169 { return this->append(s, s + Traits::length(s)); }
1170
1171 //! <b>Effects</b>: Equivalent to append(basic_string(n, c)).
1172 //!
1173 //! <b>Returns</b>: *this
1174 basic_string& append(size_type n, CharT c)
1175 { return this->append(cvalue_iterator(c, n), cvalue_iterator()); }
1176
1177 //! <b>Requires</b>: [first,last) is a valid range.
1178 //!
1179 //! <b>Effects</b>: Equivalent to append(basic_string(first, last)).
1180 //!
1181 //! <b>Returns</b>: *this
1182 template <class InputIter>
1183 basic_string& append(InputIter first, InputIter last)
1184 { this->insert(this->end(), first, last); return *this; }
1185
1186 //! <b>Effects</b>: Equivalent to append(static_cast<size_type>(1), c).
1187 void push_back(CharT c)
1188 {
1189 const size_type old_size = this->priv_size();
1190 if (old_size < this->capacity()){
1191 const pointer addr = this->priv_addr();
1192 this->priv_construct_null(addr + old_size + 1);
1193 Traits::assign(addr[old_size], c);
1194 this->priv_size(old_size+1);
1195 }
1196 else{
1197 //No enough memory, insert a new object at the end
1198 this->append(size_type(1), c);
1199 }
1200 }
1201
1202 //! <b>Effects</b>: Equivalent to assign(str, 0, npos).
1203 //!
1204 //! <b>Returns</b>: *this
1205 basic_string& assign(const basic_string& s)
1206 { return this->operator=(s); }
1207
1208 //! <b>Effects</b>: The function replaces the string controlled by *this
1209 //! with a string of length str.size() whose elements are a copy of the string
1210 //! controlled by str. Leaves str in a valid but unspecified state.
1211 //!
1212 //! <b>Throws</b>: Nothing
1213 //!
1214 //! <b>Returns</b>: *this
1215 basic_string& assign(BOOST_RV_REF(basic_string) ms) BOOST_CONTAINER_NOEXCEPT
1216 { return this->swap_data(ms), *this; }
1217
1218 //! <b>Requires</b>: pos <= str.size()
1219 //!
1220 //! <b>Effects</b>: Determines the effective length rlen of the string to assign as
1221 //! the smaller of n and str.size() - pos and calls assign(str.data() + pos rlen).
1222 //!
1223 //! <b>Throws</b>: If memory allocation throws or out_of_range if pos > str.size().
1224 //!
1225 //! <b>Returns</b>: *this
1226 basic_string& assign(const basic_string& s, size_type pos, size_type n)
1227 {
1228 if (pos > s.size())
1229 this->throw_out_of_range();
1230 return this->assign(s.begin() + pos,
1231 s.begin() + pos + container_detail::min_value(n, s.size() - pos));
1232 }
1233
1234 //! <b>Requires</b>: s points to an array of at least n elements of CharT.
1235 //!
1236 //! <b>Effects</b>: Replaces the string controlled by *this with a string of
1237 //! length n whose elements are a copy of those pointed to by s.
1238 //!
1239 //! <b>Throws</b>: If memory allocation throws or length_error if n > max_size().
1240 //!
1241 //! <b>Returns</b>: *this
1242 basic_string& assign(const CharT* s, size_type n)
1243 { return this->assign(s, s + n); }
1244
1245 //! <b>Requires</b>: s points to an array of at least traits::length(s) + 1 elements of CharT.
1246 //!
1247 //! <b>Effects</b>: Calls assign(s, traits::length(s)).
1248 //!
1249 //! <b>Returns</b>: *this
1250 basic_string& assign(const CharT* s)
1251 { return this->assign(s, s + Traits::length(s)); }
1252
1253 //! <b>Effects</b>: Equivalent to assign(basic_string(n, c)).
1254 //!
1255 //! <b>Returns</b>: *this
1256 basic_string& assign(size_type n, CharT c)
1257 { return this->assign(cvalue_iterator(c, n), cvalue_iterator()); }
1258
1259 //! <b>Effects</b>: Equivalent to assign(basic_string(first, last)).
1260 //!
1261 //! <b>Returns</b>: *this
1262 template <class InputIter>
1263 basic_string& assign(InputIter first, InputIter last
1264 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1265 , typename container_detail::enable_if_c
1266 < !container_detail::is_convertible<InputIter, size_type>::value
1267 >::type * = 0
1268 #endif
1269 )
1270 {
1271 size_type cur = 0;
1272 const pointer addr = this->priv_addr();
1273 CharT *ptr = container_detail::to_raw_pointer(addr);
1274 const size_type old_size = this->priv_size();
1275 while (first != last && cur != old_size) {
1276 Traits::assign(*ptr, *first);
1277 ++first;
1278 ++cur;
1279 ++ptr;
1280 }
1281 if (first == last)
1282 this->erase(addr + cur, addr + old_size);
1283 else
1284 this->append(first, last);
1285 return *this;
1286 }
1287
1288 //! <b>Requires</b>: pos <= size().
1289 //!
1290 //! <b>Effects</b>: Calls insert(pos, str.data(), str.size()).
1291 //!
1292 //! <b>Throws</b>: If memory allocation throws or out_of_range if pos > size().
1293 //!
1294 //! <b>Returns</b>: *this
1295 basic_string& insert(size_type pos, const basic_string& s)
1296 {
1297 const size_type sz = this->size();
1298 if (pos > sz)
1299 this->throw_out_of_range();
1300 if (sz > this->max_size() - s.size())
1301 this->throw_length_error();
1302 this->insert(this->priv_addr() + pos, s.begin(), s.end());
1303 return *this;
1304 }
1305
1306 //! <b>Requires</b>: pos1 <= size() and pos2 <= str.size()
1307 //!
1308 //! <b>Effects</b>: Determines the effective length rlen of the string to insert as
1309 //! the smaller of n and str.size() - pos2 and calls insert(pos1, str.data() + pos2, rlen).
1310 //!
1311 //! <b>Throws</b>: If memory allocation throws or out_of_range if pos1 > size() or pos2 > str.size().
1312 //!
1313 //! <b>Returns</b>: *this
1314 basic_string& insert(size_type pos1, const basic_string& s, size_type pos2, size_type n)
1315 {
1316 const size_type sz = this->size();
1317 const size_type str_size = s.size();
1318 if (pos1 > sz || pos2 > str_size)
1319 this->throw_out_of_range();
1320 size_type len = container_detail::min_value(n, str_size - pos2);
1321 if (sz > this->max_size() - len)
1322 this->throw_length_error();
1323 const CharT *beg_ptr = container_detail::to_raw_pointer(s.begin()) + pos2;
1324 const CharT *end_ptr = beg_ptr + len;
1325 this->insert(this->priv_addr() + pos1, beg_ptr, end_ptr);
1326 return *this;
1327 }
1328
1329 //! <b>Requires</b>: s points to an array of at least n elements of CharT and pos <= size().
1330 //!
1331 //! <b>Effects</b>: Replaces the string controlled by *this with a string of length size() + n
1332 //! whose first pos elements are a copy of the initial elements of the original string
1333 //! controlled by *this and whose next n elements are a copy of the elements in s and whose
1334 //! remaining elements are a copy of the remaining elements of the original string controlled by *this.
1335 //!
1336 //! <b>Throws</b>: If memory allocation throws, out_of_range if pos > size() or
1337 //! length_error if size() + n > max_size().
1338 //!
1339 //! <b>Returns</b>: *this
1340 basic_string& insert(size_type pos, const CharT* s, size_type n)
1341 {
1342 if (pos > this->size())
1343 this->throw_out_of_range();
1344 if (this->size() > this->max_size() - n)
1345 this->throw_length_error();
1346 this->insert(this->priv_addr() + pos, s, s + n);
1347 return *this;
1348 }
1349
1350 //! <b>Requires</b>: pos <= size() and s points to an array of at least traits::length(s) + 1 elements of CharT
1351 //!
1352 //! <b>Effects</b>: Calls insert(pos, s, traits::length(s)).
1353 //!
1354 //! <b>Throws</b>: If memory allocation throws, out_of_range if pos > size()
1355 //! length_error if size() > max_size() - Traits::length(s)
1356 //!
1357 //! <b>Returns</b>: *this
1358 basic_string& insert(size_type pos, const CharT* s)
1359 {
1360 if (pos > this->size())
1361 this->throw_out_of_range();
1362 size_type len = Traits::length(s);
1363 if (this->size() > this->max_size() - len)
1364 this->throw_length_error();
1365 this->insert(this->priv_addr() + pos, s, s + len);
1366 return *this;
1367 }
1368
1369 //! <b>Effects</b>: Equivalent to insert(pos, basic_string(n, c)).
1370 //!
1371 //! <b>Throws</b>: If memory allocation throws, out_of_range if pos > size()
1372 //! length_error if size() > max_size() - n
1373 //!
1374 //! <b>Returns</b>: *this
1375 basic_string& insert(size_type pos, size_type n, CharT c)
1376 {
1377 if (pos > this->size())
1378 this->throw_out_of_range();
1379 if (this->size() > this->max_size() - n)
1380 this->throw_length_error();
1381 this->insert(const_iterator(this->priv_addr() + pos), n, c);
1382 return *this;
1383 }
1384
1385 //! <b>Requires</b>: p is a valid iterator on *this.
1386 //!
1387 //! <b>Effects</b>: inserts a copy of c before the character referred to by p.
1388 //!
1389 //! <b>Returns</b>: An iterator which refers to the copy of the inserted character.
1390 iterator insert(const_iterator p, CharT c)
1391 {
1392 size_type new_offset = p - this->priv_addr();
1393 this->insert(p, cvalue_iterator(c, 1), cvalue_iterator());
1394 return this->priv_addr() + new_offset;
1395 }
1396
1397
1398 //! <b>Requires</b>: p is a valid iterator on *this.
1399 //!
1400 //! <b>Effects</b>: Inserts n copies of c before the character referred to by p.
1401 //!
1402 //! <b>Returns</b>: an iterator to the first inserted element or p if n is 0.
1403 iterator insert(const_iterator p, size_type n, CharT c)
1404 { return this->insert(p, cvalue_iterator(c, n), cvalue_iterator()); }
1405
1406 //! <b>Requires</b>: p is a valid iterator on *this. [first,last) is a valid range.
1407 //!
1408 //! <b>Effects</b>: Equivalent to insert(p - begin(), basic_string(first, last)).
1409 //!
1410 //! <b>Returns</b>: an iterator to the first inserted element or p if first == last.
1411 template <class InputIter>
1412 iterator insert(const_iterator p, InputIter first, InputIter last
1413 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1414 , typename container_detail::enable_if_c
1415 < !container_detail::is_convertible<InputIter, size_type>::value
1416 && container_detail::is_input_iterator<InputIter>::value
1417 >::type * = 0
1418 #endif
1419 )
1420 {
1421 const size_type n_pos = p - this->cbegin();
1422 for ( ; first != last; ++first, ++p) {
1423 p = this->insert(p, *first);
1424 }
1425 return this->begin() + n_pos;
1426 }
1427
1428 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1429 template <class ForwardIter>
1430 iterator insert(const_iterator p, ForwardIter first, ForwardIter last
1431 , typename container_detail::enable_if_c
1432 < !container_detail::is_convertible<ForwardIter, size_type>::value
1433 && !container_detail::is_input_iterator<ForwardIter>::value
1434 >::type * = 0
1435 )
1436 {
1437 const size_type n_pos = p - this->cbegin();
1438 if (first != last) {
1439 const size_type n = std::distance(first, last);
1440 const size_type old_size = this->priv_size();
1441 const size_type remaining = this->capacity() - old_size;
1442 const pointer old_start = this->priv_addr();
1443 bool enough_capacity = false;
1444 std::pair<pointer, bool> allocation_ret;
1445 size_type new_cap = 0;
1446
1447 //Check if we have enough capacity
1448 if (remaining >= n){
1449 enough_capacity = true;
1450 }
1451 else {
1452 //Otherwise expand current buffer or allocate new storage
1453 new_cap = this->next_capacity(n);
1454 allocation_ret = this->allocation_command
1455 (allocate_new | expand_fwd | expand_bwd, old_size + n + 1,
1456 new_cap, new_cap, old_start);
1457
1458 //Check forward expansion
1459 if(old_start == allocation_ret.first){
1460 enough_capacity = true;
1461 this->priv_storage(new_cap);
1462 }
1463 }
1464
1465 //Reuse same buffer
1466 if(enough_capacity){
1467 const size_type elems_after = old_size - (p - old_start);
1468 const size_type old_length = old_size;
1469 if (elems_after >= n) {
1470 const pointer pointer_past_last = old_start + old_size + 1;
1471 priv_uninitialized_copy(old_start + (old_size - n + 1),
1472 pointer_past_last, pointer_past_last);
1473
1474 this->priv_size(old_size+n);
1475 Traits::move(const_cast<CharT*>(container_detail::to_raw_pointer(p + n)),
1476 container_detail::to_raw_pointer(p),
1477 (elems_after - n) + 1);
1478 this->priv_copy(first, last, const_cast<CharT*>(container_detail::to_raw_pointer(p)));
1479 }
1480 else {
1481 ForwardIter mid = first;
1482 std::advance(mid, elems_after + 1);
1483
1484 priv_uninitialized_copy(mid, last, old_start + old_size + 1);
1485 const size_type newer_size = old_size + (n - elems_after);
1486 this->priv_size(newer_size);
1487 priv_uninitialized_copy
1488 (p, const_iterator(old_start + old_length + 1),
1489 old_start + newer_size);
1490 this->priv_size(newer_size + elems_after);
1491 this->priv_copy(first, mid, const_cast<CharT*>(container_detail::to_raw_pointer(p)));
1492 }
1493 }
1494 else{
1495 pointer new_start = allocation_ret.first;
1496 if(!allocation_ret.second){
1497 //Copy data to new buffer
1498 size_type new_length = 0;
1499 //This can't throw, since characters are POD
1500 new_length += priv_uninitialized_copy
1501 (const_iterator(old_start), p, new_start);
1502 new_length += priv_uninitialized_copy
1503 (first, last, new_start + new_length);
1504 new_length += priv_uninitialized_copy
1505 (p, const_iterator(old_start + old_size),
1506 new_start + new_length);
1507 this->priv_construct_null(new_start + new_length);
1508
1509 this->deallocate_block();
1510 this->is_short(false);
1511 this->priv_long_addr(new_start);
1512 this->priv_long_size(new_length);
1513 this->priv_long_storage(new_cap);
1514 }
1515 else{
1516 //value_type is POD, so backwards expansion is much easier
1517 //than with vector<T>
1518 value_type * const oldbuf = container_detail::to_raw_pointer(old_start);
1519 value_type * const newbuf = container_detail::to_raw_pointer(new_start);
1520 const value_type *const pos = container_detail::to_raw_pointer(p);
1521 const size_type before = pos - oldbuf;
1522
1523 //First move old data
1524 Traits::move(newbuf, oldbuf, before);
1525 Traits::move(newbuf + before + n, pos, old_size - before);
1526 //Now initialize the new data
1527 priv_uninitialized_copy(first, last, new_start + before);
1528 this->priv_construct_null(new_start + (old_size + n));
1529 this->is_short(false);
1530 this->priv_long_addr(new_start);
1531 this->priv_long_size(old_size + n);
1532 this->priv_long_storage(new_cap);
1533 }
1534 }
1535 }
1536 return this->begin() + n_pos;
1537 }
1538 #endif
1539
1540 //! <b>Requires</b>: pos <= size()
1541 //!
1542 //! <b>Effects</b>: Determines the effective length xlen of the string to be removed as the smaller of n and size() - pos.
1543 //! The function then replaces the string controlled by *this with a string of length size() - xlen
1544 //! whose first pos elements are a copy of the initial elements of the original string controlled by *this,
1545 //! and whose remaining elements are a copy of the elements of the original string controlled by *this
1546 //! beginning at position pos + xlen.
1547 //!
1548 //! <b>Throws</b>: out_of_range if pos > size().
1549 //!
1550 //! <b>Returns</b>: *this
1551 basic_string& erase(size_type pos = 0, size_type n = npos)
1552 {
1553 if (pos > this->size())
1554 this->throw_out_of_range();
1555 const pointer addr = this->priv_addr();
1556 erase(addr + pos, addr + pos + container_detail::min_value(n, this->size() - pos));
1557 return *this;
1558 }
1559
1560 //! <b>Effects</b>: Removes the character referred to by p.
1561 //!
1562 //! <b>Throws</b>: Nothing
1563 //!
1564 //! <b>Returns</b>: An iterator which points to the element immediately following p prior to the element being
1565 //! erased. If no such element exists, end() is returned.
1566 iterator erase(const_iterator p) BOOST_CONTAINER_NOEXCEPT
1567 {
1568 // The move includes the terminating null.
1569 CharT * const ptr = const_cast<CharT*>(container_detail::to_raw_pointer(p));
1570 const size_type old_size = this->priv_size();
1571 Traits::move(ptr,
1572 container_detail::to_raw_pointer(p + 1),
1573 old_size - (p - this->priv_addr()));
1574 this->priv_size(old_size-1);
1575 return iterator(ptr);
1576 }
1577
1578 //! <b>Requires</b>: first and last are valid iterators on *this, defining a range [first,last).
1579 //!
1580 //! <b>Effects</b>: Removes the characters in the range [first,last).
1581 //!
1582 //! <b>Throws</b>: Nothing
1583 //!
1584 //! <b>Returns</b>: An iterator which points to the element pointed to by last prior to
1585 //! the other elements being erased. If no such element exists, end() is returned.
1586 iterator erase(const_iterator first, const_iterator last) BOOST_CONTAINER_NOEXCEPT
1587 {
1588 CharT * f = const_cast<CharT*>(container_detail::to_raw_pointer(first));
1589 if (first != last) { // The move includes the terminating null.
1590 const size_type num_erased = last - first;
1591 const size_type old_size = this->priv_size();
1592 Traits::move(f,
1593 container_detail::to_raw_pointer(last),
1594 (old_size + 1)-(last - this->priv_addr()));
1595 const size_type new_length = old_size - num_erased;
1596 this->priv_size(new_length);
1597 }
1598 return iterator(f);
1599 }
1600
1601 //! <b>Requires</b>: !empty()
1602 //!
1603 //! <b>Throws</b>: Nothing
1604 //!
1605 //! <b>Effects</b>: Equivalent to erase(size() - 1, 1).
1606 void pop_back() BOOST_CONTAINER_NOEXCEPT
1607 {
1608 const size_type old_size = this->priv_size();
1609 Traits::assign(this->priv_addr()[old_size-1], CharT(0));
1610 this->priv_size(old_size-1);;
1611 }
1612
1613 //! <b>Effects</b>: Erases all the elements of the vector.
1614 //!
1615 //! <b>Throws</b>: Nothing.
1616 //!
1617 //! <b>Complexity</b>: Linear to the number of elements in the vector.
1618 void clear() BOOST_CONTAINER_NOEXCEPT
1619 {
1620 if (!this->empty()) {
1621 Traits::assign(*this->priv_addr(), CharT(0));
1622 this->priv_size(0);
1623 }
1624 }
1625
1626 //! <b>Requires</b>: pos1 <= size().
1627 //!
1628 //! <b>Effects</b>: Calls replace(pos1, n1, str.data(), str.size()).
1629 //!
1630 //! <b>Throws</b>: if memory allocation throws or out_of_range if pos1 > size().
1631 //!
1632 //! <b>Returns</b>: *this
1633 basic_string& replace(size_type pos1, size_type n1, const basic_string& str)
1634 {
1635 if (pos1 > this->size())
1636 this->throw_out_of_range();
1637 const size_type len = container_detail::min_value(n1, this->size() - pos1);
1638 if (this->size() - len >= this->max_size() - str.size())
1639 this->throw_length_error();
1640 const pointer addr = this->priv_addr();
1641 return this->replace( const_iterator(addr + pos1)
1642 , const_iterator(addr + pos1 + len)
1643 , str.begin(), str.end());
1644 }
1645
1646 //! <b>Requires</b>: pos1 <= size() and pos2 <= str.size().
1647 //!
1648 //! <b>Effects</b>: Determines the effective length rlen of the string to be
1649 //! inserted as the smaller of n2 and str.size() - pos2 and calls
1650 //! replace(pos1, n1, str.data() + pos2, rlen).
1651 //!
1652 //! <b>Throws</b>: if memory allocation throws, out_of_range if pos1 > size() or pos2 > str.size().
1653 //!
1654 //! <b>Returns</b>: *this
1655 basic_string& replace(size_type pos1, size_type n1,
1656 const basic_string& str, size_type pos2, size_type n2)
1657 {
1658 if (pos1 > this->size() || pos2 > str.size())
1659 this->throw_out_of_range();
1660 const size_type len1 = container_detail::min_value(n1, this->size() - pos1);
1661 const size_type len2 = container_detail::min_value(n2, str.size() - pos2);
1662 if (this->size() - len1 >= this->max_size() - len2)
1663 this->throw_length_error();
1664 const pointer addr = this->priv_addr();
1665 const pointer straddr = str.priv_addr();
1666 return this->replace(addr + pos1, addr + pos1 + len1,
1667 straddr + pos2, straddr + pos2 + len2);
1668 }
1669
1670 //! <b>Requires</b>: pos1 <= size() and s points to an array of at least n2 elements of CharT.
1671 //!
1672 //! <b>Effects</b>: Determines the effective length xlen of the string to be removed as the
1673 //! smaller of n1 and size() - pos1. If size() - xlen >= max_size() - n2 throws length_error.
1674 //! Otherwise, the function replaces the string controlled by *this with a string of
1675 //! length size() - xlen + n2 whose first pos1 elements are a copy of the initial elements
1676 //! of the original string controlled by *this, whose next n2 elements are a copy of the
1677 //! initial n2 elements of s, and whose remaining elements are a copy of the elements of
1678 //! the original string controlled by *this beginning at position pos + xlen.
1679 //!
1680 //! <b>Throws</b>: if memory allocation throws, out_of_range if pos1 > size() or length_error
1681 //! if the length of the resulting string would exceed max_size()
1682 //!
1683 //! <b>Returns</b>: *this
1684 basic_string& replace(size_type pos1, size_type n1, const CharT* s, size_type n2)
1685 {
1686 if (pos1 > this->size())
1687 this->throw_out_of_range();
1688 const size_type len = container_detail::min_value(n1, this->size() - pos1);
1689 if (n2 > this->max_size() || size() - len >= this->max_size() - n2)
1690 this->throw_length_error();
1691 const pointer addr = this->priv_addr();
1692 return this->replace(addr + pos1, addr + pos1 + len, s, s + n2);
1693 }
1694
1695 //! <b>Requires</b>: pos1 <= size() and s points to an array of at least n2 elements of CharT.
1696 //!
1697 //! <b>Effects</b>: Determines the effective length xlen of the string to be removed as the smaller
1698 //! of n1 and size() - pos1. If size() - xlen >= max_size() - n2 throws length_error. Otherwise,
1699 //! the function replaces the string controlled by *this with a string of length size() - xlen + n2
1700 //! whose first pos1 elements are a copy of the initial elements of the original string controlled
1701 //! by *this, whose next n2 elements are a copy of the initial n2 elements of s, and whose
1702 //! remaining elements are a copy of the elements of the original string controlled by *this
1703 //! beginning at position pos + xlen.
1704 //!
1705 //! <b>Throws</b>: if memory allocation throws, out_of_range if pos1 > size() or length_error
1706 //! if the length of the resulting string would exceed max_size()
1707 //!
1708 //! <b>Returns</b>: *this
1709 basic_string& replace(size_type pos, size_type n1, const CharT* s)
1710 {
1711 if (pos > this->size())
1712 this->throw_out_of_range();
1713 const size_type len = container_detail::min_value(n1, this->size() - pos);
1714 const size_type n2 = Traits::length(s);
1715 if (n2 > this->max_size() || this->size() - len >= this->max_size() - n2)
1716 this->throw_length_error();
1717 const pointer addr = this->priv_addr();
1718 return this->replace(addr + pos, addr + pos + len,
1719 s, s + Traits::length(s));
1720 }
1721
1722 //! <b>Requires</b>: pos1 <= size().
1723 //!
1724 //! <b>Effects</b>: Equivalent to replace(pos1, n1, basic_string(n2, c)).
1725 //!
1726 //! <b>Throws</b>: if memory allocation throws, out_of_range if pos1 > size() or length_error
1727 //! if the length of the resulting string would exceed max_size()
1728 //!
1729 //! <b>Returns</b>: *this
1730 basic_string& replace(size_type pos1, size_type n1, size_type n2, CharT c)
1731 {
1732 if (pos1 > this->size())
1733 this->throw_out_of_range();
1734 const size_type len = container_detail::min_value(n1, this->size() - pos1);
1735 if (n2 > this->max_size() || this->size() - len >= this->max_size() - n2)
1736 this->throw_length_error();
1737 const pointer addr = this->priv_addr();
1738 return this->replace(addr + pos1, addr + pos1 + len, n2, c);
1739 }
1740
1741 //! <b>Requires</b>: [begin(),i1) and [i1,i2) are valid ranges.
1742 //!
1743 //! <b>Effects</b>: Calls replace(i1 - begin(), i2 - i1, str).
1744 //!
1745 //! <b>Throws</b>: if memory allocation throws
1746 //!
1747 //! <b>Returns</b>: *this
1748 basic_string& replace(const_iterator i1, const_iterator i2, const basic_string& str)
1749 { return this->replace(i1, i2, str.begin(), str.end()); }
1750
1751 //! <b>Requires</b>: [begin(),i1) and [i1,i2) are valid ranges and
1752 //! s points to an array of at least n elements
1753 //!
1754 //! <b>Effects</b>: Calls replace(i1 - begin(), i2 - i1, s, n).
1755 //!
1756 //! <b>Throws</b>: if memory allocation throws
1757 //!
1758 //! <b>Returns</b>: *this
1759 basic_string& replace(const_iterator i1, const_iterator i2, const CharT* s, size_type n)
1760 { return this->replace(i1, i2, s, s + n); }
1761
1762 //! <b>Requires</b>: [begin(),i1) and [i1,i2) are valid ranges and s points to an
1763 //! array of at least traits::length(s) + 1 elements of CharT.
1764 //!
1765 //! <b>Effects</b>: Calls replace(i1 - begin(), i2 - i1, s, traits::length(s)).
1766 //!
1767 //! <b>Throws</b>: if memory allocation throws
1768 //!
1769 //! <b>Returns</b>: *this
1770 basic_string& replace(const_iterator i1, const_iterator i2, const CharT* s)
1771 { return this->replace(i1, i2, s, s + Traits::length(s)); }
1772
1773 //! <b>Requires</b>: [begin(),i1) and [i1,i2) are valid ranges.
1774 //!
1775 //! <b>Effects</b>: Calls replace(i1 - begin(), i2 - i1, basic_string(n, c)).
1776 //!
1777 //! <b>Throws</b>: if memory allocation throws
1778 //!
1779 //! <b>Returns</b>: *this
1780 basic_string& replace(const_iterator i1, const_iterator i2, size_type n, CharT c)
1781 {
1782 const size_type len = static_cast<size_type>(i2 - i1);
1783 if (len >= n) {
1784 Traits::assign(const_cast<CharT*>(container_detail::to_raw_pointer(i1)), n, c);
1785 erase(i1 + n, i2);
1786 }
1787 else {
1788 Traits::assign(const_cast<CharT*>(container_detail::to_raw_pointer(i1)), len, c);
1789 insert(i2, n - len, c);
1790 }
1791 return *this;
1792 }
1793
1794 //! <b>Requires</b>: [begin(),i1), [i1,i2) and [j1,j2) are valid ranges.
1795 //!
1796 //! <b>Effects</b>: Calls replace(i1 - begin(), i2 - i1, basic_string(j1, j2)).
1797 //!
1798 //! <b>Throws</b>: if memory allocation throws
1799 //!
1800 //! <b>Returns</b>: *this
1801 template <class InputIter>
1802 basic_string& replace(const_iterator i1, const_iterator i2, InputIter j1, InputIter j2
1803 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1804 , typename container_detail::enable_if_c
1805 < !container_detail::is_convertible<InputIter, size_type>::value
1806 && container_detail::is_input_iterator<InputIter>::value
1807 >::type * = 0
1808 #endif
1809 )
1810 {
1811 for ( ; i1 != i2 && j1 != j2; ++i1, ++j1){
1812 Traits::assign(*const_cast<CharT*>(container_detail::to_raw_pointer(i1)), *j1);
1813 }
1814
1815 if (j1 == j2)
1816 this->erase(i1, i2);
1817 else
1818 this->insert(i2, j1, j2);
1819 return *this;
1820 }
1821
1822 #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
1823 template <class ForwardIter>
1824 basic_string& replace(const_iterator i1, const_iterator i2, ForwardIter j1, ForwardIter j2
1825 , typename container_detail::enable_if_c
1826 < !container_detail::is_convertible<ForwardIter, size_type>::value
1827 && !container_detail::is_input_iterator<ForwardIter>::value
1828 >::type * = 0
1829 )
1830 {
1831 difference_type n = std::distance(j1, j2);
1832 const difference_type len = i2 - i1;
1833 if (len >= n) {
1834 this->priv_copy(j1, j2, const_cast<CharT*>(container_detail::to_raw_pointer(i1)));
1835 this->erase(i1 + n, i2);
1836 }
1837 else {
1838 ForwardIter m = j1;
1839 std::advance(m, len);
1840 this->priv_copy(j1, m, const_cast<CharT*>(container_detail::to_raw_pointer(i1)));
1841 this->insert(i2, m, j2);
1842 }
1843 return *this;
1844 }
1845 #endif
1846
1847 //! <b>Requires</b>: pos <= size()
1848 //!
1849 //! <b>Effects</b>: Determines the effective length rlen of the string to copy as the
1850 //! smaller of n and size() - pos. s shall designate an array of at least rlen elements.
1851 //! The function then replaces the string designated by s with a string of length rlen
1852 //! whose elements are a copy of the string controlled by *this beginning at position pos.
1853 //! The function does not append a null object to the string designated by s.
1854 //!
1855 //! <b>Throws</b>: if memory allocation throws, out_of_range if pos > size().
1856 //!
1857 //! <b>Returns</b>: rlen
1858 size_type copy(CharT* s, size_type n, size_type pos = 0) const
1859 {
1860 if (pos > this->size())
1861 this->throw_out_of_range();
1862 const size_type len = container_detail::min_value(n, this->size() - pos);
1863 Traits::copy(s, container_detail::to_raw_pointer(this->priv_addr() + pos), len);
1864 return len;
1865 }
1866
1867 //! <b>Effects</b>: *this contains the same sequence of characters that was in s,
1868 //! s contains the same sequence of characters that was in *this.
1869 //!
1870 //! <b>Throws</b>: Nothing
1871 void swap(basic_string& x)
1872 {
1873 this->base_t::swap_data(x);
1874 container_detail::bool_<allocator_traits_type::propagate_on_container_swap::value> flag;
1875 container_detail::swap_alloc(this->alloc(), x.alloc(), flag);
1876 }
1877
1878 //////////////////////////////////////////////
1879 //
1880 // data access
1881 //
1882 //////////////////////////////////////////////
1883
1884 //! <b>Requires</b>: The program shall not alter any of the values stored in the character array.
1885 //!
1886 //! <b>Returns</b>: Allocator pointer p such that p + i == &operator[](i) for each i in [0,size()].
1887 //!
1888 //! <b>Complexity</b>: constant time.
1889 const CharT* c_str() const BOOST_CONTAINER_NOEXCEPT
1890 { return container_detail::to_raw_pointer(this->priv_addr()); }
1891
1892 //! <b>Requires</b>: The program shall not alter any of the values stored in the character array.
1893 //!
1894 //! <b>Returns</b>: Allocator pointer p such that p + i == &operator[](i) for each i in [0,size()].
1895 //!
1896 //! <b>Complexity</b>: constant time.
1897 const CharT* data() const BOOST_CONTAINER_NOEXCEPT
1898 { return container_detail::to_raw_pointer(this->priv_addr()); }
1899
1900 //////////////////////////////////////////////
1901 //
1902 // string operations
1903 //
1904 //////////////////////////////////////////////
1905
1906 //! <b>Effects</b>: Determines the lowest position xpos, if possible, such that both
1907 //! of the following conditions obtain: 19 pos <= xpos and xpos + str.size() <= size();
1908 //! 2) traits::eq(at(xpos+I), str.at(I)) for all elements I of the string controlled by str.
1909 //!
1910 //! <b>Throws</b>: Nothing
1911 //!
1912 //! <b>Returns</b>: xpos if the function can determine such a value for xpos. Otherwise, returns npos.
1913 size_type find(const basic_string& s, size_type pos = 0) const
1914 { return find(s.c_str(), pos, s.size()); }
1915
1916 //! <b>Requires</b>: s points to an array of at least n elements of CharT.
1917 //!
1918 //! <b>Throws</b>: Nothing
1919 //!
1920 //! <b>Returns</b>: find(basic_string<CharT,traits,Allocator>(s,n),pos).
1921 size_type find(const CharT* s, size_type pos, size_type n) const
1922 {
1923 if (pos + n > this->size())
1924 return npos;
1925 else {
1926 const pointer addr = this->priv_addr();
1927 pointer finish = addr + this->priv_size();
1928 const const_iterator result =
1929 std::search(container_detail::to_raw_pointer(addr + pos),
1930 container_detail::to_raw_pointer(finish),
1931 s, s + n, Eq_traits<Traits>());
1932 return result != finish ? result - begin() : npos;
1933 }
1934 }
1935
1936 //! <b>Requires</b>: s points to an array of at least traits::length(s) + 1 elements of CharT.
1937 //!
1938 //! <b>Throws</b>: Nothing
1939 //!
1940 //! <b>Returns</b>: find(basic_string(s), pos).
1941 size_type find(const CharT* s, size_type pos = 0) const
1942 { return this->find(s, pos, Traits::length(s)); }
1943
1944 //! <b>Throws</b>: Nothing
1945 //!
1946 //! <b>Returns</b>: find(basic_string<CharT,traits,Allocator>(1,c), pos).
1947 size_type find(CharT c, size_type pos = 0) const
1948 {
1949 const size_type sz = this->size();
1950 if (pos >= sz)
1951 return npos;
1952 else {
1953 const pointer addr = this->priv_addr();
1954 pointer finish = addr + sz;
1955 const const_iterator result =
1956 std::find_if(addr + pos, finish,
1957 std::bind2nd(Eq_traits<Traits>(), c));
1958 return result != finish ? result - begin() : npos;
1959 }
1960 }
1961
1962 //! <b>Effects</b>: Determines the highest position xpos, if possible, such
1963 //! that both of the following conditions obtain:
1964 //! a) xpos <= pos and xpos + str.size() <= size();
1965 //! b) traits::eq(at(xpos+I), str.at(I)) for all elements I of the string controlled by str.
1966 //!
1967 //! <b>Throws</b>: Nothing
1968 //!
1969 //! <b>Returns</b>: xpos if the function can determine such a value for xpos. Otherwise, returns npos.
1970 size_type rfind(const basic_string& str, size_type pos = npos) const
1971 { return rfind(str.c_str(), pos, str.size()); }
1972
1973 //! <b>Requires</b>: s points to an array of at least n elements of CharT.
1974 //!
1975 //! <b>Throws</b>: Nothing
1976 //!
1977 //! <b>Returns</b>: rfind(basic_string(s, n), pos).
1978 size_type rfind(const CharT* s, size_type pos, size_type n) const
1979 {
1980 const size_type len = this->size();
1981
1982 if (n > len)
1983 return npos;
1984 else if (n == 0)
1985 return container_detail::min_value(len, pos);
1986 else {
1987 const const_iterator last = begin() + container_detail::min_value(len - n, pos) + n;
1988 const const_iterator result = find_end(begin(), last,
1989 s, s + n,
1990 Eq_traits<Traits>());
1991 return result != last ? result - begin() : npos;
1992 }
1993 }
1994
1995 //! <b>Requires</b>: pos <= size() and s points to an array of at least
1996 //! traits::length(s) + 1 elements of CharT.
1997 //!
1998 //! <b>Throws</b>: Nothing
1999 //!
2000 //! <b>Returns</b>: rfind(basic_string(s), pos).
2001 size_type rfind(const CharT* s, size_type pos = npos) const
2002 { return rfind(s, pos, Traits::length(s)); }
2003
2004 //! <b>Throws</b>: Nothing
2005 //!
2006 //! <b>Returns</b>: rfind(basic_string<CharT,traits,Allocator>(1,c),pos).
2007 size_type rfind(CharT c, size_type pos = npos) const
2008 {
2009 const size_type len = this->size();
2010
2011 if (len < 1)
2012 return npos;
2013 else {
2014 const const_iterator last = begin() + container_detail::min_value(len - 1, pos) + 1;
2015 const_reverse_iterator rresult =
2016 std::find_if(const_reverse_iterator(last), rend(),
2017 std::bind2nd(Eq_traits<Traits>(), c));
2018 return rresult != rend() ? (rresult.base() - 1) - begin() : npos;
2019 }
2020 }
2021
2022 //! <b>Effects</b>: Determines the lowest position xpos, if possible, such that both of the
2023 //! following conditions obtain: a) pos <= xpos and xpos < size();
2024 //! b) traits::eq(at(xpos), str.at(I)) for some element I of the string controlled by str.
2025 //!
2026 //! <b>Throws</b>: Nothing
2027 //!
2028 //! <b>Returns</b>: xpos if the function can determine such a value for xpos. Otherwise, returns npos.
2029 size_type find_first_of(const basic_string& s, size_type pos = 0) const
2030 { return find_first_of(s.c_str(), pos, s.size()); }
2031
2032 //! <b>Requires</b>: s points to an array of at least n elements of CharT.
2033 //!
2034 //! <b>Throws</b>: Nothing
2035 //!
2036 //! <b>Returns</b>: find_first_of(basic_string(s, n), pos).
2037 size_type find_first_of(const CharT* s, size_type pos, size_type n) const
2038 {
2039 const size_type sz = this->size();
2040 if (pos >= sz)
2041 return npos;
2042 else {
2043 const pointer addr = this->priv_addr();
2044 pointer finish = addr + sz;
2045 const_iterator result = std::find_first_of
2046 (addr + pos, finish, s, s + n, Eq_traits<Traits>());
2047 return result != finish ? result - this->begin() : npos;
2048 }
2049 }
2050
2051 //! <b>Requires</b>: s points to an array of at least traits::length(s) + 1 elements of CharT.
2052 //!
2053 //! <b>Throws</b>: Nothing
2054 //!
2055 //! <b>Returns</b>: find_first_of(basic_string(s), pos).
2056 size_type find_first_of(const CharT* s, size_type pos = 0) const
2057 { return find_first_of(s, pos, Traits::length(s)); }
2058
2059 //! <b>Requires</b>: s points to an array of at least traits::length(s) + 1 elements of CharT.
2060 //!
2061 //! <b>Throws</b>: Nothing
2062 //!
2063 //! <b>Returns</b>: find_first_of(basic_string<CharT,traits,Allocator>(1,c), pos).
2064 size_type find_first_of(CharT c, size_type pos = 0) const
2065 { return find(c, pos); }
2066
2067 //! <b>Effects</b>: Determines the highest position xpos, if possible, such that both of
2068 //! the following conditions obtain: a) xpos <= pos and xpos < size(); b)
2069 //! traits::eq(at(xpos), str.at(I)) for some element I of the string controlled by str.
2070 //!
2071 //! <b>Throws</b>: Nothing
2072 //!
2073 //! <b>Returns</b>: xpos if the function can determine such a value for xpos. Otherwise, returns npos.
2074 size_type find_last_of(const basic_string& str, size_type pos = npos) const
2075 { return find_last_of(str.c_str(), pos, str.size()); }
2076
2077 //! <b>Requires</b>: s points to an array of at least n elements of CharT.
2078 //!
2079 //! <b>Throws</b>: Nothing
2080 //!
2081 //! <b>Returns</b>: find_last_of(basic_string(s, n), pos).
2082 size_type find_last_of(const CharT* s, size_type pos, size_type n) const
2083 {
2084 const size_type len = this->size();
2085
2086 if (len < 1)
2087 return npos;
2088 else {
2089 const pointer addr = this->priv_addr();
2090 const const_iterator last = addr + container_detail::min_value(len - 1, pos) + 1;
2091 const const_reverse_iterator rresult =
2092 std::find_first_of(const_reverse_iterator(last), rend(),
2093 s, s + n, Eq_traits<Traits>());
2094 return rresult != rend() ? (rresult.base() - 1) - addr : npos;
2095 }
2096 }
2097
2098 //! <b>Requires</b>: s points to an array of at least traits::length(s) + 1 elements of CharT.
2099 //!
2100 //! <b>Throws</b>: Nothing
2101 //!
2102 //! <b>Returns</b>: find_last_of(basic_string<CharT,traits,Allocator>(1,c),pos).
2103 size_type find_last_of(const CharT* s, size_type pos = npos) const
2104 { return find_last_of(s, pos, Traits::length(s)); }
2105
2106 //! <b>Throws</b>: Nothing
2107 //!
2108 //! <b>Returns</b>: find_last_of(basic_string(s), pos).
2109 size_type find_last_of(CharT c, size_type pos = npos) const
2110 { return rfind(c, pos); }
2111
2112 //! <b>Effects</b>: Determines the lowest position xpos, if possible, such that
2113 //! both of the following conditions obtain:
2114 //! a) pos <= xpos and xpos < size(); b) traits::eq(at(xpos), str.at(I)) for no
2115 //! element I of the string controlled by str.
2116 //!
2117 //! <b>Throws</b>: Nothing
2118 //!
2119 //! <b>Returns</b>: xpos if the function can determine such a value for xpos. Otherwise, returns npos.
2120 size_type find_first_not_of(const basic_string& str, size_type pos = 0) const
2121 { return find_first_not_of(str.c_str(), pos, str.size()); }
2122
2123 //! <b>Requires</b>: s points to an array of at least traits::length(s) + 1 elements of CharT.
2124 //!
2125 //! <b>Throws</b>: Nothing
2126 //!
2127 //! <b>Returns</b>: find_first_not_of(basic_string(s, n), pos).
2128 size_type find_first_not_of(const CharT* s, size_type pos, size_type n) const
2129 {
2130 if (pos > this->size())
2131 return npos;
2132 else {
2133 const pointer addr = this->priv_addr();
2134 const pointer finish = addr + this->priv_size();
2135 const const_iterator result = std::find_if
2136 (addr + pos, finish, Not_within_traits<Traits>(s, s + n));
2137 return result != finish ? result - addr : npos;
2138 }
2139 }
2140
2141 //! <b>Requires</b>: s points to an array of at least traits::length(s) + 1 elements of CharT.
2142 //!
2143 //! <b>Throws</b>: Nothing
2144 //!
2145 //! <b>Returns</b>: find_first_not_of(basic_string(s), pos).
2146 size_type find_first_not_of(const CharT* s, size_type pos = 0) const
2147 { return find_first_not_of(s, pos, Traits::length(s)); }
2148
2149 //! <b>Throws</b>: Nothing
2150 //!
2151 //! <b>Returns</b>: find_first_not_of(basic_string(1, c), pos).
2152 size_type find_first_not_of(CharT c, size_type pos = 0) const
2153 {
2154 if (pos > this->size())
2155 return npos;
2156 else {
2157 const pointer addr = this->priv_addr();
2158 const pointer finish = addr + this->priv_size();
2159 const const_iterator result
2160 = std::find_if(addr + pos, finish,
2161 std::not1(std::bind2nd(Eq_traits<Traits>(), c)));
2162 return result != finish ? result - begin() : npos;
2163 }
2164 }
2165
2166 //! <b>Effects</b>: Determines the highest position xpos, if possible, such that
2167 //! both of the following conditions obtain: a) xpos <= pos and xpos < size();
2168 //! b) traits::eq(at(xpos), str.at(I)) for no element I of the string controlled by str.
2169 //!
2170 //! <b>Throws</b>: Nothing
2171 //!
2172 //! <b>Returns</b>: xpos if the function can determine such a value for xpos. Otherwise, returns npos.
2173 size_type find_last_not_of(const basic_string& str, size_type pos = npos) const
2174 { return find_last_not_of(str.c_str(), pos, str.size()); }
2175
2176 //! <b>Requires</b>: s points to an array of at least n elements of CharT.
2177 //!
2178 //! <b>Throws</b>: Nothing
2179 //!
2180 //! <b>Returns</b>: find_last_not_of(basic_string(s, n), pos).
2181 size_type find_last_not_of(const CharT* s, size_type pos, size_type n) const
2182 {
2183 const size_type len = this->size();
2184
2185 if (len < 1)
2186 return npos;
2187 else {
2188 const const_iterator last = begin() + container_detail::min_value(len - 1, pos) + 1;
2189 const const_reverse_iterator rresult =
2190 std::find_if(const_reverse_iterator(last), rend(),
2191 Not_within_traits<Traits>(s, s + n));
2192 return rresult != rend() ? (rresult.base() - 1) - begin() : npos;
2193 }
2194 }
2195
2196 //! <b>Requires</b>: s points to an array of at least traits::length(s) + 1 elements of CharT.
2197 //!
2198 //! <b>Throws</b>: Nothing
2199 //!
2200 //! <b>Returns</b>: find_last_not_of(basic_string(s), pos).
2201 size_type find_last_not_of(const CharT* s, size_type pos = npos) const
2202 { return find_last_not_of(s, pos, Traits::length(s)); }
2203
2204 //! <b>Throws</b>: Nothing
2205 //!
2206 //! <b>Returns</b>: find_last_not_of(basic_string(1, c), pos).
2207 size_type find_last_not_of(CharT c, size_type pos = npos) const
2208 {
2209 const size_type len = this->size();
2210
2211 if (len < 1)
2212 return npos;
2213 else {
2214 const const_iterator last = begin() + container_detail::min_value(len - 1, pos) + 1;
2215 const const_reverse_iterator rresult =
2216 std::find_if(const_reverse_iterator(last), rend(),
2217 std::not1(std::bind2nd(Eq_traits<Traits>(), c)));
2218 return rresult != rend() ? (rresult.base() - 1) - begin() : npos;
2219 }
2220 }
2221
2222 //! <b>Requires</b>: Requires: pos <= size()
2223 //!
2224 //! <b>Effects</b>: Determines the effective length rlen of the string to copy as
2225 //! the smaller of n and size() - pos.
2226 //!
2227 //! <b>Throws</b>: If memory allocation throws or out_of_range if pos > size().
2228 //!
2229 //! <b>Returns</b>: basic_string<CharT,traits,Allocator>(data()+pos,rlen).
2230 basic_string substr(size_type pos = 0, size_type n = npos) const
2231 {
2232 if (pos > this->size())
2233 this->throw_out_of_range();
2234 const pointer addr = this->priv_addr();
2235 return basic_string(addr + pos,
2236 addr + pos + container_detail::min_value(n, size() - pos), this->alloc());
2237 }
2238
2239 //! <b>Effects</b>: Determines the effective length rlen of the string to copy as
2240 //! the smaller of size() and str.size(). The function then compares the two strings by
2241 //! calling traits::compare(data(), str.data(), rlen).
2242 //!
2243 //! <b>Throws</b>: Nothing
2244 //!
2245 //! <b>Returns</b>: The nonzero result if the result of the comparison is nonzero.
2246 //! Otherwise, returns a value < 0 if size() < str.size(), a 0 value if size() == str.size(),
2247 //! and value > 0 if size() > str.size()
2248 int compare(const basic_string& str) const
2249 {
2250 const pointer addr = this->priv_addr();
2251 const pointer str_addr = str.priv_addr();
2252 return s_compare(addr, addr + this->priv_size(), str_addr, str_addr + str.priv_size());
2253 }
2254
2255 //! <b>Requires</b>: pos1 <= size()
2256 //!
2257 //! <b>Effects</b>: Determines the effective length rlen of the string to copy as
2258 //! the smaller of
2259 //!
2260 //! <b>Throws</b>: out_of_range if pos1 > size()
2261 //!
2262 //! <b>Returns</b>:basic_string(*this,pos1,n1).compare(str).
2263 int compare(size_type pos1, size_type n1, const basic_string& str) const
2264 {
2265 if (pos1 > this->size())
2266 this->throw_out_of_range();
2267 const pointer addr = this->priv_addr();
2268 const pointer str_addr = str.priv_addr();
2269 return s_compare(addr + pos1,
2270 addr + pos1 + container_detail::min_value(n1, this->size() - pos1),
2271 str_addr, str_addr + str.priv_size());
2272 }
2273
2274 //! <b>Requires</b>: pos1 <= size() and pos2 <= str.size()
2275 //!
2276 //! <b>Effects</b>: Determines the effective length rlen of the string to copy as
2277 //! the smaller of
2278 //!
2279 //! <b>Throws</b>: out_of_range if pos1 > size() or pos2 > str.size()
2280 //!
2281 //! <b>Returns</b>: basic_string(*this, pos1, n1).compare(basic_string(str, pos2, n2)).
2282 int compare(size_type pos1, size_type n1, const basic_string& str, size_type pos2, size_type n2) const
2283 {
2284 if (pos1 > this->size() || pos2 > str.size())
2285 this->throw_out_of_range();
2286 const pointer addr = this->priv_addr();
2287 const pointer str_addr = str.priv_addr();
2288 return s_compare(addr + pos1,
2289 addr + pos1 + container_detail::min_value(n1, this->size() - pos1),
2290 str_addr + pos2,
2291 str_addr + pos2 + container_detail::min_value(n2, str.size() - pos2));
2292 }
2293
2294 //! <b>Throws</b>: Nothing
2295 //!
2296 //! <b>Returns</b>: compare(basic_string(s)).
2297 int compare(const CharT* s) const
2298 {
2299 const pointer addr = this->priv_addr();
2300 return s_compare(addr, addr + this->priv_size(), s, s + Traits::length(s));
2301 }
2302
2303
2304 //! <b>Requires</b>: pos1 > size() and s points to an array of at least n2 elements of CharT.
2305 //!
2306 //! <b>Throws</b>: out_of_range if pos1 > size()
2307 //!
2308 //! <b>Returns</b>: basic_string(*this, pos, n1).compare(basic_string(s, n2)).
2309 int compare(size_type pos1, size_type n1, const CharT* s, size_type n2) const
2310 {
2311 if (pos1 > this->size())
2312 this->throw_out_of_range();
2313 const pointer addr = this->priv_addr();
2314 return s_compare( addr + pos1,
2315 addr + pos1 + container_detail::min_value(n1, this->size() - pos1),
2316 s, s + n2);
2317 }
2318
2319 //! <b>Requires</b>: pos1 > size() and s points to an array of at least traits::length(s) + 1 elements of CharT.
2320 //!
2321 //! <b>Throws</b>: out_of_range if pos1 > size()
2322 //!
2323 //! <b>Returns</b>: basic_string(*this, pos, n1).compare(basic_string(s, n2)).
2324 int compare(size_type pos1, size_type n1, const CharT* s) const
2325 { return this->compare(pos1, n1, s, Traits::length(s)); }
2326
2327 /// @cond
2328 private:
2329 static int s_compare(const_pointer f1, const_pointer l1,
2330 const_pointer f2, const_pointer l2)
2331 {
2332 const difference_type n1 = l1 - f1;
2333 const difference_type n2 = l2 - f2;
2334 const int cmp = Traits::compare(container_detail::to_raw_pointer(f1),
2335 container_detail::to_raw_pointer(f2),
2336 container_detail::min_value(n1, n2));
2337 return cmp != 0 ? cmp : (n1 < n2 ? -1 : (n1 > n2 ? 1 : 0));
2338 }
2339
2340 template<class AllocVersion>
2341 void priv_shrink_to_fit_dynamic_buffer
2342 ( AllocVersion
2343 , typename container_detail::enable_if<container_detail::is_same<AllocVersion, allocator_v1> >::type* = 0)
2344 {
2345 //Allocate a new buffer.
2346 size_type real_cap = 0;
2347 const pointer long_addr = this->priv_long_addr();
2348 const size_type long_size = this->priv_long_size();
2349 const size_type long_storage = this->priv_long_storage();
2350 //We can make this nothrow as chars are always NoThrowCopyables
2351 BOOST_TRY{
2352 const std::pair<pointer, bool> ret = this->allocation_command
2353 (allocate_new, long_size+1, long_size+1, real_cap, long_addr);
2354 //Copy and update
2355 Traits::copy( container_detail::to_raw_pointer(ret.first)
2356 , container_detail::to_raw_pointer(this->priv_long_addr())
2357 , long_size+1);
2358 this->priv_long_addr(ret.first);
2359 this->priv_storage(real_cap);
2360 //And release old buffer
2361 this->alloc().deallocate(long_addr, long_storage);
2362 }
2363 BOOST_CATCH(...){
2364 return;
2365 }
2366 BOOST_CATCH_END
2367 }
2368
2369 template<class AllocVersion>
2370 void priv_shrink_to_fit_dynamic_buffer
2371 ( AllocVersion
2372 , typename container_detail::enable_if<container_detail::is_same<AllocVersion, allocator_v2> >::type* = 0)
2373 {
2374 size_type received_size;
2375 if(this->alloc().allocation_command
2376 ( shrink_in_place | nothrow_allocation
2377 , this->priv_long_storage(), this->priv_long_size()+1
2378 , received_size, this->priv_long_addr()).first){
2379 this->priv_storage(received_size);
2380 }
2381 }
2382
2383 void priv_construct_null(pointer p)
2384 { this->construct(p, CharT(0)); }
2385
2386 // Helper functions used by constructors. It is a severe error for
2387 // any of them to be called anywhere except from within constructors.
2388 void priv_terminate_string()
2389 { this->priv_construct_null(this->priv_end_addr()); }
2390
2391 template<class FwdIt, class Count> inline
2392 void priv_uninitialized_fill_n(FwdIt first, Count count, const CharT val)
2393 {
2394 //Save initial position
2395 FwdIt init = first;
2396
2397 BOOST_TRY{
2398 //Construct objects
2399 for (; count--; ++first){
2400 this->construct(first, val);
2401 }
2402 }
2403 BOOST_CATCH(...){
2404 //Call destructors
2405 for (; init != first; ++init){
2406 this->destroy(init);
2407 }
2408 BOOST_RETHROW
2409 }
2410 BOOST_CATCH_END
2411 }
2412
2413 template<class InpIt, class FwdIt> inline
2414 size_type priv_uninitialized_copy(InpIt first, InpIt last, FwdIt dest)
2415 {
2416 //Save initial destination position
2417 FwdIt dest_init = dest;
2418 size_type constructed = 0;
2419
2420 BOOST_TRY{
2421 //Try to build objects
2422 for (; first != last; ++dest, ++first, ++constructed){
2423 this->construct(dest, *first);
2424 }
2425 }
2426 BOOST_CATCH(...){
2427 //Call destructors
2428 for (; constructed--; ++dest_init){
2429 this->destroy(dest_init);
2430 }
2431 BOOST_RETHROW
2432 }
2433 BOOST_CATCH_END
2434 return (constructed);
2435 }
2436
2437 template <class InputIterator, class OutIterator>
2438 void priv_copy(InputIterator first, InputIterator last, OutIterator result)
2439 {
2440 for ( ; first != last; ++first, ++result)
2441 Traits::assign(*result, *first);
2442 }
2443
2444 void priv_copy(const CharT* first, const CharT* last, CharT* result)
2445 { Traits::copy(result, first, last - first); }
2446
2447 template <class Integer>
2448 basic_string& priv_replace_dispatch(const_iterator first, const_iterator last,
2449 Integer n, Integer x,
2450 container_detail::true_)
2451 { return this->replace(first, last, (size_type) n, (CharT) x); }
2452
2453 template <class InputIter>
2454 basic_string& priv_replace_dispatch(const_iterator first, const_iterator last,
2455 InputIter f, InputIter l,
2456 container_detail::false_)
2457 {
2458 typedef typename std::iterator_traits<InputIter>::iterator_category Category;
2459 return this->priv_replace(first, last, f, l, Category());
2460 }
2461
2462 /// @endcond
2463};
2464
2465//!Typedef for a basic_string of
2466//!narrow characters
2467typedef basic_string
2468 <char
2469 ,std::char_traits<char>
2470 ,std::allocator<char> >
2471string;
2472
2473//!Typedef for a basic_string of
2474//!narrow characters
2475typedef basic_string
2476 <wchar_t
2477 ,std::char_traits<wchar_t>
2478 ,std::allocator<wchar_t> >
2479wstring;
2480
2481// ------------------------------------------------------------
2482// Non-member functions.
2483
2484// Operator+
2485
2486template <class CharT, class Traits, class Allocator> inline
2487 basic_string<CharT,Traits,Allocator>
2488 operator+(const basic_string<CharT,Traits,Allocator>& x
2489 ,const basic_string<CharT,Traits,Allocator>& y)
2490{
2491 typedef basic_string<CharT,Traits,Allocator> str_t;
2492 typedef typename str_t::reserve_t reserve_t;
2493 reserve_t reserve;
2494 str_t result(reserve, x.size() + y.size(), x.get_stored_allocator());
2495 result.append(x);
2496 result.append(y);
2497 return result;
2498}
2499
2500template <class CharT, class Traits, class Allocator> inline
2501 basic_string<CharT, Traits, Allocator> operator+
2502 ( BOOST_RV_REF_BEG basic_string<CharT, Traits, Allocator> BOOST_RV_REF_END mx
2503 , BOOST_RV_REF_BEG basic_string<CharT, Traits, Allocator> BOOST_RV_REF_END my)
2504{
2505 mx += my;
2506 return boost::move(mx);
2507}
2508
2509template <class CharT, class Traits, class Allocator> inline
2510 basic_string<CharT, Traits, Allocator> operator+
2511 ( BOOST_RV_REF_BEG basic_string<CharT, Traits, Allocator> BOOST_RV_REF_END mx
2512 , const basic_string<CharT,Traits,Allocator>& y)
2513{
2514 mx += y;
2515 return boost::move(mx);
2516}
2517
2518template <class CharT, class Traits, class Allocator> inline
2519 basic_string<CharT, Traits, Allocator> operator+
2520 (const basic_string<CharT,Traits,Allocator>& x
2521 ,BOOST_RV_REF_BEG basic_string<CharT, Traits, Allocator> BOOST_RV_REF_END my)
2522{
2523 my.insert(my.begin(), x.begin(), x.end());
2524 return boost::move(my);
2525}
2526
2527template <class CharT, class Traits, class Allocator> inline
2528 basic_string<CharT, Traits, Allocator> operator+
2529 (const CharT* s, basic_string<CharT, Traits, Allocator> y)
2530{
2531 y.insert(y.begin(), s, s + Traits::length(s));
2532 return y;
2533}
2534
2535template <class CharT, class Traits, class Allocator> inline
2536 basic_string<CharT,Traits,Allocator> operator+
2537 (basic_string<CharT,Traits,Allocator> x, const CharT* s)
2538{
2539 x += s;
2540 return x;
2541}
2542
2543template <class CharT, class Traits, class Allocator> inline
2544 basic_string<CharT,Traits,Allocator> operator+
2545 (CharT c, basic_string<CharT,Traits,Allocator> y)
2546{
2547 y.insert(y.begin(), c);
2548 return y;
2549}
2550
2551template <class CharT, class Traits, class Allocator> inline
2552 basic_string<CharT,Traits,Allocator> operator+
2553 (basic_string<CharT,Traits,Allocator> x, const CharT c)
2554{
2555 x += c;
2556 return x;
2557}
2558
2559// Operator== and operator!=
2560
2561template <class CharT, class Traits, class Allocator>
2562inline bool
2563operator==(const basic_string<CharT,Traits,Allocator>& x,
2564 const basic_string<CharT,Traits,Allocator>& y)
2565{
2566 return x.size() == y.size() &&
2567 Traits::compare(x.data(), y.data(), x.size()) == 0;
2568}
2569
2570template <class CharT, class Traits, class Allocator>
2571inline bool
2572operator==(const CharT* s, const basic_string<CharT,Traits,Allocator>& y)
2573{
2574 typename basic_string<CharT,Traits,Allocator>::size_type n = Traits::length(s);
2575 return n == y.size() && Traits::compare(s, y.data(), n) == 0;
2576}
2577
2578template <class CharT, class Traits, class Allocator>
2579inline bool
2580operator==(const basic_string<CharT,Traits,Allocator>& x, const CharT* s)
2581{
2582 typename basic_string<CharT,Traits,Allocator>::size_type n = Traits::length(s);
2583 return x.size() == n && Traits::compare(x.data(), s, n) == 0;
2584}
2585
2586template <class CharT, class Traits, class Allocator>
2587inline bool
2588operator!=(const basic_string<CharT,Traits,Allocator>& x,
2589 const basic_string<CharT,Traits,Allocator>& y)
2590 { return !(x == y); }
2591
2592template <class CharT, class Traits, class Allocator>
2593inline bool
2594operator!=(const CharT* s, const basic_string<CharT,Traits,Allocator>& y)
2595 { return !(s == y); }
2596
2597template <class CharT, class Traits, class Allocator>
2598inline bool
2599operator!=(const basic_string<CharT,Traits,Allocator>& x, const CharT* s)
2600 { return !(x == s); }
2601
2602
2603// Operator< (and also >, <=, and >=).
2604
2605template <class CharT, class Traits, class Allocator>
2606inline bool
2607operator<(const basic_string<CharT,Traits,Allocator>& x, const basic_string<CharT,Traits,Allocator>& y)
2608{
2609 return x.compare(y) < 0;
2610// return basic_string<CharT,Traits,Allocator>
2611// ::s_compare(x.begin(), x.end(), y.begin(), y.end()) < 0;
2612}
2613
2614template <class CharT, class Traits, class Allocator>
2615inline bool
2616operator<(const CharT* s, const basic_string<CharT,Traits,Allocator>& y)
2617{
2618 return y.compare(s) > 0;
2619// basic_string<CharT,Traits,Allocator>::size_type n = Traits::length(s);
2620// return basic_string<CharT,Traits,Allocator>
2621// ::s_compare(s, s + n, y.begin(), y.end()) < 0;
2622}
2623
2624template <class CharT, class Traits, class Allocator>
2625inline bool
2626operator<(const basic_string<CharT,Traits,Allocator>& x,
2627 const CharT* s)
2628{
2629 return x.compare(s) < 0;
2630// basic_string<CharT,Traits,Allocator>::size_type n = Traits::length(s);
2631// return basic_string<CharT,Traits,Allocator>
2632// ::s_compare(x.begin(), x.end(), s, s + n) < 0;
2633}
2634
2635template <class CharT, class Traits, class Allocator>
2636inline bool
2637operator>(const basic_string<CharT,Traits,Allocator>& x,
2638 const basic_string<CharT,Traits,Allocator>& y) {
2639 return y < x;
2640}
2641
2642template <class CharT, class Traits, class Allocator>
2643inline bool
2644operator>(const CharT* s, const basic_string<CharT,Traits,Allocator>& y) {
2645 return y < s;
2646}
2647
2648template <class CharT, class Traits, class Allocator>
2649inline bool
2650operator>(const basic_string<CharT,Traits,Allocator>& x, const CharT* s)
2651{
2652 return s < x;
2653}
2654
2655template <class CharT, class Traits, class Allocator>
2656inline bool
2657operator<=(const basic_string<CharT,Traits,Allocator>& x,
2658 const basic_string<CharT,Traits,Allocator>& y)
2659{
2660 return !(y < x);
2661}
2662
2663template <class CharT, class Traits, class Allocator>
2664inline bool
2665operator<=(const CharT* s, const basic_string<CharT,Traits,Allocator>& y)
2666 { return !(y < s); }
2667
2668template <class CharT, class Traits, class Allocator>
2669inline bool
2670operator<=(const basic_string<CharT,Traits,Allocator>& x, const CharT* s)
2671 { return !(s < x); }
2672
2673template <class CharT, class Traits, class Allocator>
2674inline bool
2675operator>=(const basic_string<CharT,Traits,Allocator>& x,
2676 const basic_string<CharT,Traits,Allocator>& y)
2677 { return !(x < y); }
2678
2679template <class CharT, class Traits, class Allocator>
2680inline bool
2681operator>=(const CharT* s, const basic_string<CharT,Traits,Allocator>& y)
2682 { return !(s < y); }
2683
2684template <class CharT, class Traits, class Allocator>
2685inline bool
2686operator>=(const basic_string<CharT,Traits,Allocator>& x, const CharT* s)
2687 { return !(x < s); }
2688
2689// Swap.
2690template <class CharT, class Traits, class Allocator>
2691inline void swap(basic_string<CharT,Traits,Allocator>& x, basic_string<CharT,Traits,Allocator>& y)
2692{ x.swap(y); }
2693
2694/// @cond
2695// I/O.
2696namespace container_detail {
2697
2698template <class CharT, class Traits>
2699inline bool
2700string_fill(std::basic_ostream<CharT, Traits>& os,
2701 std::basic_streambuf<CharT, Traits>* buf,
2702 std::size_t n)
2703{
2704 CharT f = os.fill();
2705 std::size_t i;
2706 bool ok = true;
2707
2708 for (i = 0; i < n; i++)
2709 ok = ok && !Traits::eq_int_type(buf->sputc(f), Traits::eof());
2710 return ok;
2711}
2712
2713} //namespace container_detail {
2714/// @endcond
2715
2716template <class CharT, class Traits, class Allocator>
2717std::basic_ostream<CharT, Traits>&
2718operator<<(std::basic_ostream<CharT, Traits>& os, const basic_string<CharT,Traits,Allocator>& s)
2719{
2720 typename std::basic_ostream<CharT, Traits>::sentry sentry(os);
2721 bool ok = false;
2722
2723 if (sentry) {
2724 ok = true;
2725 typename basic_string<CharT,Traits,Allocator>::size_type n = s.size();
2726 typename basic_string<CharT,Traits,Allocator>::size_type pad_len = 0;
2727 const bool left = (os.flags() & std::ios::left) != 0;
2728 const std::size_t w = os.width(0);
2729 std::basic_streambuf<CharT, Traits>* buf = os.rdbuf();
2730
2731 if (w != 0 && n < w)
2732 pad_len = w - n;
2733
2734 if (!left)
2735 ok = container_detail::string_fill(os, buf, pad_len);
2736
2737 ok = ok &&
2738 buf->sputn(s.data(), std::streamsize(n)) == std::streamsize(n);
2739
2740 if (left)
2741 ok = ok && container_detail::string_fill(os, buf, pad_len);
2742 }
2743
2744 if (!ok)
2745 os.setstate(std::ios_base::failbit);
2746
2747 return os;
2748}
2749
2750
2751template <class CharT, class Traits, class Allocator>
2752std::basic_istream<CharT, Traits>&
2753operator>>(std::basic_istream<CharT, Traits>& is, basic_string<CharT,Traits,Allocator>& s)
2754{
2755 typename std::basic_istream<CharT, Traits>::sentry sentry(is);
2756
2757 if (sentry) {
2758 std::basic_streambuf<CharT, Traits>* buf = is.rdbuf();
2759 const std::ctype<CharT>& ctype = std::use_facet<std::ctype<CharT> >(is.getloc());
2760
2761 s.clear();
2762 std::size_t n = is.width(0);
2763 if (n == 0)
2764 n = static_cast<std::size_t>(-1);
2765 else
2766 s.reserve(n);
2767
2768 while (n-- > 0) {
2769 typename Traits::int_type c1 = buf->sbumpc();
2770
2771 if (Traits::eq_int_type(c1, Traits::eof())) {
2772 is.setstate(std::ios_base::eofbit);
2773 break;
2774 }
2775 else {
2776 CharT c = Traits::to_char_type(c1);
2777
2778 if (ctype.is(std::ctype<CharT>::space, c)) {
2779 if (Traits::eq_int_type(buf->sputbackc(c), Traits::eof()))
2780 is.setstate(std::ios_base::failbit);
2781 break;
2782 }
2783 else
2784 s.push_back(c);
2785 }
2786 }
2787
2788 // If we have read no characters, then set failbit.
2789 if (s.size() == 0)
2790 is.setstate(std::ios_base::failbit);
2791 }
2792 else
2793 is.setstate(std::ios_base::failbit);
2794
2795 return is;
2796}
2797
2798template <class CharT, class Traits, class Allocator>
2799std::basic_istream<CharT, Traits>&
2800getline(std::istream& is, basic_string<CharT,Traits,Allocator>& s,CharT delim)
2801{
2802 typename basic_string<CharT,Traits,Allocator>::size_type nread = 0;
2803 typename std::basic_istream<CharT, Traits>::sentry sentry(is, true);
2804 if (sentry) {
2805 std::basic_streambuf<CharT, Traits>* buf = is.rdbuf();
2806 s.clear();
2807
2808 while (nread < s.max_size()) {
2809 int c1 = buf->sbumpc();
2810 if (Traits::eq_int_type(c1, Traits::eof())) {
2811 is.setstate(std::ios_base::eofbit);
2812 break;
2813 }
2814 else {
2815 ++nread;
2816 CharT c = Traits::to_char_type(c1);
2817 if (!Traits::eq(c, delim))
2818 s.push_back(c);
2819 else
2820 break; // Character is extracted but not appended.
2821 }
2822 }
2823 }
2824 if (nread == 0 || nread >= s.max_size())
2825 is.setstate(std::ios_base::failbit);
2826
2827 return is;
2828}
2829
2830template <class CharT, class Traits, class Allocator>
2831inline std::basic_istream<CharT, Traits>&
2832getline(std::basic_istream<CharT, Traits>& is, basic_string<CharT,Traits,Allocator>& s)
2833{
2834 return getline(is, s, '\n');
2835}
2836
2837template <class Ch, class Allocator>
2838inline std::size_t hash_value(basic_string<Ch, std::char_traits<Ch>, Allocator> const& v)
2839{
2840 return hash_range(v.begin(), v.end());
2841}
2842
2843}}
2844
2845/// @cond
2846
2847namespace boost {
2848
2849//!has_trivial_destructor_after_move<> == true_type
2850//!specialization for optimizations
2851template <class C, class T, class Allocator>
2852struct has_trivial_destructor_after_move<boost::container::basic_string<C, T, Allocator> >
2853 : public ::boost::has_trivial_destructor_after_move<Allocator>
2854{};
2855
2856}
2857
2858/// @endcond
2859
2860#include <boost/container/detail/config_end.hpp>
2861
2862#endif // BOOST_CONTAINER_STRING_HPP