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

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

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