source: mainline/uspace/lib/cpp/include/__bits/string/string.hpp@ 08e103d4

Last change on this file since 08e103d4 was 08e103d4, checked in by Jiří Zárevúcky <zarevucky.jiri@…>, 7 years ago

Use clearer naming for string length functions

This and the following commit change the names of functions, as well as
their documentation, to use unambiguous terms "bytes" and "code points"
instead of ambiguous terms "size", "length", and "characters".
  • Property mode set to 100644
File size: 60.4 KB
Line 
1/*
2 * Copyright (c) 2019 Jaroslav Jindrak
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *
9 * - Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * - Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * - The name of the author may not be used to endorse or promote products
15 * derived from this software without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28
29#ifndef LIBCPP_BITS_STRING
30#define LIBCPP_BITS_STRING
31
32#include <__bits/string/stringfwd.hpp>
33#include <algorithm>
34#include <cassert>
35#include <initializer_list>
36#include <iosfwd>
37#include <iterator>
38#include <cstdio>
39#include <cstdlib>
40#include <cstring>
41#include <cwchar>
42#include <memory>
43#include <utility>
44
45namespace std
46{
47 /**
48 * 21.2, char_traits:
49 */
50
51 template<class Char>
52 struct char_traits;
53
54 /**
55 * 21.2.3, char_traits specializations:
56 */
57
58 template<>
59 struct char_traits<char>
60 {
61 using char_type = char;
62 using int_type = int;
63 using off_type = streamoff;
64 using pos_type = streampos;
65 /* using state_type = mbstate_t; */
66
67 static void assign(char_type& c1, const char_type& c2) noexcept
68 {
69 c1 = c2;
70 }
71
72 static constexpr bool eq(char_type c1, char_type c2) noexcept
73 {
74 return c1 == c2;
75 }
76
77 static constexpr bool lt(char_type c1, char_type c2) noexcept
78 {
79 return c1 < c2;
80 }
81
82 static int compare(const char_type* s1, const char_type* s2, size_t n)
83 {
84 return hel::str_lcmp(s1, s2, n);
85 }
86
87 static size_t length(const char_type* s)
88 {
89 return hel::str_bytes(s);
90 }
91
92 static const char_type* find(const char_type* s, size_t n, const char_type& c)
93 {
94 size_t i{};
95 while (i++ < n)
96 {
97 if (s[i] == c)
98 return s + i;
99 }
100
101 return nullptr;
102 }
103
104 static char_type* move(char_type* s1, const char_type* s2, size_t n)
105 {
106 return static_cast<char_type*>(memmove(s1, s2, n));
107 }
108
109 static char_type* copy(char_type* s1, const char_type* s2, size_t n)
110 {
111 return static_cast<char_type*>(memcpy(s1, s2, n));
112 }
113
114 static char_type* assign(char_type* s, size_t n, char_type c)
115 {
116 /**
117 * Note: Even though memset accepts int as its second argument,
118 * the actual implementation assigns that int to a dereferenced
119 * char pointer.
120 */
121 return static_cast<char_type*>(memset(s, static_cast<int>(c), n));
122 }
123
124 static constexpr int_type not_eof(int_type c) noexcept
125 {
126 if (!eq_int_type(c, eof()))
127 return c;
128 else
129 return to_int_type('a'); // We just need something that is not eof.
130 }
131
132 static constexpr char_type to_char_type(int_type c) noexcept
133 {
134 return static_cast<char_type>(c);
135 }
136
137 static constexpr int_type to_int_type(char_type c) noexcept
138 {
139 return static_cast<int_type>(c);
140 }
141
142 static constexpr bool eq_int_type(int_type c1, int_type c2) noexcept
143 {
144 return c1 == c2;
145 }
146
147 static constexpr int_type eof() noexcept
148 {
149 return static_cast<int_type>(EOF);
150 }
151 };
152
153 template<>
154 struct char_traits<char16_t>
155 {
156 // TODO: implement
157 using char_type = char16_t;
158 using int_type = int16_t;
159 using off_type = streamoff;
160 using pos_type = streampos;
161 /* using state_type = mbstate_t; */
162
163 static void assign(char_type& c1, const char_type& c2) noexcept
164 {
165 c1 = c2;
166 }
167
168 static constexpr bool eq(char_type c1, char_type c2) noexcept
169 {
170 return c1 == c2;
171 }
172
173 static constexpr bool lt(char_type c1, char_type c2) noexcept
174 {
175 return c1 < c2;
176 }
177
178 static int compare(const char_type* s1, const char_type* s2, size_t n)
179 {
180 // TODO: implement
181 __unimplemented();
182 return 0;
183 }
184
185 static size_t length(const char_type* s)
186 {
187 // TODO: implement
188 __unimplemented();
189 return 0;
190 }
191
192 static const char_type* find(const char_type* s, size_t n, const char_type& c)
193 {
194 // TODO: implement
195 __unimplemented();
196 return nullptr;
197 }
198
199 static char_type* move(char_type* s1, const char_type* s2, size_t n)
200 {
201 // TODO: implement
202 __unimplemented();
203 return nullptr;
204 }
205
206 static char_type* copy(char_type* s1, const char_type* s2, size_t n)
207 {
208 // TODO: implement
209 __unimplemented();
210 return nullptr;
211 }
212
213 static char_type* assign(char_type* s, size_t n, char_type c)
214 {
215 // TODO: implement
216 __unimplemented();
217 return nullptr;
218 }
219
220 static constexpr int_type not_eof(int_type c) noexcept
221 {
222 // TODO: implement
223 return int_type{};
224 }
225
226 static constexpr char_type to_char_type(int_type c) noexcept
227 {
228 return static_cast<char_type>(c);
229 }
230
231 static constexpr int_type to_int_type(char_type c) noexcept
232 {
233 return static_cast<int_type>(c);
234 }
235
236 static constexpr bool eq_int_type(int_type c1, int_type c2) noexcept
237 {
238 return c1 == c2;
239 }
240
241 static constexpr int_type eof() noexcept
242 {
243 return static_cast<int_type>(EOF);
244 }
245 };
246
247 template<>
248 struct char_traits<char32_t>
249 {
250 // TODO: implement
251 using char_type = char32_t;
252 using int_type = int32_t;
253 using off_type = streamoff;
254 using pos_type = streampos;
255 /* using state_type = mbstate_t; */
256
257 static void assign(char_type& c1, const char_type& c2) noexcept
258 {
259 c1 = c2;
260 }
261
262 static constexpr bool eq(char_type c1, char_type c2) noexcept
263 {
264 return c1 == c2;
265 }
266
267 static constexpr bool lt(char_type c1, char_type c2) noexcept
268 {
269 return c1 < c2;
270 }
271
272 static int compare(const char_type* s1, const char_type* s2, size_t n)
273 {
274 // TODO: implement
275 __unimplemented();
276 return 0;
277 }
278
279 static size_t length(const char_type* s)
280 {
281 // TODO: implement
282 __unimplemented();
283 return 0;
284 }
285
286 static const char_type* find(const char_type* s, size_t n, const char_type& c)
287 {
288 // TODO: implement
289 __unimplemented();
290 return nullptr;
291 }
292
293 static char_type* move(char_type* s1, const char_type* s2, size_t n)
294 {
295 // TODO: implement
296 __unimplemented();
297 return nullptr;
298 }
299
300 static char_type* copy(char_type* s1, const char_type* s2, size_t n)
301 {
302 // TODO: implement
303 __unimplemented();
304 return nullptr;
305 }
306
307 static char_type* assign(char_type* s, size_t n, char_type c)
308 {
309 // TODO: implement
310 __unimplemented();
311 return nullptr;
312 }
313
314 static constexpr int_type not_eof(int_type c) noexcept
315 {
316 // TODO: implement
317 return int_type{};
318 }
319
320 static constexpr char_type to_char_type(int_type c) noexcept
321 {
322 return static_cast<char_type>(c);
323 }
324
325 static constexpr int_type to_int_type(char_type c) noexcept
326 {
327 return static_cast<int_type>(c);
328 }
329
330 static constexpr bool eq_int_type(int_type c1, int_type c2) noexcept
331 {
332 return c1 == c2;
333 }
334
335 static constexpr int_type eof() noexcept
336 {
337 return static_cast<int_type>(EOF);
338 }
339 };
340
341 template<>
342 struct char_traits<wchar_t>
343 {
344 using char_type = wchar_t;
345 using int_type = wint_t;
346 using off_type = streamoff;
347 using pos_type = wstreampos;
348 /* using state_type = mbstate_t; */
349
350 static void assign(char_type& c1, const char_type& c2) noexcept
351 {
352 c1 = c2;
353 }
354
355 static constexpr bool eq(char_type c1, char_type c2) noexcept
356 {
357 return c1 == c2;
358 }
359
360 static constexpr bool lt(char_type c1, char_type c2) noexcept
361 {
362 return c1 < c2;
363 }
364
365 static int compare(const char_type* s1, const char_type* s2, size_t n)
366 {
367 // TODO: This function does not exits...
368 __unimplemented();
369 //return hel::wstr_lcmp(s1, s2, n);
370 return 0;
371 }
372
373 static size_t length(const char_type* s)
374 {
375 return hel::wstr_bytes(s);
376 }
377
378 static const char_type* find(const char_type* s, size_t n, const char_type& c)
379 {
380 size_t i{};
381 while (i++ < n)
382 {
383 if (s[i] == c)
384 return s + i;
385 }
386
387 return nullptr;
388 }
389
390 static char_type* move(char_type* s1, const char_type* s2, size_t n)
391 {
392 return static_cast<char_type*>(memmove(s1, s2, n * sizeof(wchar_t)));
393 }
394
395 static char_type* copy(char_type* s1, const char_type* s2, size_t n)
396 {
397 return static_cast<char_type*>(memcpy(s1, s2, n * sizeof(wchar_t)));
398 }
399
400 static char_type* assign(char_type* s, size_t n, char_type c)
401 {
402 return static_cast<char_type*>(memset(s, static_cast<int>(c), n * sizeof(wchar_t)));
403 }
404
405 static constexpr int_type not_eof(int_type c) noexcept
406 {
407 if (!eq_int_type(c, eof()))
408 return c;
409 else
410 return to_int_type(L'a'); // We just need something that is not eof.
411 }
412
413 static constexpr char_type to_char_type(int_type c) noexcept
414 {
415 return static_cast<char_type>(c);
416 }
417
418 static constexpr int_type to_int_type(char_type c) noexcept
419 {
420 return static_cast<int_type>(c);
421 }
422
423 static constexpr bool eq_int_type(int_type c1, int_type c2) noexcept
424 {
425 return c1 == c2;
426 }
427
428 static constexpr int_type eof() noexcept
429 {
430 return static_cast<int_type>(EOF);
431 }
432 };
433
434 /**
435 * 21.4, class template basic_string:
436 */
437
438 template<class Char, class Traits, class Allocator>
439 class basic_string
440 {
441 public:
442 using traits_type = Traits;
443 using value_type = typename traits_type::char_type;
444 using allocator_type = Allocator;
445 using size_type = typename allocator_traits<allocator_type>::size_type;
446 using difference_type = typename allocator_traits<allocator_type>::difference_type;
447
448 using reference = value_type&;
449 using const_reference = const value_type&;
450 using pointer = typename allocator_traits<allocator_type>::pointer;
451 using const_pointer = typename allocator_traits<allocator_type>::const_pointer;
452
453 using iterator = pointer;
454 using const_iterator = const_pointer;
455 using reverse_iterator = std::reverse_iterator<iterator>;
456 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
457
458 static constexpr size_type npos = -1;
459
460 /**
461 * 21.4.2, construct/copy/destroy:
462 * TODO: tagged constructor that moves the char*
463 * and use that with asprintf in to_string
464 */
465
466 basic_string() noexcept
467 : basic_string(allocator_type{})
468 { /* DUMMY BODY */ }
469
470 explicit basic_string(const allocator_type& alloc)
471 : data_{}, size_{}, capacity_{}, allocator_{alloc}
472 {
473 /**
474 * Postconditions:
475 * data() = non-null copyable value that can have 0 added to it.
476 * size() = 0
477 * capacity() = unspecified
478 */
479 data_ = allocator_.allocate(default_capacity_);
480 capacity_ = default_capacity_;
481 }
482
483 basic_string(const basic_string& other)
484 : data_{}, size_{other.size_}, capacity_{other.capacity_},
485 allocator_{other.allocator_}
486 {
487 init_(other.data(), size_);
488 }
489
490 basic_string(basic_string&& other)
491 : data_{other.data_}, size_{other.size_},
492 capacity_{other.capacity_}, allocator_{move(other.allocator_)}
493 {
494 other.data_ = nullptr;
495 other.size_ = 0;
496 other.capacity_ = 0;
497 }
498
499 basic_string(const basic_string& other, size_type pos, size_type n = npos,
500 const allocator_type& alloc = allocator_type{})
501 : data_{}, size_{}, capacity_{}, allocator_{alloc}
502 {
503 // TODO: if pos < other.size() throw out_of_range.
504 auto len = min(n, other.size() - pos);
505 init_(other.data() + pos, len);
506 }
507
508 basic_string(const value_type* str, size_type n, const allocator_type& alloc = allocator_type{})
509 : data_{}, size_{n}, capacity_{n}, allocator_{alloc}
510 {
511 init_(str, size_);
512 }
513
514 basic_string(const value_type* str, const allocator_type& alloc = allocator_type{})
515 : data_{}, size_{}, capacity_{}, allocator_{alloc}
516 {
517 init_(str, traits_type::length(str));
518 }
519
520 basic_string(size_type n, value_type c, const allocator_type& alloc = allocator_type{})
521 : data_{}, size_{n}, capacity_{n}, allocator_{alloc}
522 {
523 data_ = allocator_.allocate(capacity_);
524 for (size_type i = 0; i < size_; ++i)
525 traits_type::assign(data_[i], c);
526 ensure_null_terminator_();
527 }
528
529 template<class InputIterator>
530 basic_string(InputIterator first, InputIterator last,
531 const allocator_type& alloc = allocator_type{})
532 : data_{}, size_{}, capacity_{}, allocator_{alloc}
533 {
534 if constexpr (is_integral<InputIterator>::value)
535 { // Required by the standard.
536 size_ = static_cast<size_type>(first);
537 capacity_ = size_;
538 data_ = allocator_.allocate(capacity_);
539
540 for (size_type i = 0; i < size_; ++i)
541 traits_type::assign(data_[i], static_cast<value_type>(last));
542 ensure_null_terminator_();
543 }
544 else
545 {
546 auto len = static_cast<size_type>(last - first);
547 init_(first, len);
548 }
549 }
550
551 basic_string(initializer_list<value_type> init, const allocator_type& alloc = allocator_type{})
552 : basic_string{init.begin(), init.size(), alloc}
553 { /* DUMMY BODY */ }
554
555 basic_string(const basic_string& other, const allocator_type& alloc)
556 : data_{}, size_{other.size_}, capacity_{other.capacity_}, allocator_{alloc}
557 {
558 init_(other.data(), size_);
559 }
560
561 basic_string(basic_string&& other, const allocator_type& alloc)
562 : data_{other.data_}, size_{other.size_}, capacity_{other.capacity_}, allocator_{alloc}
563 {
564 other.data_ = nullptr;
565 other.size_ = 0;
566 other.capacity_ = 0;
567 }
568
569 ~basic_string()
570 {
571 allocator_.deallocate(data_, capacity_);
572 }
573
574 basic_string& operator=(const basic_string& other)
575 {
576 if (this != &other)
577 {
578 basic_string tmp{other};
579 swap(tmp);
580 }
581
582 return *this;
583 }
584
585 basic_string& operator=(basic_string&& other)
586 noexcept(allocator_traits<allocator_type>::propagate_on_container_move_assignment::value ||
587 allocator_traits<allocator_type>::is_always_equal::value)
588 {
589 if (this != &other)
590 swap(other);
591
592 return *this;
593 }
594
595 basic_string& operator=(const value_type* other)
596 {
597 *this = basic_string{other};
598
599 return *this;
600 }
601
602 basic_string& operator=(value_type c)
603 {
604 *this = basic_string{1, c};
605
606 return *this;
607 }
608
609 basic_string& operator=(initializer_list<value_type> init)
610 {
611 *this = basic_string{init};
612
613 return *this;
614 }
615
616 /**
617 * 21.4.3, iterators:
618 */
619
620 iterator begin() noexcept
621 {
622 return &data_[0];
623 }
624
625 const_iterator begin() const noexcept
626 {
627 return &data_[0];
628 }
629
630 iterator end() noexcept
631 {
632 return begin() + size_;
633 }
634
635 const_iterator end() const noexcept
636 {
637 return begin() + size_;
638 }
639
640 reverse_iterator rbegin() noexcept
641 {
642 return make_reverse_iterator(end());
643 }
644
645 const_reverse_iterator rbegin() const noexcept
646 {
647 return make_reverse_iterator(cend());
648 }
649
650 reverse_iterator rend() noexcept
651 {
652 return make_reverse_iterator(begin());
653 }
654
655 const_reverse_iterator rend() const noexcept
656 {
657 return make_reverse_iterator(cbegin());
658 }
659
660 const_iterator cbegin() const noexcept
661 {
662 return &data_[0];
663 }
664
665 const_iterator cend() const noexcept
666 {
667 return cbegin() + size_;
668 }
669
670 const_reverse_iterator crbegin() const noexcept
671 {
672 return rbegin();
673 }
674
675 const_reverse_iterator crend() const noexcept
676 {
677 return rend();
678 }
679
680 /**
681 * 21.4.4, capacity:
682 */
683
684 size_type size() const noexcept
685 {
686 return size_;
687 }
688
689 size_type length() const noexcept
690 {
691 return size();
692 }
693
694 size_type max_size() const noexcept
695 {
696 return 0x7FFF; // TODO: just temporary
697 /* return allocator_traits<allocator_type>::max_size(allocator_); */
698 }
699
700 void resize(size_type new_size, value_type c)
701 {
702 // TODO: if new_size > max_size() throw length_error.
703 if (new_size > size_)
704 {
705 ensure_free_space_(new_size - size_ + 1);
706 for (size_type i = size_; i < new_size; ++i)
707 traits_type::assign(data_[i], i);
708 }
709
710 size_ = new_size;
711 ensure_null_terminator_();
712 }
713
714 void resize(size_type new_size)
715 {
716 resize(new_size, value_type{});
717 }
718
719 size_type capacity() const noexcept
720 {
721 return capacity_;
722 }
723
724 void reserve(size_type new_capacity = 0)
725 {
726 // TODO: if new_capacity > max_size() throw
727 // length_error (this function shall have no
728 // effect in such case)
729 if (new_capacity > capacity_)
730 resize_with_copy_(size_, new_capacity);
731 else if (new_capacity < capacity_)
732 shrink_to_fit(); // Non-binding request, but why not.
733 }
734
735 void shrink_to_fit()
736 {
737 if (size_ != capacity_)
738 resize_with_copy_(size_, capacity_);
739 }
740
741 void clear() noexcept
742 {
743 size_ = 0;
744 }
745
746 bool empty() const noexcept
747 {
748 return size_ == 0;
749 }
750
751 /**
752 * 21.4.5, element access:
753 */
754
755 const_reference operator[](size_type idx) const
756 {
757 return data_[idx];
758 }
759
760 reference operator[](size_type idx)
761 {
762 return data_[idx];
763 }
764
765 const_reference at(size_type idx) const
766 {
767 // TODO: bounds checking
768 return data_[idx];
769 }
770
771 reference at(size_type idx)
772 {
773 // TODO: bounds checking
774 return data_[idx];
775 }
776
777 const_reference front() const
778 {
779 return at(0);
780 }
781
782 reference front()
783 {
784 return at(0);
785 }
786
787 const_reference back() const
788 {
789 return at(size_ - 1);
790 }
791
792 reference back()
793 {
794 return at(size_ - 1);
795 }
796
797 /**
798 * 21.4.6, modifiers:
799 */
800
801 basic_string& operator+=(const basic_string& str)
802 {
803 return append(str);
804 }
805
806 basic_string& operator+=(const value_type* str)
807 {
808 return append(str);
809 }
810
811 basic_string& operator+=(value_type c)
812 {
813 push_back(c);
814 return *this;
815 }
816
817 basic_string& operator+=(initializer_list<value_type> init)
818 {
819 return append(init.begin(), init.size());
820 }
821
822 basic_string& append(const basic_string& str)
823 {
824 return append(str.data(), str.size());
825 }
826
827 basic_string& append(const basic_string& str, size_type pos,
828 size_type n = npos)
829 {
830 if (pos < str.size())
831 {
832 auto len = min(n, str.size() - pos);
833
834 return append(str.data() + pos, len);
835 }
836 // TODO: Else throw out_of_range.
837 }
838
839 basic_string& append(const value_type* str, size_type n)
840 {
841 // TODO: if (size_ + n > max_size()) throw length_error
842 ensure_free_space_(n);
843 traits_type::copy(data_ + size(), str, n);
844 size_ += n;
845 ensure_null_terminator_();
846
847 return *this;
848 }
849
850 basic_string& append(const value_type* str)
851 {
852 return append(str, traits_type::length(str));
853 }
854
855 basic_string& append(size_type n, value_type c)
856 {
857 return append(basic_string(n, c));
858 }
859
860 template<class InputIterator>
861 basic_string& append(InputIterator first, InputIterator last)
862 {
863 return append(basic_string(first, last));
864 }
865
866 basic_string& append(initializer_list<value_type> init)
867 {
868 return append(init.begin(), init.size());
869 }
870
871 void push_back(value_type c)
872 {
873 ensure_free_space_(1);
874 traits_type::assign(data_[size_++], c);
875 ensure_null_terminator_();
876 }
877
878 basic_string& assign(const basic_string& str)
879 {
880 return assign(str, 0, npos);
881 }
882
883 basic_string& assign(basic_string&& str)
884 {
885 swap(str);
886
887 return *this;
888 }
889
890 basic_string& assign(const basic_string& str, size_type pos,
891 size_type n = npos)
892 {
893 if (pos < str.size())
894 {
895 auto len = min(n, str.size() - pos);
896 ensure_free_space_(len);
897
898 return assign(str.data() + pos, len);
899 }
900 // TODO: Else throw out_of_range.
901
902 return *this;
903 }
904
905 basic_string& assign(const value_type* str, size_type n)
906 {
907 // TODO: if (n > max_size()) throw length_error.
908 resize_without_copy_(n);
909 traits_type::copy(begin(), str, n);
910 size_ = n;
911 ensure_null_terminator_();
912
913 return *this;
914 }
915
916 basic_string& assign(const value_type* str)
917 {
918 return assign(str, traits_type::length(str));
919 }
920
921 basic_string& assign(size_type n, value_type c)
922 {
923 return assign(basic_string(n, c));
924 }
925
926 template<class InputIterator>
927 basic_string& assign(InputIterator first, InputIterator last)
928 {
929 return assign(basic_string(first, last));
930 }
931
932 basic_string& assign(initializer_list<value_type> init)
933 {
934 return assign(init.begin(), init.size());
935 }
936
937 basic_string& insert(size_type pos, const basic_string& str)
938 {
939 // TODO: if (pos > str.size()) throw out_of_range.
940 return insert(pos, str.data(), str.size());
941 }
942
943 basic_string& insert(size_type pos1, const basic_string& str,
944 size_type pos2, size_type n = npos)
945 {
946 // TODO: if (pos1 > size() or pos2 > str.size()) throw
947 // out_of_range.
948 auto len = min(n, str.size() - pos2);
949
950 return insert(pos1, str.data() + pos2, len);
951 }
952
953 basic_string& insert(size_type pos, const value_type* str, size_type n)
954 {
955 // TODO: throw out_of_range if pos > size()
956 // TODO: throw length_error if size() + n > max_size()
957 ensure_free_space_(n);
958
959 copy_backward_(begin() + pos, end(), end() + n);
960 copy_(str, str + n, begin() + pos);
961 size_ += n;
962
963 ensure_null_terminator_();
964 return *this;
965 }
966
967 basic_string& insert(size_type pos, const value_type* str)
968 {
969 return insert(pos, str, traits_type::length(str));
970 }
971
972 basic_string& insert(size_type pos, size_type n, value_type c)
973 {
974 return insert(pos, basic_string(n, c));
975 }
976
977 iterator insert(const_iterator pos, value_type c)
978 {
979 auto idx = static_cast<size_type>(pos - begin());
980
981 ensure_free_space_(1);
982 copy_backward_(begin() + idx, end(), end() + 1);
983 traits_type::assign(data_[idx], c);
984
985 ++size_;
986 ensure_null_terminator_();
987
988 return begin() + idx;
989 }
990
991 iterator insert(const_iterator pos, size_type n, value_type c)
992 {
993 if (n == 0)
994 return const_cast<iterator>(pos);
995
996 auto idx = static_cast<size_type>(pos - begin());
997
998 ensure_free_space_(n);
999 copy_backward_(begin() + idx, end(), end() + n);
1000
1001 auto it = begin() + idx;
1002 for (size_type i = 0; i < n; ++i)
1003 traits_type::assign(*it++, c);
1004 size_ += n;
1005 ensure_null_terminator_();
1006
1007 return begin() + idx;
1008 }
1009
1010 template<class InputIterator>
1011 iterator insert(const_iterator pos, InputIterator first,
1012 InputIterator last)
1013 {
1014 if (first == last)
1015 return const_cast<iterator>(pos);
1016
1017 auto idx = static_cast<size_type>(pos - begin());
1018 auto str = basic_string{first, last};
1019 insert(idx, str);
1020
1021 return begin() + idx;
1022 }
1023
1024 iterator insert(const_iterator pos, initializer_list<value_type> init)
1025 {
1026 return insert(pos, init.begin(), init.end());
1027 }
1028
1029 basic_string& erase(size_type pos = 0, size_type n = npos)
1030 {
1031 auto len = min(n, size_ - pos);
1032 copy_(begin() + pos + n, end(), begin() + pos);
1033 size_ -= len;
1034 ensure_null_terminator_();
1035
1036 return *this;
1037 }
1038
1039 iterator erase(const_iterator pos)
1040 {
1041 auto idx = static_cast<size_type>(pos - cbegin());
1042 erase(idx, 1);
1043
1044 return begin() + idx;
1045 }
1046
1047 iterator erase(const_iterator first, const_iterator last)
1048 {
1049 auto idx = static_cast<size_type>(first - cbegin());
1050 auto count = static_cast<size_type>(last - first);
1051 erase(idx, count);
1052
1053 return begin() + idx;
1054 }
1055
1056 void pop_back()
1057 {
1058 --size_;
1059 ensure_null_terminator_();
1060 }
1061
1062 basic_string& replace(size_type pos, size_type n, const basic_string& str)
1063 {
1064 // TODO: throw out_of_range if pos > size()
1065 return replace(pos, n, str.data(), str.size());
1066 }
1067
1068 basic_string& replace(size_type pos1, size_type n1, const basic_string& str,
1069 size_type pos2, size_type n2 = npos)
1070 {
1071 // TODO: throw out_of_range if pos1 > size() or pos2 > str.size()
1072 auto len = min(n2, str.size() - pos2);
1073 return replace(pos1, n1, str.data() + pos2, len);
1074 }
1075
1076 basic_string& replace(size_type pos, size_type n1, const value_type* str,
1077 size_type n2)
1078 {
1079 // TODO: throw out_of_range if pos > size()
1080 // TODO: if size() - len > max_size() - n2 throw length_error
1081 auto len = min(n1, size_ - pos);
1082
1083 basic_string tmp{};
1084 tmp.resize_without_copy_(size_ - len + n2);
1085
1086 // Prefix.
1087 copy_(begin(), begin() + pos, tmp.begin());
1088
1089 // Substitution.
1090 traits_type::copy(tmp.begin() + pos, str, n2);
1091
1092 // Suffix.
1093 copy_(begin() + pos + len, end(), tmp.begin() + pos + n2);
1094
1095 tmp.size_ = size_ - len + n2;
1096 swap(tmp);
1097 return *this;
1098 }
1099
1100 basic_string& replace(size_type pos, size_type n, const value_type* str)
1101 {
1102 return replace(pos, n, str, traits_type::length(str));
1103 }
1104
1105 basic_string& replace(size_type pos, size_type n1, size_type n2,
1106 value_type c)
1107 {
1108 return replace(pos, n1, basic_string(n2, c));
1109 }
1110
1111 basic_string& replace(const_iterator i1, const_iterator i2,
1112 const basic_string& str)
1113 {
1114 return replace(i1 - begin(), i2 - i1, str);
1115 }
1116
1117 basic_string& replace(const_iterator i1, const_iterator i2,
1118 const value_type* str, size_type n)
1119 {
1120 return replace(i1 - begin(), i2 - i1, str, n);
1121 }
1122
1123 basic_string& replace(const_iterator i1, const_iterator i2,
1124 const value_type* str)
1125 {
1126 return replace(i1 - begin(), i2 - i1, str, traits_type::length(str));
1127 }
1128
1129 basic_string& replace(const_iterator i1, const_iterator i2,
1130 size_type n, value_type c)
1131 {
1132 return replace(i1 - begin(), i2 - i1, basic_string(n, c));
1133 }
1134
1135 template<class InputIterator>
1136 basic_string& replace(const_iterator i1, const_iterator i2,
1137 InputIterator j1, InputIterator j2)
1138 {
1139 return replace(i1 - begin(), i2 - i1, basic_string(j1, j2));
1140 }
1141
1142 basic_string& replace(const_iterator i1, const_iterator i2,
1143 initializer_list<value_type> init)
1144 {
1145 return replace(i1 - begin(), i2 - i1, init.begin(), init.size());
1146 }
1147
1148 size_type copy(value_type* str, size_type n, size_type pos = 0) const
1149 {
1150 auto len = min(n , size_ - pos);
1151 for (size_type i = 0; i < len; ++i)
1152 traits_type::assign(str[i], data_[pos + i]);
1153
1154 return len;
1155 }
1156
1157 void swap(basic_string& other)
1158 noexcept(allocator_traits<allocator_type>::propagate_on_container_swap::value ||
1159 allocator_traits<allocator_type>::is_always_equal::value)
1160 {
1161 std::swap(data_, other.data_);
1162 std::swap(size_, other.size_);
1163 std::swap(capacity_, other.capacity_);
1164 }
1165
1166 /**
1167 * 21.4.7, string operations:
1168 */
1169
1170 const value_type* c_str() const noexcept
1171 {
1172 return data_;
1173 }
1174
1175 const value_type* data() const noexcept
1176 {
1177 return data_;
1178 }
1179
1180 allocator_type get_allocator() const noexcept
1181 {
1182 return allocator_type{allocator_};
1183 }
1184
1185 /**
1186 * Note: The following find functions have 4 versions each:
1187 * (1) takes basic_string
1188 * (2) takes c string and length
1189 * (3) takes c string
1190 * (4) takes value_type
1191 * According to the C++14 standard, only (1) is marked as
1192 * noexcept and the other three return the first one with
1193 * a newly allocated strings (and thus cannot be noexcept).
1194 * However, allocating a new string results in memory
1195 * allocation and copying of the source and thus we have
1196 * decided to follow C++17 signatures of these functions
1197 * (i.e. all of them being marked as noexcept) and use
1198 * (2) for the actual implementation (and avoiding any
1199 * allocations or copying in the process and also providing
1200 * stronger guarantees to the user).
1201 */
1202
1203 size_type find(const basic_string& str, size_type pos = 0) const noexcept
1204 {
1205 return find(str.c_str(), pos, str.size());
1206 }
1207
1208 size_type find(const value_type* str, size_type pos, size_type len) const noexcept
1209 {
1210 if (empty() || len == 0 || len + pos > size())
1211 return npos;
1212
1213 size_type idx{pos};
1214
1215 while (idx + len < size_)
1216 {
1217 if (substr_starts_at_(idx, str, len))
1218 return idx;
1219 ++idx;
1220 }
1221
1222 return npos;
1223 }
1224
1225 size_type find(const value_type* str, size_type pos = 0) const noexcept
1226 {
1227 return find(str, pos, traits_type::length(str));
1228 }
1229
1230 size_type find(value_type c, size_type pos = 0) const noexcept
1231 {
1232 if (empty())
1233 return npos;
1234
1235 for (size_type i = pos; i < size_; ++i)
1236 {
1237 if (traits_type::eq(c, data_[i]))
1238 return i;
1239 }
1240
1241 return npos;
1242 }
1243
1244 size_type rfind(const basic_string& str, size_type pos = npos) const noexcept
1245 {
1246 return rfind(str.c_str(), pos, str.size());
1247 }
1248
1249 size_type rfind(const value_type* str, size_type pos, size_type len) const noexcept
1250 {
1251 if (empty() || len == 0 || len + pos > size())
1252 return npos;
1253
1254 size_type idx{min(pos, size_ - 1) + 1};
1255
1256 while (idx > 0)
1257 {
1258 if (substr_starts_at_(idx - 1, str, len))
1259 return idx - 1;
1260 --idx;
1261 }
1262
1263 return npos;
1264 }
1265
1266 size_type rfind(const value_type* str, size_type pos = npos) const noexcept
1267 {
1268 return rfind(str, pos, traits_type::length(str));
1269 }
1270
1271 size_type rfind(value_type c, size_type pos = npos) const noexcept
1272 {
1273 if (empty())
1274 return npos;
1275
1276 for (size_type i = min(pos + 1, size_ - 1) + 1; i > 0; --i)
1277 {
1278 if (traits_type::eq(c, data_[i - 1]))
1279 return i - 1;
1280 }
1281
1282 return npos;
1283 }
1284
1285 size_type find_first_of(const basic_string& str, size_type pos = 0) const noexcept
1286 {
1287 return find_first_of(str.c_str(), pos, str.size());
1288 }
1289
1290 size_type find_first_of(const value_type* str, size_type pos, size_type len) const noexcept
1291 {
1292 if (empty() || len == 0 || pos >= size())
1293 return npos;
1294
1295 size_type idx{pos};
1296
1297 while (idx < size_)
1298 {
1299 if (is_any_of_(idx, str, len))
1300 return idx;
1301 ++idx;
1302 }
1303
1304 return npos;
1305 }
1306
1307 size_type find_first_of(const value_type* str, size_type pos = 0) const noexcept
1308 {
1309 return find_first_of(str, pos, traits_type::length(str));
1310 }
1311
1312 size_type find_first_of(value_type c, size_type pos = 0) const noexcept
1313 {
1314 return find(c, pos);
1315 }
1316
1317 size_type find_last_of(const basic_string& str, size_type pos = npos) const noexcept
1318 {
1319 return find_last_of(str.c_str(), pos, str.size());
1320 }
1321
1322 size_type find_last_of(const value_type* str, size_type pos, size_type len) const noexcept
1323 {
1324 if (empty() || len == 0)
1325 return npos;
1326
1327 for (size_type i = min(pos, size_ - 1) + 1; i > 0; --i)
1328 {
1329 if (is_any_of_(i - 1, str, len))
1330 return i - 1;
1331 }
1332
1333 return npos;
1334 }
1335
1336 size_type find_last_of(const value_type* str, size_type pos = npos) const noexcept
1337 {
1338 return find_last_of(str, pos, traits_type::length(str));
1339 }
1340
1341 size_type find_last_of(value_type c, size_type pos = npos) const noexcept
1342 {
1343 return rfind(c, pos);
1344 }
1345
1346 size_type find_first_not_of(const basic_string& str, size_type pos = 0) const noexcept
1347 {
1348 return find_first_not_of(str.c_str(), pos, str.size());
1349 }
1350
1351 size_type find_first_not_of(const value_type* str, size_type pos, size_type len) const noexcept
1352 {
1353 if (empty() || pos >= size())
1354 return npos;
1355
1356 size_type idx{pos};
1357
1358 while (idx < size_)
1359 {
1360 if (!is_any_of_(idx, str, len))
1361 return idx;
1362 ++idx;
1363 }
1364
1365 return npos;
1366 }
1367
1368 size_type find_first_not_of(const value_type* str, size_type pos = 0) const noexcept
1369 {
1370 return find_first_not_of(str, pos, traits_type::length(str));
1371 }
1372
1373 size_type find_first_not_of(value_type c, size_type pos = 0) const noexcept
1374 {
1375 if (empty())
1376 return npos;
1377
1378 for (size_type i = pos; i < size_; ++i)
1379 {
1380 if (!traits_type::eq(c, data_[i]))
1381 return i;
1382 }
1383
1384 return npos;
1385 }
1386
1387 size_type find_last_not_of(const basic_string& str, size_type pos = npos) const noexcept
1388 {
1389 return find_last_not_of(str.c_str(), pos, str.size());
1390 }
1391
1392 size_type find_last_not_of(const value_type* str, size_type pos, size_type len) const noexcept
1393 {
1394 if (empty())
1395 return npos;
1396
1397 for (size_type i = min(pos, size_ - 1) + 1; i > 0; --i)
1398 {
1399 if (!is_any_of_(i - 1, str, len))
1400 return i - 1;
1401 }
1402
1403 return npos;
1404 }
1405
1406 size_type find_last_not_of(const value_type* str, size_type pos = npos) const noexcept
1407 {
1408 return find_last_not_of(str, pos, traits_type::length(str));
1409 }
1410
1411 size_type find_last_not_of(value_type c, size_type pos = npos) const noexcept
1412 {
1413 if (empty())
1414 return npos;
1415
1416 pos = min(pos, size_ - 1);
1417
1418 for (size_type i = min(pos, size_ - 1) + 1; i > 1; --i)
1419 {
1420 if (!traits_type::eq(c, data_[i - 1]))
1421 return i - 1;
1422 }
1423
1424 return npos;
1425 }
1426
1427 basic_string substr(size_type pos = 0, size_type n = npos) const
1428 {
1429 // TODO: throw out_of_range if pos > size().
1430 auto len = min(n, size_ - pos);
1431 return basic_string{data() + pos, len};
1432 }
1433
1434 int compare(const basic_string& other) const noexcept
1435 {
1436 auto len = min(size(), other.size());
1437 auto comp = traits_type::compare(data_, other.data(), len);
1438
1439 if (comp != 0)
1440 return comp;
1441 else if (size() == other.size())
1442 return 0;
1443 else if (size() > other.size())
1444 return 1;
1445 else
1446 return -1;
1447 }
1448
1449 int compare(size_type pos, size_type n, const basic_string& other) const
1450 {
1451 return basic_string{*this, pos, n}.compare(other);
1452 }
1453
1454 int compare(size_type pos1, size_type n1, const basic_string& other,
1455 size_type pos2, size_type n2 = npos) const
1456 {
1457 return basic_string{*this, pos1, n1}.compare(basic_string{other, pos2, n2});
1458 }
1459
1460 int compare(const value_type* other) const
1461 {
1462 return compare(basic_string(other));
1463 }
1464
1465 int compare(size_type pos, size_type n, const value_type* other) const
1466 {
1467 return basic_string{*this, pos, n}.compare(basic_string{other});
1468 }
1469
1470 int compare(size_type pos, size_type n1,
1471 const value_type* other, size_type n2) const
1472 {
1473 return basic_string{*this, pos, n1}.compare(basic_string{other, n2});
1474 }
1475
1476 private:
1477 value_type* data_;
1478 size_type size_;
1479 size_type capacity_;
1480 allocator_type allocator_;
1481
1482 template<class C, class T, class A>
1483 friend class basic_stringbuf;
1484
1485 /**
1486 * Arbitrary value, standard just requires
1487 * data() to have some capacity.
1488 * (Well, we could've done data_ = &data_ and
1489 * set capacity to 0, but that would be too cryptic.)
1490 */
1491 static constexpr size_type default_capacity_{4};
1492
1493 void init_(const value_type* str, size_type size)
1494 {
1495 if (data_)
1496 allocator_.deallocate(data_, capacity_);
1497
1498 size_ = size;
1499 capacity_ = size + 1;
1500
1501 data_ = allocator_.allocate(capacity_);
1502 traits_type::copy(data_, str, size);
1503 ensure_null_terminator_();
1504 }
1505
1506 size_type next_capacity_(size_type hint = 0) const noexcept
1507 {
1508 if (hint != 0)
1509 return max(capacity_ * 2, hint);
1510 else
1511 return max(capacity_ * 2, size_type{2u});
1512 }
1513
1514 void ensure_free_space_(size_type n)
1515 {
1516 /**
1517 * Note: We cannot use reserve like we
1518 * did in vector, because in string
1519 * reserve can cause shrinking.
1520 */
1521 if (size_ + 1 + n > capacity_)
1522 resize_with_copy_(size_, max(size_ + 1 + n, next_capacity_()));
1523 }
1524
1525 void resize_without_copy_(size_type capacity)
1526 {
1527 if (data_)
1528 allocator_.deallocate(data_, capacity_);
1529
1530 data_ = allocator_.allocate(capacity);
1531 size_ = 0;
1532 capacity_ = capacity;
1533 ensure_null_terminator_();
1534 }
1535
1536 void resize_with_copy_(size_type size, size_type capacity)
1537 {
1538 if(capacity_ == 0 || capacity_ < capacity)
1539 {
1540 auto new_data = allocator_.allocate(capacity);
1541
1542 auto to_copy = min(size, size_);
1543 traits_type::move(new_data, data_, to_copy);
1544
1545 std::swap(data_, new_data);
1546
1547 allocator_.deallocate(new_data, capacity_);
1548 }
1549
1550 capacity_ = capacity;
1551 size_ = size;
1552 ensure_null_terminator_();
1553 }
1554
1555 template<class Iterator1, class Iterator2>
1556 Iterator2 copy_(Iterator1 first, Iterator1 last,
1557 Iterator2 result)
1558 {
1559 while (first != last)
1560 traits_type::assign(*result++, *first++);
1561
1562 return result;
1563 }
1564
1565 template<class Iterator1, class Iterator2>
1566 Iterator2 copy_backward_(Iterator1 first, Iterator1 last,
1567 Iterator2 result)
1568 {
1569 while (last != first)
1570 traits_type::assign(*--result, *--last);
1571
1572 return result;
1573 }
1574
1575 void ensure_null_terminator_()
1576 {
1577 value_type c{};
1578 traits_type::assign(data_[size_], c);
1579 }
1580
1581 bool is_any_of_(size_type idx, const value_type* str, size_type len) const
1582 {
1583 for (size_type i = 0; i < len; ++i)
1584 {
1585 if (traits_type::eq(data_[idx], str[i]))
1586 return true;
1587 }
1588
1589 return false;
1590 }
1591
1592 bool substr_starts_at_(size_type idx, const value_type* str, size_type len) const
1593 {
1594 size_type i{};
1595 for (i = 0; i < len; ++i)
1596 {
1597 if (!traits_type::eq(data_[idx + i], str[i]))
1598 break;
1599 }
1600
1601 return i == len;
1602 }
1603 };
1604
1605 using string = basic_string<char>;
1606 using u16string = basic_string<char16_t>;
1607 using u32string = basic_string<char32_t>;
1608 using wstring = basic_string<wchar_t>;
1609
1610 /**
1611 * 21.4.8, basic_string non-member functions:
1612 */
1613
1614 /**
1615 * 21.4.8.1, operator+:
1616 */
1617
1618 template<class Char, class Traits, class Allocator>
1619 basic_string<Char, Traits, Allocator>
1620 operator+(const basic_string<Char, Traits, Allocator>& lhs,
1621 const basic_string<Char, Traits, Allocator>& rhs)
1622 {
1623 return basic_string<Char, Traits, Allocator>{lhs}.append(rhs);
1624 }
1625
1626 template<class Char, class Traits, class Allocator>
1627 basic_string<Char, Traits, Allocator>
1628 operator+(basic_string<Char, Traits, Allocator>&& lhs,
1629 const basic_string<Char, Traits, Allocator>& rhs)
1630 {
1631 return move(lhs.append(rhs));
1632 }
1633
1634 template<class Char, class Traits, class Allocator>
1635 basic_string<Char, Traits, Allocator>
1636 operator+(const basic_string<Char, Traits, Allocator>& lhs,
1637 basic_string<Char, Traits, Allocator>&& rhs)
1638 {
1639 return move(rhs.insert(0, lhs));
1640 }
1641
1642 template<class Char, class Traits, class Allocator>
1643 basic_string<Char, Traits, Allocator>
1644 operator+(basic_string<Char, Traits, Allocator>&& lhs,
1645 basic_string<Char, Traits, Allocator>&& rhs)
1646 {
1647 return move(lhs.append(rhs));
1648 }
1649
1650 template<class Char, class Traits, class Allocator>
1651 basic_string<Char, Traits, Allocator>
1652 operator+(const Char* lhs,
1653 const basic_string<Char, Traits, Allocator>& rhs)
1654 {
1655 return basic_string<Char, Traits, Allocator>{lhs} + rhs;
1656 }
1657
1658 template<class Char, class Traits, class Allocator>
1659 basic_string<Char, Traits, Allocator>
1660 operator+(const Char* lhs,
1661 basic_string<Char, Traits, Allocator>&& rhs)
1662 {
1663 return move(rhs.insert(0, lhs));
1664 }
1665
1666 template<class Char, class Traits, class Allocator>
1667 basic_string<Char, Traits, Allocator>
1668 operator+(Char lhs,
1669 const basic_string<Char, Traits, Allocator>& rhs)
1670 {
1671 return basic_string<Char, Traits, Allocator>{1, lhs}.append(rhs);
1672 }
1673
1674 template<class Char, class Traits, class Allocator>
1675 basic_string<Char, Traits, Allocator>
1676 operator+(Char lhs,
1677 basic_string<Char, Traits, Allocator>&& rhs)
1678 {
1679 return move(rhs.insert(0, 1, lhs));
1680 }
1681
1682 template<class Char, class Traits, class Allocator>
1683 basic_string<Char, Traits, Allocator>
1684 operator+(const basic_string<Char, Traits, Allocator>& lhs,
1685 const Char* rhs)
1686 {
1687 return lhs + basic_string<Char, Traits, Allocator>{rhs};
1688 }
1689
1690 template<class Char, class Traits, class Allocator>
1691 basic_string<Char, Traits, Allocator>
1692 operator+(basic_string<Char, Traits, Allocator>&& lhs,
1693 const Char* rhs)
1694 {
1695 return move(lhs.append(rhs));
1696 }
1697
1698 template<class Char, class Traits, class Allocator>
1699 basic_string<Char, Traits, Allocator>
1700 operator+(const basic_string<Char, Traits, Allocator>& lhs,
1701 Char rhs)
1702 {
1703 return lhs + basic_string<Char, Traits, Allocator>{1, rhs};
1704 }
1705
1706 template<class Char, class Traits, class Allocator>
1707 basic_string<Char, Traits, Allocator>
1708 operator+(basic_string<Char, Traits, Allocator>&& lhs,
1709 Char rhs)
1710 {
1711 return move(lhs.append(1, rhs));
1712 }
1713
1714 /**
1715 * 21.4.8.2, operator==:
1716 */
1717
1718 template<class Char, class Traits, class Allocator>
1719 bool operator==(const basic_string<Char, Traits, Allocator>& lhs,
1720 const basic_string<Char, Traits, Allocator>& rhs) noexcept
1721 {
1722 return lhs.compare(rhs) == 0;
1723 }
1724
1725 template<class Char, class Traits, class Allocator>
1726 bool operator==(const Char* lhs,
1727 const basic_string<Char, Traits, Allocator>& rhs)
1728 {
1729 return rhs == lhs;
1730 }
1731
1732 template<class Char, class Traits, class Allocator>
1733 bool operator==(const basic_string<Char, Traits, Allocator>& lhs,
1734 const Char* rhs)
1735 {
1736 return lhs.compare(rhs) == 0;
1737 }
1738
1739 /**
1740 * 21.4.8.3, operator!=:
1741 */
1742
1743 template<class Char, class Traits, class Allocator>
1744 bool operator!=(const basic_string<Char, Traits, Allocator>& lhs,
1745 const basic_string<Char, Traits, Allocator>& rhs) noexcept
1746 {
1747 return !(lhs == rhs);
1748 }
1749
1750 template<class Char, class Traits, class Allocator>
1751 bool operator!=(const Char* lhs,
1752 const basic_string<Char, Traits, Allocator>& rhs)
1753 {
1754 return rhs != lhs;
1755 }
1756
1757 template<class Char, class Traits, class Allocator>
1758 bool operator!=(const basic_string<Char, Traits, Allocator>& lhs,
1759 const Char* rhs)
1760 {
1761 return lhs.compare(rhs) != 0;
1762 }
1763
1764 /**
1765 * 21.4.8.4, operator<:
1766 */
1767
1768 template<class Char, class Traits, class Allocator>
1769 bool operator<(const basic_string<Char, Traits, Allocator>& lhs,
1770 const basic_string<Char, Traits, Allocator>& rhs) noexcept
1771 {
1772 return lhs.compare(rhs) < 0;
1773 }
1774
1775 template<class Char, class Traits, class Allocator>
1776 bool operator<(const Char* lhs,
1777 const basic_string<Char, Traits, Allocator>& rhs)
1778 {
1779 return rhs.compare(lhs) > 0;
1780 }
1781
1782 template<class Char, class Traits, class Allocator>
1783 bool operator<(const basic_string<Char, Traits, Allocator>& lhs,
1784 const Char* rhs)
1785 {
1786 return lhs.compare(rhs) < 0;
1787 }
1788
1789 /**
1790 * 21.4.8.5, operator>:
1791 */
1792
1793 template<class Char, class Traits, class Allocator>
1794 bool operator>(const basic_string<Char, Traits, Allocator>& lhs,
1795 const basic_string<Char, Traits, Allocator>& rhs) noexcept
1796 {
1797 return lhs.compare(rhs) > 0;
1798 }
1799
1800 template<class Char, class Traits, class Allocator>
1801 bool operator>(const Char* lhs,
1802 const basic_string<Char, Traits, Allocator>& rhs)
1803 {
1804 return rhs.compare(lhs) < 0;
1805 }
1806
1807 template<class Char, class Traits, class Allocator>
1808 bool operator>(const basic_string<Char, Traits, Allocator>& lhs,
1809 const Char* rhs)
1810 {
1811 return lhs.compare(rhs) > 0;
1812 }
1813
1814 /**
1815 * 21.4.8.6, operator<=:
1816 */
1817
1818 template<class Char, class Traits, class Allocator>
1819 bool operator<=(const basic_string<Char, Traits, Allocator>& lhs,
1820 const basic_string<Char, Traits, Allocator>& rhs) noexcept
1821 {
1822 return lhs.compare(rhs) <= 0;
1823 }
1824
1825 template<class Char, class Traits, class Allocator>
1826 bool operator<=(const Char* lhs,
1827 const basic_string<Char, Traits, Allocator>& rhs)
1828 {
1829 return rhs.compare(lhs) >= 0;
1830 }
1831
1832 template<class Char, class Traits, class Allocator>
1833 bool operator<=(const basic_string<Char, Traits, Allocator>& lhs,
1834 const Char* rhs)
1835 {
1836 return lhs.compare(rhs) <= 0;
1837 }
1838
1839 /**
1840 * 21.4.8.7, operator>=:
1841 */
1842
1843 template<class Char, class Traits, class Allocator>
1844 bool operator>=(const basic_string<Char, Traits, Allocator>& lhs,
1845 const basic_string<Char, Traits, Allocator>& rhs) noexcept
1846 {
1847 return lhs.compare(rhs) >= 0;
1848 }
1849
1850 template<class Char, class Traits, class Allocator>
1851 bool operator>=(const Char* lhs,
1852 const basic_string<Char, Traits, Allocator>& rhs)
1853 {
1854 return rhs.compare(lhs) <= 0;
1855 }
1856
1857 template<class Char, class Traits, class Allocator>
1858 bool operator>=(const basic_string<Char, Traits, Allocator>& lhs,
1859 const Char* rhs)
1860 {
1861 return lhs.compare(rhs) >= 0;
1862 }
1863
1864 /**
1865 * 21.4.8.8, swap:
1866 */
1867
1868 template<class Char, class Traits, class Allocator>
1869 void swap(basic_string<Char, Traits, Allocator>& lhs,
1870 basic_string<Char, Traits, Allocator>& rhs)
1871 noexcept(noexcept(lhs.swap(rhs)))
1872 {
1873 lhs.swap(rhs);
1874 }
1875
1876 /**
1877 * 21.5, numeric conversions:
1878 */
1879
1880 int stoi(const string& str, size_t* idx = nullptr, int base = 10);
1881 long stol(const string& str, size_t* idx = nullptr, int base = 10);
1882 unsigned long stoul(const string& str, size_t* idx = nullptr, int base = 10);
1883 long long stoll(const string& str, size_t* idx = nullptr, int base = 10);
1884 unsigned long long stoull(const string& str, size_t* idx = nullptr, int base = 10);
1885
1886 float stof(const string& str, size_t* idx = nullptr);
1887 double stod(const string& str, size_t* idx = nullptr);
1888 long double stold(const string& str, size_t* idx = nullptr);
1889
1890 string to_string(int val);
1891 string to_string(unsigned val);
1892 string to_string(long val);
1893 string to_string(unsigned long val);
1894 string to_string(long long val);
1895 string to_string(unsigned long long val);
1896 string to_string(float val);
1897 string to_string(double val);
1898 string to_string(long double val);
1899
1900 int stoi(const wstring& str, size_t* idx = nullptr, int base = 10);
1901 long stol(const wstring& str, size_t* idx = nullptr, int base = 10);
1902 unsigned long stoul(const wstring& str, size_t* idx = nullptr, int base = 10);
1903 long long stoll(const wstring& str, size_t* idx = nullptr, int base = 10);
1904 unsigned long long stoull(const wstring& str, size_t* idx = nullptr, int base = 10);
1905
1906 float stof(const wstring& str, size_t* idx = nullptr);
1907 double stod(const wstring& str, size_t* idx = nullptr);
1908 long double stold(const wstring& str, size_t* idx = nullptr);
1909
1910 wstring to_wstring(int val);
1911 wstring to_wstring(unsigned val);
1912 wstring to_wstring(long val);
1913 wstring to_wstring(unsigned long val);
1914 wstring to_wstring(long long val);
1915 wstring to_wstring(unsigned long long val);
1916 wstring to_wstring(float val);
1917 wstring to_wstring(double val);
1918 wstring to_wstring(long double val);
1919
1920 /**
1921 * 21.6, hash support:
1922 */
1923
1924 template<class>
1925 struct hash;
1926
1927 template<>
1928 struct hash<string>
1929 {
1930 size_t operator()(const string& str) const noexcept
1931 {
1932 size_t res{};
1933
1934 /**
1935 * Note: No need for fancy algorithms here,
1936 * std::hash is used for indexing, not
1937 * cryptography.
1938 */
1939 for (const auto& c: str)
1940 res = res * 5 + (res >> 3) + static_cast<size_t>(c);
1941
1942 return res;
1943 }
1944
1945 using argument_type = string;
1946 using result_type = size_t;
1947 };
1948
1949 template<>
1950 struct hash<wstring>
1951 {
1952 size_t operator()(const wstring& str) const noexcept
1953 {
1954 // TODO: implement
1955 __unimplemented();
1956 return size_t{};
1957 }
1958
1959 using argument_type = wstring;
1960 using result_type = size_t;
1961 };
1962
1963 // TODO: add those other 2 string types
1964
1965 /**
1966 * 21.7, suffix for basic_string literals:
1967 */
1968
1969 /**
1970 * Note: According to the standard, literal suffixes that do not
1971 * start with an underscore are reserved for future standardization,
1972 * but since we are implementing the standard, we're going to ignore it.
1973 * This should work (according to their documentation) work for clang,
1974 * but that should be tested.
1975 */
1976#pragma GCC diagnostic push
1977#pragma GCC diagnostic ignored "-Wliteral-suffix"
1978inline namespace literals {
1979inline namespace string_literals
1980{
1981 string operator "" s(const char* str, size_t len);
1982 u16string operator "" s(const char16_t* str, size_t len);
1983 u32string operator "" s(const char32_t* str, size_t len);
1984
1985 /* Problem: wchar_t == int in HelenOS, but standard forbids it.
1986 wstring operator "" s(const wchar_t* str, size_t len);
1987 */
1988}}
1989#pragma GCC diagnostic pop
1990}
1991
1992#endif
Note: See TracBrowser for help on using the repository browser.