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

lfn serial ticket/834-toolchain-update topic/msim-upgrade topic/simplify-dev-export
Last change on this file since 7dcce0a was 7dcce0a, checked in by jxsvoboda <5887334+jxsvoboda@…>, 6 years ago

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