GCC Code Coverage Report

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