source: mainline/uspace/lib/cpp/include/impl/vector.hpp@ 79f35d40

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

cpp: std::vector::get_allocator now returns a copy for sure
  • Property mode set to 100644
File size: 18.9 KB
Line 
1/*
2 * Copyright (c) 2017 Jaroslav Jindrak
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *
9 * - Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * - Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * - The name of the author may not be used to endorse or promote products
15 * derived from this software without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28
29#ifndef LIBCPP_VECTOR
30#define LIBCPP_VECTOR
31
32#include <algorithm>
33#include <initializer_list>
34#include <iterator>
35#include <memory>
36#include <utility>
37
38namespace std
39{
40 /**
41 * 23.3.6, vector:
42 */
43
44 template<class T, class Allocator = allocator<T>>
45 class vector
46 {
47 public:
48 using value_type = T;
49 using reference = value_type&;
50 using const_reference = const value_type&;
51 using allocator_type = Allocator;
52 using size_type = size_t;
53 using difference_type = ptrdiff_t;
54 using pointer = typename allocator_traits<Allocator>::pointer;
55 using const_pointer = typename allocator_traits<Allocator>::pointer;
56 using iterator = pointer;
57 using const_iterator = const_pointer;
58 using reverse_iterator = std::reverse_iterator<iterator>;
59 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
60
61 vector() noexcept
62 : vector{Allocator{}}
63 { /* DUMMY BODY */ }
64
65 explicit vector(const Allocator& alloc)
66 : data_{nullptr}, size_{}, capacity_{},
67 allocator_{alloc}
68 { /* DUMMY BODY */ }
69
70 explicit vector(size_type n, const Allocator& alloc = Allocator{})
71 : data_{}, size_{n}, capacity_{n}, allocator_{alloc}
72 {
73 data_ = allocator_.allocate(capacity_);
74
75 for (size_type i = 0; i < size_; ++i)
76 allocator_traits<Allocator>::construct(allocator_, data_ + i);
77 }
78
79 vector(size_type n, const T& val, const Allocator& alloc = Allocator{})
80 : data_{}, size_{n}, capacity_{n}, allocator_{alloc}
81 {
82 data_ = allocator_.allocate(capacity_);
83
84 for (size_type i = 0; i < size_; ++i)
85 data_[i] = val;
86 }
87
88 template<class InputIterator>
89 vector(InputIterator first, InputIterator last,
90 const Allocator& alloc = Allocator{})
91 {
92 // TODO: research constraints and provide multiple
93 // implementations via enable_if
94 }
95
96 vector(const vector& other)
97 : data_{nullptr}, size_{other.size_}, capacity_{other.capacity_},
98 allocator_{other.allocator_}
99 {
100 data_ = allocator_.allocate(capacity_);
101
102 for (size_type i = 0; i < size_; ++i)
103 data_[i] = other.data_[i];
104 }
105
106 vector(vector&& other) noexcept
107 : data_{other.data_}, size_{other.size_}, capacity_{other.capacity_},
108 allocator_{move(other.allocator_)}
109 {
110 // other is guaranteed to be empty()
111 other.size_ = other.capacity_ = 0;
112 other.data_ = nullptr;
113 }
114
115 vector(const vector& other, const Allocator& alloc)
116 : data_{nullptr}, size_{other.size_}, capacity_{other.capacity_},
117 allocator_{alloc}
118 {
119 data_ = allocator_.allocate(capacity_);
120
121 for (size_type i = 0; i < size_; ++i)
122 data_[i] = other.data_[i];
123 }
124
125 vector(initializer_list<T> init, const Allocator& alloc = Allocator{})
126 : data_{nullptr}, size_{init.size()}, capacity_{init.size()},
127 allocator_{alloc}
128 {
129 data_ = allocator_.allocate(capacity_);
130
131 auto it = init.begin();
132 for (size_type i = 0; it != init.end(); ++i, ++it)
133 {
134 data_[i] = *it;
135 }
136 }
137
138 ~vector()
139 {
140 allocator_.deallocate(data_, capacity_);
141 }
142
143 vector& operator=(const vector& other)
144 {
145 vector tmp{other};
146 swap(tmp);
147
148 return *this;
149 }
150
151 vector& operator=(vector&& other)
152 noexcept(allocator_traits<Allocator>::propagate_on_container_move_assignment::value ||
153 allocator_traits<Allocator>::is_always_equal::value)
154 {
155 // TODO: implement
156 return *this;
157 }
158
159 vector& operator=(initializer_list<T> init)
160 {
161 vector tmp{init, allocator_};
162 swap(tmp);
163
164 return *this;
165 }
166
167 template<class InputIterator>
168 void assign(InputIterator first, InputIterator last)
169 {
170 vector tmp{first, last};
171 swap(tmp);
172 }
173
174 void assign(size_type size, const T& val)
175 {
176 // Parenthesies required to avoid initializer list
177 // construction.
178 vector tmp(size, val);
179 swap(tmp);
180 }
181
182 void assign(initializer_list<T> init)
183 {
184 vector tmp{init};
185 swap(tmp);
186 }
187
188 allocator_type get_allocator() const noexcept
189 {
190 return allocator_type{allocator_};
191 }
192
193 iterator begin() noexcept
194 {
195 return &data_[0];
196 }
197
198 const_iterator begin() const noexcept
199 {
200 return &data_[0];
201 }
202
203 iterator end() noexcept
204 {
205 return begin() + size_;
206 }
207
208 const_iterator end() const noexcept
209 {
210 return begin() + size_;
211 }
212
213 reverse_iterator rbegin() noexcept
214 {
215 return make_reverse_iterator(end());
216 }
217
218 const_reverse_iterator rbegin() const noexcept
219 {
220 return make_reverse_iterator(cend());
221 }
222
223 reverse_iterator rend() noexcept
224 {
225 return make_reverse_iterator(begin());
226 }
227
228 const_reverse_iterator rend() const noexcept
229 {
230 return make_reverse_iterator(cbegin());
231 }
232
233 const_iterator cbegin() const noexcept
234 {
235 return &data_[0];
236 }
237
238 const_iterator cend() const noexcept
239 {
240 return cbegin() + size_;
241 }
242
243 const_reverse_iterator rcbegin() const noexcept
244 {
245 return rbegin();
246 }
247
248 const_reverse_iterator rcend() const noexcept
249 {
250 return rend();
251 }
252
253 size_type size() const noexcept
254 {
255 return size_;
256 }
257
258 size_type max_size() const noexcept
259 {
260 return std::allocator_traits<Allocator>::max_size(allocator_);
261 }
262
263 void resize(size_type sz)
264 {
265 resize_with_copy_(size_, capacity_);
266 }
267
268 void resize(size_type sz, const value_type& val)
269 {
270 auto old_size = size_;
271 resize_with_copy_(sz, capacity_);
272
273 for (size_type i = old_size - 1; i < size_; ++i)
274 data_[i] = val;
275 }
276
277 size_type capacity() const noexcept
278 {
279 return capacity_;
280 }
281
282 bool empty() const noexcept
283 {
284 return size_ == 0;
285 }
286
287 void reserve(size_type new_capacity)
288 {
289 // TODO: if new_capacity > max_size() throw
290 // length_error (this function shall have no
291 // effect in such case)
292 if (new_capacity > capacity_)
293 resize_with_copy_(size_, new_capacity);
294 }
295
296 void shrink_to_fit()
297 {
298 resize_with_copy_(size_, size_);
299 }
300
301 reference operator[](size_type idx)
302 {
303 return data_[idx];
304 }
305
306 const_reference operator[](size_type idx) const
307 {
308 return data_[idx];
309 }
310
311 reference at(size_type idx)
312 {
313 // TODO: bounds checking
314 return data_[idx];
315 }
316
317 const_reference at(size_type idx) const
318 {
319 // TODO: bounds checking
320 return data_[idx];
321 }
322
323 reference front()
324 {
325 /**
326 * Note: Calling front/back on an empty container
327 * is undefined, we opted for at-like
328 * behavior to provide our users with means
329 * to protect their programs from accidental
330 * accesses to an empty vector.
331 */
332 return at(0);
333 }
334
335 const_reference front() const
336 {
337 return at(0);
338 }
339
340 reference back()
341 {
342 return at(size_ - 1);
343 }
344
345 const_reference back() const
346 {
347 return at(size - 1);
348 }
349
350 T* data() noexcept
351 {
352 return data_;
353 }
354
355 const T* data() const noexcept
356 {
357 return data_;
358 }
359
360 template<class... Args>
361 reference emplace_back(Args&&... args)
362 {
363 if (size_ >= capacity_)
364 resize_with_copy_(size_, next_capacity_());
365
366 allocator_traits<Allocator>::construct(begin() + size_, forward<Args>(args)...);
367
368 return back();
369 }
370
371 // TODO: assert CopyInstertable etc with enable_if!
372 void push_back(const T& x)
373 {
374 if (size_ >= capacity_)
375 resize_with_copy_(size_, next_capacity_());
376 data_[size_++] = x;
377 }
378
379 void push_back(T&& x)
380 {
381 if (size_ >= capacity_)
382 resize_with_copy_(size_, next_capacity_());
383 data_[size_++] = forward<T>(x);
384 }
385
386 void pop_back()
387 {
388 destroy_from_end_until_(end() - 1);
389 }
390
391 template<class... Args>
392 iterator emplace(const_iterator position, Args&&... args)
393 {
394 auto pos = const_cast<iterator>(position);
395
396 pos = shift_(pos, 1);
397 allocator_.construct(pos, forward<Args>(args)...);
398
399 return pos;
400 }
401
402 iterator insert(const_iterator position, const value_type& x)
403 {
404 auto pos = const_cast<iterator>(position);
405
406 pos = shift_(pos, 1);
407 *pos = x;
408
409 return pos;
410 }
411
412 iterator insert(const_iterator position, value_type&& x)
413 {
414 auto pos = const_cast<iterator>(position);
415
416 pos = shift_(pos, 1);
417 *pos = forward<value_type>(x);
418
419 return pos;
420 }
421
422 iterator insert(const_iterator position, size_type count, const value_type& x)
423 {
424 auto pos = const_cast<iterator>(position);
425
426 pos = shift_(pos, count);
427 auto copy_target = pos;
428 for (size_type i = 0; i < count; ++i)
429 *copy_target++ = x;
430
431 return pos;
432 }
433
434 template<class InputIterator>
435 iterator insert(const_iterator position, InputIterator first,
436 InputIterator last)
437 {
438 auto pos = const_cast<iterator>(position);
439 auto count = static_cast<size_type>(last - first);
440
441 pos = shift_(pos, count);
442 copy(first, last, pos);
443
444 return pos;
445 }
446
447 iterator insert(const_iterator position, initializer_list<T> init)
448 {
449 auto pos = const_cast<iterator>(position);
450
451 pos = shift_(pos, init.size());
452 copy(init.begin(), init.end(), pos);
453
454 return pos;
455 }
456
457 iterator erase(const_iterator position)
458 {
459 iterator pos = const_cast<iterator>(position);
460 copy(position + 1, cend(), pos);
461 --size_;
462
463 return pos;
464 }
465
466 iterator erase(const_iterator first, const_iterator last)
467 {
468 iterator pos = const_cast<iterator>(first);
469 copy(last, cend(), pos);
470 size_ -= static_cast<size_type>(last - first);
471
472 return pos;
473 }
474
475 void swap(vector& other)
476 noexcept(allocator_traits<Allocator>::propagate_on_container_swap::value ||
477 allocator_traits<Allocator>::is_always_equal::value)
478 {
479 std::swap(data_, other.data_);
480 std::swap(size_, other.size_);
481 std::swap(capacity_, other.capacity_);
482 }
483
484 void clear() noexcept
485 {
486 // Note: Capacity remains unchanged.
487 destroy_from_end_until_(begin());
488 size_ = 0;
489 }
490
491 private:
492 value_type* data_;
493 size_type size_;
494 size_type capacity_;
495 allocator_type allocator_;
496
497 void resize_without_copy_(size_type capacity)
498 {
499 if (data_)
500 allocator_.deallocate(data_, capacity_);
501
502 data_ = allocator_.allocate(capacity);
503 size_ = 0;
504 capacity_ = capacity;
505 }
506
507 void resize_with_copy_(size_type size, size_type capacity)
508 {
509 if (size < size_)
510 destroy_from_end_until_(begin() + size);
511
512 if(capacity_ == 0 || capacity_ < capacity)
513 {
514 auto new_data = allocator_.allocate(capacity);
515
516 auto to_copy = min(size, size_);
517 for (size_type i = 0; i < to_copy; ++i)
518 new_data[i] = move(data_[i]);
519
520 std::swap(data_, new_data);
521
522 allocator_.deallocate(new_data, capacity_);
523 }
524
525 capacity_ = capacity;
526 size_ = size;
527 }
528
529 void destroy_from_end_until_(iterator target)
530 {
531 if (!empty())
532 {
533 auto last = end();
534 while(last != target)
535 allocator_traits<Allocator>::destroy(allocator_, --last);
536 }
537 }
538
539 size_type next_capacity_(size_type hint = 0) const noexcept
540 {
541 if (hint != 0)
542 return max(capacity_ * 2, hint);
543 else
544 return max(capacity_ * 2, 2ul);
545 }
546
547 iterator shift_(iterator position, size_type count)
548 {
549 if (size_ + count < capacity_)
550 {
551 copy_backward(position, end(), end() + count);
552 size_ += count;
553
554 return position;
555 }
556 else
557 {
558 auto start_idx = static_cast<size_type>(position - begin());
559 auto end_idx = start_idx + count;
560 auto new_size = size_ + count;
561
562 // Auxiliary vector for easier swap.
563 vector tmp{};
564 tmp.resize_without_copy_(max(new_size, capacity_));
565 tmp.size_ = new_size;
566
567 // Copy before insertion index.
568 copy(begin(), begin() + start_idx, tmp.begin());
569
570 // Copy after insertion index.
571 copy(begin() + start_idx, end(), tmp.begin() + end_idx);
572
573 swap(tmp);
574
575 // Position was invalidated!
576 return begin() + start_idx;
577 }
578 }
579 };
580
581 template<class T, class Alloc>
582 bool operator==(const vector<T, Alloc>& lhs, const vector<T, Alloc>& rhs)
583 {
584 // TODO: implement
585 return false;
586 }
587
588 template<class T, class Alloc>
589 bool operator<(const vector<T, Alloc>& lhs, const vector<T, Alloc>& rhs)
590 {
591 // TODO: implement
592 return false;
593 }
594
595 template<class T, class Alloc>
596 bool operator!=(const vector<T, Alloc>& lhs, const vector<T, Alloc>& rhs)
597 {
598 return !(lhs == rhs);
599 }
600
601 template<class T, class Alloc>
602 bool operator>(const vector<T, Alloc>& lhs, const vector<T, Alloc>& rhs)
603 {
604 // TODO: implement
605 return false;
606 }
607
608 template<class T, class Alloc>
609 bool operator>=(const vector<T, Alloc>& lhs, const vector<T, Alloc>& rhs)
610 {
611 // TODO: implement
612 return false;
613 }
614
615 template<class T, class Alloc>
616 bool operator<=(const vector<T, Alloc>& lhs, const vector<T, Alloc>& rhs)
617 {
618 // TODO: implement
619 return false;
620 }
621
622 /**
623 * 23.3.6.6, specialized algorithms:
624 */
625 template<class T, class Alloc>
626 void swap(vector<T, Alloc>& lhs, vector<T, Alloc>& rhs)
627 noexcept(noexcept(lhs.swap(rhs)))
628 {
629 lhs.swap(rhs);
630 }
631}
632
633#endif
Note: See TracBrowser for help on using the repository browser.