Line data Source code
1 : //
2 : // Copyright (c) 2019 Vinnie Falco (vinnie.falco@gmail.com)
3 : //
4 : // Distributed under the Boost Software License, Version 1.0. (See accompanying
5 : // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6 : //
7 : // Official repository: https://github.com/boostorg/json
8 : //
9 :
10 : #ifndef BOOST_JSON_ARRAY_HPP
11 : #define BOOST_JSON_ARRAY_HPP
12 :
13 : #include <boost/json/detail/config.hpp>
14 : #include <boost/json/detail/array.hpp>
15 : #include <boost/json/kind.hpp>
16 : #include <boost/json/pilfer.hpp>
17 : #include <boost/json/storage_ptr.hpp>
18 : #include <boost/system/result.hpp>
19 : #include <cstdlib>
20 : #include <initializer_list>
21 : #include <iterator>
22 :
23 : namespace boost {
24 : namespace json {
25 :
26 : #ifndef BOOST_JSON_DOCS
27 : class value;
28 : class value_ref;
29 : #endif
30 :
31 : /** A dynamically sized array of JSON values
32 :
33 : This is the type used to represent a JSON array as a modifiable container.
34 : The interface and performance characteristics are modeled after
35 : `std::vector<value>`.
36 :
37 : Elements are stored contiguously, which means that they can be accessed not
38 : only through iterators, but also using offsets to regular pointers to
39 : elements. A pointer to an element of an `array` may be passed to any
40 : function that expects a pointer to @ref value.
41 :
42 : The storage of the array is handled automatically, being expanded and
43 : contracted as needed. Arrays usually occupy more space than array language
44 : constructs, because more memory is allocated to handle future growth. This
45 : way an array does not need to reallocate each time an element is inserted,
46 : but only when the additional memory is used up. The total amount of
47 : allocated memory can be queried using the @ref capacity function. Extra
48 : memory can be relinquished by calling @ref shrink_to_fit.
49 :
50 :
51 : Reallocations are usually costly operations in terms of performance. The
52 : @ref reserve function can be used to eliminate reallocations if the number
53 : of elements is known beforehand.
54 :
55 : The complexity (efficiency) of common operations on arrays is as follows:
56 :
57 : @li Random access---constant *O(1)*.
58 : @li Insertion or removal of elements at the end - amortized
59 : constant *O(1)*.
60 : @li Insertion or removal of elements---linear in the distance to the end of
61 : the array *O(n)*.
62 :
63 : @par Allocators
64 :
65 : All elements stored in the container, and their children if any, will use
66 : the same memory resource that was used to construct the container.
67 :
68 : @par Thread Safety
69 :
70 : Non-const member functions may not be called concurrently with any other
71 : member functions.
72 :
73 : @par Satisfies
74 : [*ContiguousContainer*](https://en.cppreference.com/w/cpp/named_req/ContiguousContainer),
75 : [*ReversibleContainer*](https://en.cppreference.com/w/cpp/named_req/ReversibleContainer), and
76 : {req_SequenceContainer}.
77 : */
78 : class array
79 : {
80 : struct table;
81 : class revert_construct;
82 : class revert_insert;
83 : friend class value;
84 :
85 : storage_ptr sp_; // must come first
86 : kind k_ = kind::array; // must come second
87 : table* t_;
88 :
89 : BOOST_JSON_DECL
90 : static table empty_;
91 :
92 : inline
93 : static
94 : void
95 : relocate(
96 : value* dest,
97 : value* src,
98 : std::size_t n) noexcept;
99 :
100 : inline
101 : void
102 : destroy(
103 : value* first,
104 : value* last) noexcept;
105 :
106 : BOOST_JSON_DECL
107 : void
108 : destroy() noexcept;
109 :
110 : BOOST_JSON_DECL
111 : explicit
112 : array(detail::unchecked_array&& ua);
113 :
114 : public:
115 : /// Associated [Allocator](https://en.cppreference.com/w/cpp/named_req/Allocator)
116 : using allocator_type = container::pmr::polymorphic_allocator<value>;
117 :
118 : /// The type used to represent unsigned integers
119 : using size_type = std::size_t;
120 :
121 : /// The type of each element
122 : using value_type = value;
123 :
124 : /// The type used to represent signed integers
125 : using difference_type = std::ptrdiff_t;
126 :
127 : /// A reference to an element
128 : using reference = value&;
129 :
130 : /// A const reference to an element
131 : using const_reference = value const&;
132 :
133 : /// A pointer to an element
134 : using pointer = value*;
135 :
136 : /// A const pointer to an element
137 : using const_pointer = value const*;
138 :
139 : /// A random access iterator to an element
140 : using iterator = value*;
141 :
142 : /// A random access const iterator to an element
143 : using const_iterator = value const*;
144 :
145 : /// A reverse random access iterator to an element
146 : using reverse_iterator =
147 : std::reverse_iterator<iterator>;
148 :
149 : /// A reverse random access const iterator to an element
150 : using const_reverse_iterator =
151 : std::reverse_iterator<const_iterator>;
152 :
153 : //------------------------------------------------------
154 :
155 : /** Destructor.
156 :
157 : The destructor for each element is called if needed, any used memory is
158 : deallocated, and shared ownership of the
159 : @ref boost::container::pmr::memory_resource is released.
160 :
161 : @par Complexity
162 : Linear in @ref size().
163 :
164 : @par Exception Safety
165 : No-throw guarantee.
166 : */
167 : BOOST_JSON_DECL
168 : ~array() noexcept;
169 :
170 : //------------------------------------------------------
171 :
172 : /** Constructors.
173 :
174 : Constructs an array.
175 :
176 : @li **(1)**, **(2)** the array is empty and has zero capacity.
177 :
178 : @li **(3)** the array is filled with `count` copies of `jv`.
179 :
180 : @li **(4)** the array is filled with `count` null values.
181 :
182 : @li **(5)** the array is filled with values in the range
183 : `[first, last)`, preserving order.
184 :
185 : @li **(6)** the array is filled with copies of the values in `init`,
186 : preserving order.
187 :
188 : @li **(7)**, **(8)** the array is filled with copies of the elements of
189 : `other`, preserving order.
190 :
191 : @li **(9)** the array acquires ownership of the contents of `other`.
192 :
193 : @li **(10)** equivalent to **(9)** if `*sp == *other.storage()`;
194 : otherwise equivalent to **(8)**.
195 :
196 : @li **(11)** the array acquires ownership of the contents of `other`
197 : using pilfer semantics. This is more efficient than move
198 : construction, when it is known that the moved-from object will be
199 : immediately destroyed afterwards.
200 :
201 : With **(2)**, **(4)**, **(5)**, **(6)**, **(8)**, **(10)** the
202 : constructed array uses memory resource of `sp`. With **(7)**, **(9)**,
203 : and **(11)** it uses `other`'s memory resource. In either case the
204 : array will share the ownership of the memory resource. With **(1)**
205 : and **(3)** it uses the
206 : \<\<default_memory_resource, default memory resource\>\>.
207 :
208 : After **(9)** `other` behaves as if newly constructed with its
209 : current storage pointer.
210 :
211 : After **(11)** `other` is not in a usable state and may only be
212 : destroyed.
213 :
214 : @par Constraints
215 :
216 : @code
217 : std::is_constructible_v<value, std::iterator_traits<InputIt>::reference>
218 : @endcode
219 :
220 : @par Complexity
221 : @li **(1)**, **(2)**, **(9)**, **(11)** constant.
222 : @li **(3)**, **(4)** linear in `count`.
223 : @li **(5)** linear in `std::distance(first, last)`
224 : @li **(6)** linear in `init.size()`.
225 : @li **(7)**, **(8)** linear in `other.size()`.
226 : @li **(10)** constant if `*sp == *other.storage()`; otherwise linear in
227 : `other.size()`.
228 :
229 : @par Exception Safety
230 : @li **(1)**, **(2)**, **(9)**, **(11)** no-throw guarantee.
231 : @li **(3)**, **(4)**, **(6)**--**(8)**, **(10)** strong
232 : guarantee.
233 : @li **(5)** strong guarantee if `InputIt` satisfies
234 : {req_ForwardIterator}, basic guarantee otherwise.
235 :
236 : Calls to `memory_resource::allocate` may throw.
237 :
238 : @see @ref pilfer,
239 : [Valueless Variants Considered Harmful](http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0308r0.html).
240 : @{
241 : */
242 79 : array() noexcept
243 79 : : t_(&empty_)
244 : {
245 79 : }
246 :
247 : /** Overload
248 : @param sp A pointer to the @ref boost::container::pmr::memory_resource
249 : to use. The container will acquire shared ownership of the memory
250 : resource.
251 : */
252 : explicit
253 644 : array(storage_ptr sp) noexcept
254 644 : : sp_(std::move(sp))
255 644 : , k_(kind::array)
256 644 : , t_(&empty_)
257 : {
258 644 : }
259 :
260 : /** Overload
261 : @param count The number of copies to insert.
262 : @param jv The value to be inserted.
263 : @param sp
264 : */
265 : BOOST_JSON_DECL
266 : array(
267 : std::size_t count,
268 : value const& jv,
269 : storage_ptr sp = {});
270 :
271 : /// Overload
272 : BOOST_JSON_DECL
273 : array(
274 : std::size_t count,
275 : storage_ptr sp = {});
276 :
277 : /** Overload
278 :
279 : @param first An input iterator pointing to the first element to insert,
280 : or pointing to the end of the range.
281 : @param last An input iterator pointing to the end of the range.
282 : @param sp
283 :
284 : @tparam InputIt a type satisfying the {req_InputIterator} requirement.
285 : */
286 : template<
287 : class InputIt
288 : #ifndef BOOST_JSON_DOCS
289 : ,class = typename std::enable_if<
290 : std::is_constructible<value,
291 : typename std::iterator_traits<
292 : InputIt>::reference>::value>::type
293 : #endif
294 : >
295 : array(
296 : InputIt first, InputIt last,
297 : storage_ptr sp = {});
298 :
299 : /** Overload
300 : @param init The initializer list with elements to insert.
301 : @param sp
302 : */
303 : BOOST_JSON_DECL
304 : array(
305 : std::initializer_list<value_ref> init,
306 : storage_ptr sp = {});
307 :
308 : /** Overload
309 : @param other Another array.
310 : */
311 : BOOST_JSON_DECL
312 : array(array const& other);
313 :
314 : /// Overload
315 : BOOST_JSON_DECL
316 : array(
317 : array const& other,
318 : storage_ptr sp);
319 :
320 : /// Overload
321 188 : array(array&& other) noexcept
322 188 : : sp_(other.sp_)
323 376 : , t_(detail::exchange(
324 188 : other.t_, &empty_))
325 : {
326 188 : }
327 :
328 : /// Overload
329 : BOOST_JSON_DECL
330 : array(
331 : array&& other,
332 : storage_ptr sp);
333 :
334 : /// Overload
335 6 : array(pilfered<array> other) noexcept
336 6 : : sp_(std::move(other.get().sp_))
337 12 : , t_(detail::exchange(
338 6 : other.get().t_, &empty_))
339 : {
340 6 : }
341 : /// @}
342 :
343 : /** Assignment operators.
344 :
345 : Replaces the contents of the array.
346 : @li **(1)** the contents are replaced with an element-wise copy of
347 : `other`.
348 : @li **(2)** takes ownership of `other`'s element storage if
349 : `*storage() == *other.storage()`; otherwise equivalent to **(1)**.
350 : @li **(3)** the contents are replaced with a copy of the values in
351 : `init`.
352 :
353 : After **(2)**, the moved-from array behaves as if newly constructed
354 : with its current storage pointer.
355 :
356 : @par Complexity
357 : @li **(1)** linear in `size() + other.size()`.
358 : @li **(2)** constant if `*storage() == *other.storage()`; otherwise
359 : linear in `size() + other.size()`.
360 : @li **(1)** linear in `size() + init.size()`.
361 :
362 : @par Exception Safety
363 : {sp} **(2)** provides strong guarantee if
364 : `*storage() != *other.storage()` and no-throw guarantee otherwise.
365 : Other overloads provide strong guarantee.
366 : Calls to `memory_resource::allocate` may throw.
367 :
368 : @param other The array to copy.
369 :
370 : @return `*this`
371 :
372 : @{
373 : */
374 : BOOST_JSON_DECL
375 : array&
376 : operator=(array const& other);
377 :
378 : /** Overload
379 : @param other The array to move.
380 : */
381 : BOOST_JSON_DECL
382 : array&
383 : operator=(array&& other);
384 :
385 : /** Overload
386 : @param init The initializer list to copy.
387 : */
388 : BOOST_JSON_DECL
389 : array&
390 : operator=(
391 : std::initializer_list<value_ref> init);
392 : /// @}
393 :
394 : /** Return the associated memory resource.
395 :
396 : This function returns a smart pointer to the
397 : @ref boost::container::pmr::memory_resource used by the container.
398 :
399 : @par Complexity
400 : Constant.
401 :
402 : @par Exception Safety
403 : No-throw guarantee.
404 : */
405 : storage_ptr const&
406 15208 : storage() const noexcept
407 : {
408 15208 : return sp_;
409 : }
410 :
411 : /** Return the associated allocator.
412 :
413 : This function returns an instance of @ref allocator_type constructed
414 : from the associated @ref boost::container::pmr::memory_resource.
415 :
416 : @par Complexity
417 : Constant.
418 :
419 : @par Exception Safety
420 : No-throw guarantee.
421 : */
422 : allocator_type
423 1 : get_allocator() const noexcept
424 : {
425 1 : return sp_.get();
426 : }
427 :
428 : //------------------------------------------------------
429 : //
430 : // Element access
431 : //
432 : //------------------------------------------------------
433 :
434 : /** Access an element, with bounds checking.
435 :
436 : Returns @ref boost::system::result containing a reference to the
437 : element specified at location `pos`, if `pos` is within the range of
438 : the container. Otherwise the result contains an `error_code`.
439 :
440 : @par Exception Safety
441 : No-throw guarantee.
442 :
443 : @param pos A zero-based index.
444 :
445 : @par Complexity
446 : Constant.
447 :
448 : @{
449 : */
450 : BOOST_JSON_DECL
451 : system::result<value&>
452 : try_at(std::size_t pos) noexcept;
453 :
454 : BOOST_JSON_DECL
455 : system::result<value const&>
456 : try_at(std::size_t pos) const noexcept;
457 : /// @}
458 :
459 : /** Access an element, with bounds checking.
460 :
461 : Returns a reference to the element specified at location `pos`, with
462 : bounds checking. If `pos` is not within the range of the container, an
463 : exception of type @ref boost::system::system_error is thrown.
464 :
465 : @par Complexity
466 : Constant.
467 :
468 : @param pos A zero-based index.
469 :
470 : @param loc `source_location` to use in thrown exception; the source
471 : location of the call site by default.
472 :
473 : @throw `boost::system::system_error` `pos >= size()`.
474 :
475 : @{
476 : */
477 : inline
478 : value&
479 : at(
480 : std::size_t pos,
481 : source_location const& loc = BOOST_CURRENT_LOCATION) &;
482 :
483 : inline
484 : value&&
485 : at(
486 : std::size_t pos,
487 : source_location const& loc = BOOST_CURRENT_LOCATION) &&;
488 :
489 : BOOST_JSON_DECL
490 : value const&
491 : at(
492 : std::size_t pos,
493 : source_location const& loc = BOOST_CURRENT_LOCATION) const&;
494 : /// @}
495 :
496 : /** Access an element.
497 :
498 : Returns a reference to the element specified at
499 : location `pos`. No bounds checking is performed.
500 :
501 : @pre `pos < size()`
502 :
503 : @par Complexity
504 : Constant.
505 :
506 : @param pos A zero-based index
507 :
508 : @{
509 : */
510 : inline
511 : value&
512 : operator[](std::size_t pos) & noexcept;
513 :
514 : inline
515 : value&&
516 : operator[](std::size_t pos) && noexcept;
517 :
518 : inline
519 : value const&
520 : operator[](std::size_t pos) const& noexcept;
521 : /// @}
522 :
523 : /** Access the first element.
524 :
525 : Returns a reference to the first element.
526 :
527 : @pre `! empty()`
528 :
529 : @par Complexity
530 : Constant.
531 :
532 : @{
533 : */
534 : inline
535 : value&
536 : front() & noexcept;
537 :
538 : inline
539 : value&&
540 : front() && noexcept;
541 :
542 : inline
543 : value const&
544 : front() const& noexcept;
545 : /// @}
546 :
547 : /** Access the last element.
548 :
549 : Returns a reference to the last element.
550 :
551 : @pre `!empty()`
552 :
553 : @par Complexity
554 : Constant.
555 :
556 : @{
557 : */
558 : inline
559 : value&
560 : back() & noexcept;
561 :
562 : inline
563 : value&&
564 : back() && noexcept;
565 :
566 : inline
567 : value const&
568 : back() const& noexcept;
569 : /// @}
570 :
571 : /** Access the underlying array directly.
572 :
573 : Returns a pointer to the underlying array serving as element storage.
574 : The value returned is such that the range `[data(), data() + size())`
575 : is always a valid range, even if the container is empty.
576 :
577 : @note
578 : If `size() == 0`, the function may or may not return
579 : a null pointer.
580 :
581 : @par Complexity
582 : Constant.
583 :
584 : @par Exception Safety
585 : No-throw guarantee.
586 :
587 : @{
588 : */
589 : inline
590 : value*
591 : data() noexcept;
592 :
593 : inline
594 : value const*
595 : data() const noexcept;
596 : /// @}
597 :
598 : /** Return a pointer to an element if it exists.
599 :
600 : This function returns a pointer to the element at index `pos` when the
601 : index is less then the size of the container. Otherwise it returns
602 : null.
603 :
604 : @par Example
605 : @code
606 : if( auto p = arr.if_contains( 1 ) )
607 : std::cout << *p;
608 : @endcode
609 :
610 : @par Complexity
611 : Constant.
612 :
613 : @par Exception Safety
614 : No-throw guarantee.
615 :
616 : @param pos The index of the element to return.
617 :
618 : @{
619 : */
620 : inline
621 : value const*
622 : if_contains(std::size_t pos) const noexcept;
623 :
624 : inline
625 : value*
626 : if_contains(std::size_t pos) noexcept;
627 : /// @}
628 :
629 : //------------------------------------------------------
630 : //
631 : // Iterators
632 : //
633 : //------------------------------------------------------
634 :
635 : /** Return an iterator to the first element.
636 :
637 : If the container is empty, @ref end() is returned.
638 :
639 : @par Complexity
640 : Constant.
641 :
642 : @par Exception Safety
643 : No-throw guarantee.
644 :
645 : @{
646 : */
647 : inline
648 : iterator
649 : begin() noexcept;
650 :
651 : inline
652 : const_iterator
653 : begin() const noexcept;
654 : /// @}
655 :
656 : /** Return a const iterator to the first element.
657 :
658 : If the container is empty, @ref cend() is returned.
659 :
660 : @par Complexity
661 : Constant.
662 :
663 : @par Exception Safety
664 : No-throw guarantee.
665 : */
666 : inline
667 : const_iterator
668 : cbegin() const noexcept;
669 :
670 : /** Return a const iterator past the last element.
671 :
672 : The returned iterator only acts as a sentinel. Dereferencing it results
673 : in undefined behavior.
674 :
675 : @par Complexity
676 : Constant.
677 :
678 : @par Exception Safety
679 : No-throw guarantee.
680 :
681 : @{
682 : */
683 : inline
684 : iterator
685 : end() noexcept;
686 :
687 : inline
688 : const_iterator
689 : end() const noexcept;
690 : /// @}
691 :
692 : /** Return a const iterator past the last element.
693 :
694 : The returned iterator only acts as a sentinel. Dereferencing it results
695 : in undefined behavior.
696 :
697 : @par Complexity
698 : Constant.
699 :
700 : @par Exception Safety
701 : No-throw guarantee.
702 : */
703 : inline
704 : const_iterator
705 : cend() const noexcept;
706 :
707 : /** Return a reverse iterator to the first element of the reversed container.
708 :
709 : The pointed-to element corresponds to the
710 : last element of the non-reversed container.
711 : If the container is empty, @ref rend() is returned.
712 :
713 : @par Complexity
714 : Constant.
715 :
716 : @par Exception Safety
717 : No-throw guarantee.
718 :
719 : @{
720 : */
721 : inline
722 : reverse_iterator
723 : rbegin() noexcept;
724 :
725 : inline
726 : const_reverse_iterator
727 : rbegin() const noexcept;
728 : /// @}
729 :
730 : /** Return a const reverse iterator to the first element of the reversed container.
731 :
732 : The pointed-to element corresponds to the
733 : last element of the non-reversed container.
734 : If the container is empty, @ref crend() is returned.
735 :
736 : @par Complexity
737 : Constant.
738 :
739 : @par Exception Safety
740 : No-throw guarantee.
741 : */
742 : inline
743 : const_reverse_iterator
744 : crbegin() const noexcept;
745 :
746 : /** Return a reverse iterator to the element following the last element of the reversed container.
747 :
748 : The pointed-to element corresponds to the element
749 : preceding the first element of the non-reversed container.
750 : The returned iterator only acts as a sentinel. Dereferencing it results
751 : in undefined behavior.
752 :
753 : @par Complexity
754 : Constant.
755 :
756 : @par Exception Safety
757 : No-throw guarantee.
758 :
759 : @{
760 : */
761 : inline
762 : reverse_iterator
763 : rend() noexcept;
764 :
765 : inline
766 : const_reverse_iterator
767 : rend() const noexcept;
768 : /// @}
769 :
770 : /** Return a const reverse iterator to the element following the last element of the reversed container.
771 :
772 : The pointed-to element corresponds to the element preceding the first
773 : element of the non-reversed container. The returned iterator only acts
774 : as a sentinel. Dereferencing it results in undefined behavior.
775 :
776 : @par Complexity
777 : Constant.
778 :
779 : @par Exception Safety
780 : No-throw guarantee.
781 : */
782 : inline
783 : const_reverse_iterator
784 : crend() const noexcept;
785 :
786 : //------------------------------------------------------
787 : //
788 : // Capacity
789 : //
790 : //------------------------------------------------------
791 :
792 : /** Return the number of elements in the array.
793 :
794 : This returns the number of elements in the array.
795 : The value returned may be different from the number
796 : returned from @ref capacity.
797 :
798 : @par Complexity
799 : Constant.
800 :
801 : @par Exception Safety
802 : No-throw guarantee.
803 : */
804 : inline
805 : std::size_t
806 : size() const noexcept;
807 :
808 : /** The maximum number of elements an array can hold.
809 :
810 : The maximum is an implementation-defined number. This value is
811 : a theoretical limit; at runtime, the actual maximum size may be less
812 : due to resource limits.
813 :
814 : @par Complexity
815 : Constant.
816 :
817 : @par Exception Safety
818 : No-throw guarantee.
819 : */
820 : static
821 : inline
822 : constexpr
823 : std::size_t
824 : max_size() noexcept;
825 :
826 : /** Return the number of elements that can be held in currently allocated memory.
827 :
828 : Returns the number of elements that the container has currently
829 : allocated space for. This number is never smaller than the value
830 : returned by @ref size().
831 :
832 : @par Complexity
833 : Constant.
834 :
835 : @par Exception Safety
836 : No-throw guarantee.
837 : */
838 : inline
839 : std::size_t
840 : capacity() const noexcept;
841 :
842 : /** Check if the array has no elements.
843 :
844 : Returns `true` if there are no elements in the
845 : array, i.e. @ref size() returns 0.
846 :
847 : @par Complexity
848 : Constant.
849 :
850 : @par Exception Safety
851 : No-throw guarantee.
852 : */
853 : inline
854 : bool
855 : empty() const noexcept;
856 :
857 : /** Increase the capacity to at least a certain amount.
858 :
859 : This increases the @ref capacity() to a value that is greater than or
860 : equal to `new_capacity`. If `new_capacity > capacity()`, new memory is
861 : allocated. Otherwise, the call has no effect. The number of elements
862 : and therefore the @ref size() of the container is not changed.
863 :
864 : If new memory is allocated, all iterators including any past-the-end
865 : iterators, and all references to the elements are invalidated.
866 : Otherwise, no iterators or references are invalidated.
867 :
868 : @par Complexity
869 : At most, linear in @ref size().
870 :
871 : @par Exception Safety
872 : Strong guarantee.
873 : Calls to `memory_resource::allocate` may throw.
874 :
875 : @param new_capacity The new capacity of the array.
876 :
877 : @throw boost::system::system_error `new_capacity >` @ref max_size().
878 : */
879 : inline
880 : void
881 : reserve(std::size_t new_capacity);
882 :
883 : /** Request the removal of unused capacity.
884 :
885 : This performs a non-binding request to reduce the
886 : capacity to the current size. The request may or
887 : may not be fulfilled. If reallocation occurs, all
888 : iterators including any past-the-end iterators,
889 : and all references to the elements are invalidated.
890 : Otherwise, no iterators or references are
891 : invalidated.
892 :
893 : @par Complexity
894 : At most, linear in @ref size().
895 :
896 : @par Exception Safety
897 : No-throw guarantee.
898 : */
899 : BOOST_JSON_DECL
900 : void
901 : shrink_to_fit() noexcept;
902 :
903 : //------------------------------------------------------
904 : //
905 : // Modifiers
906 : //
907 : //------------------------------------------------------
908 :
909 : /** Clear the contents.
910 :
911 : Erases all elements from the container. After this call, @ref size()
912 : returns zero but @ref capacity() is unchanged. All references,
913 : pointers, and iterators are invalidated
914 :
915 : @par Complexity
916 : Linear in @ref size().
917 :
918 : @par Exception Safety
919 : No-throw guarantee.
920 : */
921 : BOOST_JSON_DECL
922 : void
923 : clear() noexcept;
924 :
925 : /** Insert elements before the specified location.
926 :
927 : @li **(1)** and **(2)** insert a single new element before
928 : `pos`. **(1)** copy-constructs and **(2)** move-constructs the new
929 : element from `jv`.
930 : @li **(3)** inserts `count` copies of `jv` before `pos`.
931 : @li **(4)** the elements in the range `[first, last)` are inserted in
932 : order.
933 : @li **(5)** the elements of the initializer list `init` are inserted in
934 : order.
935 :
936 : Inserted values will be constructed using the container's
937 : associated @ref boost::container::pmr::memory_resource.
938 :
939 : @note Overload **(2)** is equivalent to **(1)** if
940 : `*jv.storage() != *this->storage()`.
941 :
942 : If the size of the array after insertion would have exceeded
943 : @ref capacity(), a reallocation occurs first, and all iterators and
944 : references are invalidated. Otherwise, only the iterators and
945 : references from the insertion point forward are invalidated. All
946 : past-the-end iterators are also invalidated.
947 :
948 : @pre
949 : `first` and `last` are not iterators into `*this`.
950 :
951 : @par Constraints
952 : @code
953 : ! std::is_convertible_v<InputIt, value>
954 : std::is_constructible_v<value, std::iterator_traits<InputIt>::reference>
955 : @endcode
956 :
957 : @par Complexity
958 : @li **(1)**, **(2)** linear in `std::distance(pos, end())`.
959 : @li **(3)** linear in `count + std::distance(pos, end())`.
960 : @li **(4)** linear in `std::distance(first, last) +
961 : std::distance(pos, end())`.
962 : @li **(5)** linear in `init.size() + std::distance(pos, end())`.
963 :
964 : @par Exception Safety
965 : {sp}**(4)** provides strong guarantee if `InputIt` satisfies
966 : {req_ForwardIterator}, and basic guarantee otherwise. Other overloads
967 : provide strong guarantee.
968 : Calls to `memory_resource::allocate` may throw.
969 :
970 : @param pos Iterator before which the new elements will
971 : be inserted. This may be the @ref end() iterator.
972 :
973 : @param jv The value to insert. A copy will be made
974 : using container's associated
975 : @ref boost::container::pmr::memory_resource.
976 :
977 : @return An iterator to the first inserted value, or `pos` if no values
978 : were inserted.
979 :
980 : @{
981 : */
982 : BOOST_JSON_DECL
983 : iterator
984 : insert(
985 : const_iterator pos,
986 : value const& jv);
987 :
988 : // Overload
989 : BOOST_JSON_DECL
990 : iterator
991 : insert(
992 : const_iterator pos,
993 : value&& jv);
994 :
995 :
996 : /** Overload
997 : @param count The number of copies to insert.
998 : @param pos
999 : @param jv
1000 : */
1001 : BOOST_JSON_DECL
1002 : iterator
1003 : insert(
1004 : const_iterator pos,
1005 : std::size_t count,
1006 : value const& jv);
1007 :
1008 : /** Overload
1009 :
1010 : @param first An input iterator pointing to the first element to insert,
1011 : or pointing to the end of the range.
1012 : @param last An input iterator pointing to the end of the range.
1013 : @param pos
1014 :
1015 : @tparam InputIt a type satisfying the requirements
1016 : of {req_InputIterator}.
1017 : */
1018 : template<
1019 : class InputIt
1020 : #ifndef BOOST_JSON_DOCS
1021 : ,class = typename std::enable_if<
1022 : std::is_constructible<value,
1023 : typename std::iterator_traits<
1024 : InputIt>::reference>::value>::type
1025 : #endif
1026 : >
1027 : iterator
1028 : insert(
1029 : const_iterator pos,
1030 : InputIt first, InputIt last);
1031 :
1032 : /** Overload
1033 : @param init The initializer list to insert
1034 : @param pos
1035 : */
1036 : BOOST_JSON_DECL
1037 : iterator
1038 : insert(
1039 : const_iterator pos,
1040 : std::initializer_list<value_ref> init);
1041 : /// @}
1042 :
1043 : /** Insert a constructed element in-place.
1044 :
1045 : Inserts a new element into the container directly before
1046 : `pos`. The element is constructed using placement-new
1047 : with the parameter `std::forward<Arg>(arg)`.
1048 : If `capacity() < size() + 1`,
1049 : a reallocation occurs first, and all iterators and
1050 : references are invalidated.
1051 : Otherwise, only the iterators and references from
1052 : the insertion point forward are invalidated. All
1053 : past-the-end iterators are also invalidated.
1054 :
1055 : @par Complexity
1056 : Linear in `std::distance(pos, end())`.
1057 :
1058 : @par Exception Safety
1059 : Strong guarantee.
1060 : Calls to `memory_resource::allocate` may throw.
1061 :
1062 : @param pos Iterator before which the element will
1063 : be inserted. This may be the @ref end() iterator.
1064 :
1065 : @param arg The argument to forward to the @ref value
1066 : constructor.
1067 :
1068 : @return An iterator to the inserted element
1069 : */
1070 : template<class Arg>
1071 : iterator
1072 : emplace(
1073 : const_iterator pos,
1074 : Arg&& arg);
1075 :
1076 : /** Remove elements from the array.
1077 :
1078 : @li **(1)** the element at `pos` is removed.
1079 : @li **(2)** the elements in the range `[first, last)` are removed.
1080 :
1081 : @par Complexity
1082 : @li **(1)** linear in `std::distance(pos, end())`.
1083 : @li **(2)** linear in `std::distance(first, end())`.
1084 :
1085 : @par Exception Safety
1086 : No-throw guarantee.
1087 :
1088 : @param pos Iterator to the element to remove
1089 :
1090 : @return Iterator following the last removed element. If that was the
1091 : last element of the array, the @ref end() iterator is returned.
1092 :
1093 : @{
1094 : */
1095 : BOOST_JSON_DECL
1096 : iterator
1097 : erase(const_iterator pos) noexcept;
1098 :
1099 : /** Overload
1100 : @param first An iterator pointing to the first element to erase, or
1101 : pointing to the end of the range.
1102 : @param last An iterator pointing to one past the last element to erase,
1103 : or pointing to the end of the range.
1104 : */
1105 : BOOST_JSON_DECL
1106 : iterator
1107 : erase(
1108 : const_iterator first,
1109 : const_iterator last) noexcept;
1110 : /// @}
1111 :
1112 : /** Add an element to the end.
1113 :
1114 : Insert a new element at the end of the container. **(1)**
1115 : copy-constructs the new element from `jv`, **(2)** move-constructs from
1116 : `jv`.
1117 :
1118 : If `capacity() < size() + 1`, a reallocation occurs first, and all
1119 : iterators and references are invalidated. Any past-the-end iterators
1120 : are always invalidated.
1121 :
1122 : The new element will be constructed using the container's associated
1123 : @ref boost::container::pmr::memory_resource.
1124 :
1125 : @par Complexity
1126 : Amortized constant.
1127 :
1128 : @par Exception Safety
1129 : Strong guarantee.
1130 : Calls to `memory_resource::allocate` may throw.
1131 :
1132 : @param jv The value to insert.
1133 :
1134 : @{
1135 : */
1136 : BOOST_JSON_DECL
1137 : void
1138 : push_back(value const& jv);
1139 :
1140 : BOOST_JSON_DECL
1141 : void
1142 : push_back(value&& jv);
1143 : /// @}
1144 :
1145 : /** Append a constructed element in-place.
1146 :
1147 : Appends a new element to the end of the container's
1148 : list of elements.
1149 : The element is constructed using placement-new
1150 : with the parameter `std::forward<Arg>(arg)`.
1151 : If `capacity() < size() + 1`,
1152 : a reallocation occurs first, and all iterators and
1153 : references are invalidated.
1154 : Otherwise, only the iterators and references from
1155 : the insertion point forward are invalidated. All
1156 : past-the-end iterators are also invalidated.
1157 :
1158 : @par Complexity
1159 : Amortized constant.
1160 :
1161 : @par Exception Safety
1162 : Strong guarantee.
1163 : Calls to `memory_resource::allocate` may throw.
1164 :
1165 : @param arg The argument to forward to the @ref value
1166 : constructor.
1167 :
1168 : @return A reference to the inserted element
1169 : */
1170 : template<class Arg>
1171 : value&
1172 : emplace_back(Arg&& arg);
1173 :
1174 : /** Remove the last element
1175 :
1176 : The last element of the container is erased.
1177 :
1178 : @pre
1179 : `! empty()`
1180 :
1181 : @par Exception Safety
1182 : No-throw guarantee.
1183 : */
1184 : BOOST_JSON_DECL
1185 : void
1186 : pop_back() noexcept;
1187 :
1188 : /** Change the number of elements stored.
1189 :
1190 : Resizes the container to contain `count` elements.
1191 :
1192 : @li If `size() > count`, the container is reduced to its first `count`
1193 : elements.
1194 : @li If `size() < count`, additional null values (**(1)**) or copies
1195 : of `jv` (**(2)**) are appended.
1196 :
1197 : If `capacity() < count`, a reallocation occurs first, and all iterators
1198 : and references are invalidated. Any past-the-end iterators are always
1199 : invalidated.
1200 :
1201 : @par Complexity
1202 : Linear in `size() + count`.
1203 :
1204 : @par Exception Safety
1205 : Strong guarantee.
1206 : Calls to `memory_resource::allocate` may throw.
1207 :
1208 : @param count The new size of the container.
1209 :
1210 : @{
1211 : */
1212 : BOOST_JSON_DECL
1213 : void
1214 : resize(std::size_t count);
1215 :
1216 : /** Overload
1217 : @param jv The @ref value to copy into the new elements.
1218 : @param count
1219 : */
1220 : BOOST_JSON_DECL
1221 : void
1222 : resize(
1223 : std::size_t count,
1224 : value const& jv);
1225 : /// @}
1226 :
1227 : /** Swap two arrays.
1228 :
1229 : Exchanges the contents of this array with another array. Ownership of
1230 : the respective @ref boost::container::pmr::memory_resource objects is
1231 : not transferred. If `this == &other`, this function call has no effect.
1232 :
1233 : @li If `*storage() == *other.storage()` all iterators and references
1234 : remain valid.
1235 :
1236 : @li Otherwise, the contents are logically swapped by making copies,
1237 : which can throw. In this case all iterators and references are
1238 : invalidated.
1239 :
1240 : @par Complexity
1241 : If `*storage() == *other.storage()`, then constant; otherwise linear in
1242 : `size() + other.size()`.
1243 :
1244 : @par Exception Safety
1245 : No-throw guarantee if `*storage() == *other.storage()`. Otherwise
1246 : strong guarantee. Calls to `memory_resource::allocate` may throw.
1247 :
1248 : @param other The value to swap with.
1249 : */
1250 : BOOST_JSON_DECL
1251 : void
1252 : swap(array& other);
1253 :
1254 : /** Swap two arrays.
1255 :
1256 : Exchanges the contents of the array `lhs` with another array `rhs`.
1257 : Ownership of the respective @ref boost::container::pmr::memory_resource
1258 : objects is not transferred. If `&lhs == &rhs`, this function call has
1259 : no effect.
1260 :
1261 : @li If `*lhs.storage() == *rhs.storage()` all iterators and references
1262 : remain valid.
1263 :
1264 : @li Otherwise, the contents are logically swapped by making copies,
1265 : which can throw. In this case all iterators and references are
1266 : invalidated.
1267 :
1268 : @par Complexity
1269 : If `*lhs.storage() == *rhs.storage()`, then constant; otherwise linear
1270 : in `lhs.size() + rhs.size()`.
1271 :
1272 : @par Exception Safety
1273 : No-throw guarantee if `*lhs.storage() == *rhs.storage()`. Otherwise
1274 : strong guarantee. Calls to `memory_resource::allocate` may throw.
1275 :
1276 : @param lhs The array to exchange.
1277 :
1278 : @param rhs The array to exchange.
1279 : If `&lhs == &rhs`, this function call has no effect.
1280 :
1281 : @see @ref array::swap
1282 : */
1283 : friend
1284 : void
1285 1 : swap(array& lhs, array& rhs)
1286 : {
1287 1 : lhs.swap(rhs);
1288 1 : }
1289 :
1290 : /** Compare two arrays for equality.
1291 :
1292 : Arrays are equal when their sizes are the same, and they are
1293 : element-for-element equal in order.
1294 :
1295 : @par Complexity
1296 : Linear in `lhs.size()`.
1297 :
1298 : @par Exception Safety
1299 : No-throw guarantee.
1300 : */
1301 : // inline friend speeds up overload resolution
1302 : friend
1303 : bool
1304 96 : operator==(
1305 : array const& lhs,
1306 : array const& rhs) noexcept
1307 : {
1308 96 : return lhs.equal(rhs);
1309 : }
1310 :
1311 : /** Compare two arrays for inequality.
1312 :
1313 : Arrays are equal when their sizes are the same, and they are
1314 : element-for-element equal in order.
1315 :
1316 : @par Complexity
1317 : Linear in `lhs.size()`.
1318 :
1319 : @par Exception Safety
1320 : No-throw guarantee.
1321 : */
1322 : // inline friend speeds up overload resolution
1323 : friend
1324 : bool
1325 9 : operator!=(
1326 : array const& lhs,
1327 : array const& rhs) noexcept
1328 : {
1329 9 : return ! (lhs == rhs);
1330 : }
1331 :
1332 : /** Serialize to an output stream.
1333 :
1334 : This function serializes an `array` as JSON into the output stream.
1335 :
1336 : @return Reference to `os`.
1337 :
1338 : @par Complexity
1339 : Constant or linear in the size of `arr`.
1340 :
1341 : @par Exception Safety
1342 : Strong guarantee.
1343 : Calls to `memory_resource::allocate` may throw.
1344 :
1345 : @param os The output stream to serialize to.
1346 :
1347 : @param arr The value to serialize.
1348 : */
1349 : BOOST_JSON_DECL
1350 : friend
1351 : std::ostream&
1352 : operator<<(
1353 : std::ostream& os,
1354 : array const& arr);
1355 :
1356 : private:
1357 : template<class It>
1358 : using iter_cat = typename
1359 : std::iterator_traits<It>::iterator_category;
1360 :
1361 : template<class InputIt>
1362 : array(
1363 : InputIt first, InputIt last,
1364 : storage_ptr sp,
1365 : std::input_iterator_tag);
1366 :
1367 : template<class InputIt>
1368 : array(
1369 : InputIt first, InputIt last,
1370 : storage_ptr sp,
1371 : std::forward_iterator_tag);
1372 :
1373 : inline
1374 : std::size_t
1375 : growth(std::size_t new_size) const;
1376 :
1377 : BOOST_JSON_DECL
1378 : void
1379 : reserve_impl(
1380 : std::size_t new_capacity);
1381 :
1382 : BOOST_JSON_DECL
1383 : value&
1384 : push_back(
1385 : pilfered<value> pv);
1386 :
1387 : BOOST_JSON_DECL
1388 : iterator
1389 : insert(
1390 : const_iterator pos,
1391 : pilfered<value> pv);
1392 :
1393 : template<class InputIt>
1394 : iterator
1395 : insert(
1396 : const_iterator pos,
1397 : InputIt first, InputIt last,
1398 : std::input_iterator_tag);
1399 :
1400 : template<class InputIt>
1401 : iterator
1402 : insert(
1403 : const_iterator pos,
1404 : InputIt first, InputIt last,
1405 : std::forward_iterator_tag);
1406 :
1407 : BOOST_JSON_DECL
1408 : bool
1409 : equal(array const& other) const noexcept;
1410 : };
1411 :
1412 : } // namespace json
1413 : } // namespace boost
1414 :
1415 : // std::hash specialization
1416 : #ifndef BOOST_JSON_DOCS
1417 : namespace std {
1418 : template <>
1419 : struct hash< ::boost::json::array > {
1420 : BOOST_JSON_DECL
1421 : std::size_t
1422 : operator()(::boost::json::array const& ja) const noexcept;
1423 : };
1424 : } // std
1425 : #endif
1426 :
1427 : // Must be included here for this file to stand alone
1428 : #include <boost/json/value.hpp>
1429 :
1430 : // includes are at the bottom of <boost/json/value.hpp>
1431 :
1432 : #endif
|
