source: mainline/uspace/lib/cpp/include/impl/string.hpp@ a1c35cc

lfn serial ticket/834-toolchain-update topic/msim-upgrade topic/simplify-dev-export
Last change on this file since a1c35cc was edd2e61, checked in by Dzejrou <dzejrou@…>, 7 years ago

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