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

ticket/834-toolchain-update topic/msim-upgrade topic/simplify-dev-export
Last change on this file since aaafcc8 was 1502c05, checked in by Jiří Zárevúcky <zarevucky.jiri@…>, 21 months ago

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