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		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
1433