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

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

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