array.hpp

100.0% Lines (29/29) 100.0% Functions (9/9) -% Branches (0/0)

Covered Uncovered

array.hpp

29 covered 0 uncovered

Line	Hits	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		*/
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