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
34		a modifiable container. The interface and performance
35		characteristics are modeled after `std::vector<value>`.
36		\n
37		Elements are stored contiguously, which means that
38		they can be accessed not only through iterators, but
39		also using offsets to regular pointers to elements. A
40		pointer to an element of an @ref array may be passed to
41		any function that expects a pointer to @ref value.
42		\n
43		The storage of the array is handled automatically, being
44		expanded and contracted as needed. Arrays usually occupy
45		more space than array language constructs, because more
46		memory is allocated to handle future growth. This way an
47		array does not need to reallocate each time an element
48		is inserted, but only when the additional memory is used
49		up. The total amount of allocated memory can be queried
50		using the @ref capacity function. Extra memory can be
51		relinquished by calling @ref shrink_to_fit.
52		\n
53
54		Reallocations are usually costly operations in terms of
55		performance. The @ref reserve function can be used to
56		eliminate reallocations if the number of elements is
57		known beforehand.
58		\n
59		The complexity (efficiency) of common operations on
60		arrays is as follows:
61
62		@li Random access - constant *O(1)*.
63		@li Insertion or removal of elements at the
64		end - amortized constant *O(1)*.
65		@li Insertion or removal of elements - linear in
66		the distance to the end of the array *O(n)*.
67
68		@par Allocators
69
70		All elements stored in the container, and their
71		children if any, will use the same memory resource
72		that was used to construct the container.
73
74		@par Thread Safety
75
76		Non-const member functions may not be called
77		concurrently with any other member functions.
78
79		@par Satisfies
80		<a href="https://en.cppreference.com/w/cpp/named_req/ContiguousContainer"><em>ContiguousContainer</em></a>,
81		<a href="https://en.cppreference.com/w/cpp/named_req/ReversibleContainer"><em>ReversibleContainer</em></a>, and
82		<a href="https://en.cppreference.com/w/cpp/named_req/SequenceContainer"><em>SequenceContainer</em></a>.
83		*/
84		class array
85		{
86		struct table;
87		class revert_construct;
88		class revert_insert;
89		friend class value;
90
91		storage_ptr sp_; // must come first
92		kind k_ = kind::array; // must come second
93		table* t_;
94
95		BOOST_JSON_DECL
96		static table empty_;
97
98		inline
99		static
100		void
101		relocate(
102		value* dest,
103		value* src,
104		std::size_t n) noexcept;
105
106		inline
107		void
108		destroy(
109		value* first,
110		value* last) noexcept;
111
112		BOOST_JSON_DECL
113		void
114		destroy() noexcept;
115
116		BOOST_JSON_DECL
117		explicit
118		array(detail::unchecked_array&& ua);
119
120		public:
121		/// Associated [Allocator](https://en.cppreference.com/w/cpp/named_req/Allocator)
122		using allocator_type = container::pmr::polymorphic_allocator<value>;
123
124		/// The type used to represent unsigned integers
125		using size_type = std::size_t;
126
127		/// The type of each element
128		using value_type = value;
129
130		/// The type used to represent signed integers
131		using difference_type = std::ptrdiff_t;
132
133		/// A reference to an element
134		using reference = value&;
135
136		/// A const reference to an element
137		using const_reference = value const&;
138
139		/// A pointer to an element
140		using pointer = value*;
141
142		/// A const pointer to an element
143		using const_pointer = value const*;
144
145		/// A random access iterator to an element
146		using iterator = value*;
147
148		/// A random access const iterator to an element
149		using const_iterator = value const*;
150
151		/// A reverse random access iterator to an element
152		using reverse_iterator =
153		std::reverse_iterator<iterator>;
154
155		/// A reverse random access const iterator to an element
156		using const_reverse_iterator =
157		std::reverse_iterator<const_iterator>;
158
159		//------------------------------------------------------
160
161		/** Destructor.
162
163		The destructor for each element is called if needed,
164		any used memory is deallocated, and shared ownership
165		of the `boost::container::pmr::memory_resource` is released.
166
167		@par Complexity
168		Constant, or linear in @ref size().
169
170		@par Exception Safety
171		No-throw guarantee.
172		*/
173		BOOST_JSON_DECL
174		~array() noexcept;
175
176		//------------------------------------------------------
177
178		/** Constructor.
179
180		The constructed array is empty with zero
181		capacity, using the [default memory resource].
182
183		@par Complexity
184		Constant.
185
186		@par Exception Safety
187		No-throw guarantee.
188
189		[default memory resource]: json/allocators/storage_ptr.html#json.allocators.storage_ptr.default_memory_resource
190		*/
191	79	array() noexcept
192	79	: t_(&empty_)
193		{
194	79	}
195
196		/** Constructor.
197
198		The constructed array is empty with zero
199		capacity, using the specified memory resource.
200
201		@par Complexity
202		Constant.
203
204		@par Exception Safety
205		No-throw guarantee.
206
207		@param sp A pointer to the `boost::container::pmr::memory_resource`
208		to use. The container will acquire shared
209		ownership of the memory resource.
210		*/
211		explicit
212	682	array(storage_ptr sp) noexcept
213	682	: sp_(std::move(sp))
214	682	, k_(kind::array)
215	682	, t_(&empty_)
216		{
217	682	}
218
219		/** Constructor.
220
221		The array is constructed with `count`
222		copies of the value `v`, using the
223		specified memory resource.
224
225		@par Complexity
226		Linear in `count`
227
228		@par Exception Safety
229		Strong guarantee.
230		Calls to `memory_resource::allocate` may throw.
231
232		@param count The number of copies to insert.
233
234		@param v The value to be inserted.
235
236		@param sp A pointer to the `boost::container::pmr::memory_resource`
237		to use. The container will acquire shared
238		ownership of the memory resource.
239		*/
240		BOOST_JSON_DECL
241		array(
242		std::size_t count,
243		value const& v,
244		storage_ptr sp = {});
245
246		/** Constructor.
247
248		The array is constructed with `count` null values,
249		using the specified memory resource.
250
251		@par Complexity
252		Linear in `count`
253
254		@par Exception Safety
255		Strong guarantee.
256		Calls to `memory_resource::allocate` may throw.
257
258		@param count The number of nulls to insert.
259
260		@param sp A pointer to the `boost::container::pmr::memory_resource`
261		to use. The container will acquire shared
262		ownership of the memory resource.
263		*/
264		BOOST_JSON_DECL
265		array(
266		std::size_t count,
267		storage_ptr sp = {});
268
269		/** Constructor.
270
271		The array is constructed with the elements
272		in the range `{first, last)`, preserving order,
273		using the specified memory resource.
274
275		@par Constraints
276
277		@code
278		std::is_constructible_v<value, std::iterator_traits<InputIt>::reference>
279		@endcode
280
281		@par Complexity
282		Linear in `std::distance(first, last)`
283
284		@par Exception Safety
285		Strong guarantee.
286		Calls to `memory_resource::allocate` may throw.
287
288		@param first An input iterator pointing to the
289		first element to insert, or pointing to the end
290		of the range.
291
292		@param last An input iterator pointing to the end
293		of the range.
294
295		@param sp A pointer to the `boost::container::pmr::memory_resource`
296		to use. The container will acquire shared
297		ownership of the memory resource.
298
299		@tparam InputIt a type satisfying the requirements
300		of __InputIterator__.
301		*/
302		template<
303		class InputIt
304		#ifndef BOOST_JSON_DOCS
305		,class = typename std::enable_if<
306		std::is_constructible<value,
307		typename std::iterator_traits<
308		InputIt>::reference>::value>::type
309		#endif
310		>
311		array(
312		InputIt first, InputIt last,
313		storage_ptr sp = {});
314
315		/** Copy constructor.
316
317		The array is constructed with a copy of the
318		contents of `other`, using `other`'s memory resource.
319
320		@par Complexity
321		Linear in `other.size()`.
322
323		@par Exception Safety
324		Strong guarantee.
325		Calls to `memory_resource::allocate` may throw.
326
327		@param other The array to copy
328		*/
329		BOOST_JSON_DECL
330		array(array const& other);
331
332		/** Copy constructor.
333
334		The array is constructed with a copy of the
335		contents of `other`, using the specified memory resource.
336
337		@par Complexity
338		Linear in `other.size()`.
339
340		@par Exception Safety
341		Strong guarantee.
342		Calls to `memory_resource::allocate` may throw.
343
344		@param other The array to copy
345
346		@param sp A pointer to the `boost::container::pmr::memory_resource`
347		to use. The container will acquire shared
348		ownership of the memory resource.
349		*/
350		BOOST_JSON_DECL
351		array(
352		array const& other,
353		storage_ptr sp);
354
355		/** Pilfer constructor.
356
357		The array is constructed by acquiring ownership
358		of the contents of `other` using pilfer semantics.
359		This is more efficient than move construction, when
360		it is known that the moved-from object will be
361		immediately destroyed afterwards.
362
363		@par Complexity
364		Constant.
365
366		@par Exception Safety
367		No-throw guarantee.
368
369		@param other The value to pilfer. After pilfer
370		construction, `other` is not in a usable state
371		and may only be destroyed.
372
373		@see @ref pilfer,
374		<a href="http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0308r0.html">
375		Valueless Variants Considered Harmful</a>
376		*/
377	6	array(pilfered<array> other) noexcept
378	6	: sp_(std::move(other.get().sp_))
379	12	, t_(detail::exchange(
380	6	other.get().t_, &empty_))
381		{
382	6	}
383
384		/** Move constructor.
385
386		The array is constructed by acquiring ownership of
387		the contents of `other` and shared ownership of
388		`other`'s memory resource.
389
390		@note
391
392		After construction, the moved-from array behaves
393		as if newly constructed with its current storage
394		pointer.
395
396		@par Complexity
397		Constant.
398
399		@par Exception Safety
400		No-throw guarantee.
401
402		@param other The container to move
403		*/
404	188	array(array&& other) noexcept
405	188	: sp_(other.sp_)
406	376	, t_(detail::exchange(
407	188	other.t_, &empty_))
408		{
409	188	}
410
411		/** Move constructor.
412
413		The array is constructed with the contents of
414		`other` by move semantics, using the specified
415		memory resource:
416
417		@li If `*other.storage() == *sp`, ownership of
418		the underlying memory is transferred in constant
419		time, with no possibility of exceptions.
420		After construction, the moved-from array behaves
421		as if newly constructed with its current storage
422		pointer.
423
424		@li If `*other.storage() != *sp`, an
425		element-wise copy is performed, which may throw.
426		In this case, the moved-from array is not
427		changed.
428
429		@par Complexity
430		At most, linear in `other.size()`.
431
432		@par Exception Safety
433		Strong guarantee.
434		Calls to `memory_resource::allocate` may throw.
435
436		@param other The container to move
437
438		@param sp A pointer to the `boost::container::pmr::memory_resource`
439		to use. The container will acquire shared
440		ownership of the memory resource.
441		*/
442		BOOST_JSON_DECL
443		array(
444		array&& other,
445		storage_ptr sp);
446
447		/** Constructor.
448
449		The array is constructed with a copy of the values
450		in the initializer-list in order, using the
451		specified memory resource.
452
453		@par Complexity
454		Linear in `init.size()`.
455
456		@par Exception Safety
457		Strong guarantee.
458		Calls to `memory_resource::allocate` may throw.
459
460		@param init The initializer list to insert
461
462		@param sp A pointer to the `boost::container::pmr::memory_resource`
463		to use. The container will acquire shared
464		ownership of the memory resource.
465		*/
466		BOOST_JSON_DECL
467		array(
468		std::initializer_list<value_ref> init,
469		storage_ptr sp = {});
470
471		//------------------------------------------------------
472
473		/** Copy assignment.
474
475		The contents of the array are replaced with an
476		element-wise copy of `other`.
477
478		@par Complexity
479		Linear in @ref size() plus `other.size()`.
480
481		@par Exception Safety
482		Strong guarantee.
483		Calls to `memory_resource::allocate` may throw.
484
485		@param other The array to copy.
486		*/
487		BOOST_JSON_DECL
488		array&
489		operator=(array const& other);
490
491		/** Move assignment.
492
493		The contents of the array are replaced with the
494		contents of `other` using move semantics:
495
496		@li If `*other.storage() == *sp`, ownership of
497		the underlying memory is transferred in constant
498		time, with no possibility of exceptions.
499		After assignment, the moved-from array behaves
500		as if newly constructed with its current storage
501		pointer.
502
503		@li If `*other.storage() != *sp`, an
504		element-wise copy is performed, which may throw.
505		In this case, the moved-from array is not
506		changed.
507
508		@par Complexity
509		Constant, or linear in
510		`this->size()` plus `other.size()`.
511
512		@par Exception Safety
513		Strong guarantee.
514		Calls to `memory_resource::allocate` may throw.
515
516		@param other The array to move.
517		*/
518		BOOST_JSON_DECL
519		array&
520		operator=(array&& other);
521
522		/** Assignment.
523
524		The contents of the array are replaced with a
525		copy of the values in the initializer-list.
526
527		@par Complexity
528		Linear in `this->size()` plus `init.size()`.
529
530		@par Exception Safety
531		Strong guarantee.
532		Calls to `memory_resource::allocate` may throw.
533
534		@param init The initializer list to copy.
535		*/
536		BOOST_JSON_DECL
537		array&
538		operator=(
539		std::initializer_list<value_ref> init);
540
541		//------------------------------------------------------
542
543		/** Return the associated memory resource.
544
545		This function returns the `boost::container::pmr::memory_resource` used
546		by the container.
547
548		@par Complexity
549		Constant.
550
551		@par Exception Safety
552		No-throw guarantee.
553		*/
554		storage_ptr const&
555	15436	storage() const noexcept
556		{
557	15436	return sp_;
558		}
559
560		/** Return the associated allocator.
561
562		This function returns an instance of @ref allocator_type constructed
563		from the associated `boost::container::pmr::memory_resource`.
564
565		@par Complexity
566		Constant.
567
568		@par Exception Safety
569		No-throw guarantee.
570		*/
571		allocator_type
572	1	get_allocator() const noexcept
573		{
574	1	return sp_.get();
575		}
576
577		//------------------------------------------------------
578		//
579		// Element access
580		//
581		//------------------------------------------------------
582
583		/** Access an element, with bounds checking.
584
585		Returns `boost::system::result` containing a reference to the element
586		specified at location `pos`, if `pos` is within the range of the
587		container. Otherwise the result contains an `error_code`.
588
589		@par Exception Safety
590		No-throw guarantee.
591
592		@param pos A zero-based index.
593
594		@par Complexity
595		Constant.
596		*/
597		/** @{ */
598		BOOST_JSON_DECL
599		system::result<value&>
600		try_at(std::size_t pos) noexcept;
601
602		BOOST_JSON_DECL
603		system::result<value const&>
604		try_at(std::size_t pos) const noexcept;
605		/** @} */
606
607		/** Access an element, with bounds checking.
608
609		Returns a reference to the element specified at
610		location `pos`, with bounds checking. If `pos` is
611		not within the range of the container, an exception
612		of type `boost::system::system_error` is thrown.
613
614		@par Complexity
615		Constant.
616
617		@param pos A zero-based index.
618
619		@param loc `source_location` to use in thrown exception; the source
620		location of the call site by default.
621
622		@throw `boost::system::system_error` `pos >= size()`.
623		*/
624		/** @{ */
625		inline
626		value&
627		at(
628		std::size_t pos,
629		source_location const& loc = BOOST_CURRENT_LOCATION) &;
630
631		inline
632		value&&
633		at(
634		std::size_t pos,
635		source_location const& loc = BOOST_CURRENT_LOCATION) &&;
636
637		BOOST_JSON_DECL
638		value const&
639		at(
640		std::size_t pos,
641		source_location const& loc = BOOST_CURRENT_LOCATION) const&;
642		/** @} */
643
644		/** Access an element.
645
646		Returns a reference to the element specified at
647		location `pos`. No bounds checking is performed.
648
649		@par Precondition
650		`pos < size()`
651
652		@par Complexity
653		Constant.
654
655		@param pos A zero-based index
656		*/
657		/** @{ */
658		inline
659		value&
660		operator[](std::size_t pos) & noexcept;
661
662		inline
663		value&&
664		operator[](std::size_t pos) && noexcept;
665
666		inline
667		value const&
668		operator[](std::size_t pos) const& noexcept;
669		/** @} */
670
671		/** Access the first element.
672
673		Returns a reference to the first element.
674
675		@par Precondition
676		`not empty()`
677
678		@par Complexity
679		Constant.
680		*/
681		/** @{ */
682		inline
683		value&
684		front() & noexcept;
685
686		inline
687		value&&
688		front() && noexcept;
689
690		inline
691		value const&
692		front() const& noexcept;
693		/** @} */
694
695		/** Access the last element.
696
697		Returns a reference to the last element.
698
699		@par Precondition
700		`not empty()`
701
702		@par Complexity
703		Constant.
704		*/
705		/** @{ */
706		inline
707		value&
708		back() & noexcept;
709
710		inline
711		value&&
712		back() && noexcept;
713
714		inline
715		value const&
716		back() const& noexcept;
717		/** @} */
718
719		/** Access the underlying array directly.
720
721		Returns a pointer to the underlying array serving
722		as element storage. The value returned is such that
723		the range `{data(), data() + size())` is always a
724		valid range, even if the container is empty.
725
726		@par Complexity
727		Constant.
728
729		@par Exception Safety
730		No-throw guarantee.
731
732		@note
733
734		If `size() == 0`, the function may or may not return
735		a null pointer.
736		*/
737		inline
738		value*
739		data() noexcept;
740
741		/** Access the underlying array directly.
742
743		Returns a pointer to the underlying array serving
744		as element storage. The value returned is such that
745		the range `{data(), data() + size())` is always a
746		valid range, even if the container is empty.
747
748		@par Complexity
749		Constant.
750
751		@par Exception Safety
752		No-throw guarantee.
753
754		@note
755
756		If `size() == 0`, the function may or may not return
757		a null pointer.
758		*/
759		inline
760		value const*
761		data() const noexcept;
762
763		/** Return a pointer to an element, or nullptr if the index is invalid
764
765		This function returns a pointer to the element
766		at index `pos` when the index is less then the size
767		of the container. Otherwise it returns null.
768
769		@par Example
770		@code
771		if( auto p = arr.if_contains( 1 ) )
772		std::cout << *p;
773		@endcode
774
775		@par Complexity
776		Constant.
777
778		@par Exception Safety
779		No-throw guarantee.
780
781		@param pos The index of the element to return.
782		*/
783		inline
784		value const*
785		if_contains(std::size_t pos) const noexcept;
786
787		/** Return a pointer to an element, or nullptr if the index is invalid
788
789		This function returns a pointer to the element
790		at index `pos` when the index is less then the size
791		of the container. Otherwise it returns null.
792
793		@par Example
794		@code
795		if( auto p = arr.if_contains( 1 ) )
796		std::cout << *p;
797		@endcode
798
799		@par Complexity
800		Constant.
801
802		@par Exception Safety
803		No-throw guarantee.
804
805		@param pos The index of the element to return.
806		*/
807		inline
808		value*
809		if_contains(std::size_t pos) noexcept;
810
811		//------------------------------------------------------
812		//
813		// Iterators
814		//
815		//------------------------------------------------------
816
817		/** Return an iterator to the first element.
818
819		If the container is empty, @ref end() is returned.
820
821		@par Complexity
822		Constant.
823
824		@par Exception Safety
825		No-throw guarantee.
826		*/
827		inline
828		iterator
829		begin() noexcept;
830
831		/** Return a const iterator to the first element.
832
833		If the container is empty, @ref end() is returned.
834
835		@par Complexity
836		Constant.
837
838		@par Exception Safety
839		No-throw guarantee.
840		*/
841		inline
842		const_iterator
843		begin() const noexcept;
844
845		/** Return a const iterator to the first element.
846
847		If the container is empty, @ref cend() is returned.
848
849		@par Complexity
850		Constant.
851
852		@par Exception Safety
853		No-throw guarantee.
854		*/
855		inline
856		const_iterator
857		cbegin() const noexcept;
858
859		/** Return an iterator to the element following the last element.
860
861		The element acts as a placeholder; attempting
862		to access it results in undefined behavior.
863
864		@par Complexity
865		Constant.
866
867		@par Exception Safety
868		No-throw guarantee.
869		*/
870		inline
871		iterator
872		end() noexcept;
873
874		/** Return a const iterator to the element following the last element.
875
876		The element acts as a placeholder; attempting
877		to access it results in undefined behavior.
878
879		@par Complexity
880		Constant.
881
882		@par Exception Safety
883		No-throw guarantee.
884		*/
885		inline
886		const_iterator
887		end() const noexcept;
888
889		/** Return a const iterator to the element following the last element.
890
891		The element acts as a placeholder; attempting
892		to access it results in undefined behavior.
893
894		@par Complexity
895		Constant.
896
897		@par Exception Safety
898		No-throw guarantee.
899		*/
900		inline
901		const_iterator
902		cend() const noexcept;
903
904		/** Return a reverse iterator to the first element of the reversed container.
905
906		The pointed-to element corresponds to the
907		last element of the non-reversed container.
908		If the container is empty, @ref rend() is returned.
909
910		@par Complexity
911		Constant.
912
913		@par Exception Safety
914		No-throw guarantee.
915		*/
916		inline
917		reverse_iterator
918		rbegin() noexcept;
919
920		/** Return a const reverse iterator to the first element of the reversed container.
921
922		The pointed-to element corresponds to the
923		last element of the non-reversed container.
924		If the container is empty, @ref rend() is returned.
925
926		@par Complexity
927		Constant.
928
929		@par Exception Safety
930		No-throw guarantee.
931		*/
932		inline
933		const_reverse_iterator
934		rbegin() const noexcept;
935
936		/** Return a const reverse iterator to the first element of the reversed container.
937
938		The pointed-to element corresponds to the
939		last element of the non-reversed container.
940		If the container is empty, @ref crend() is returned.
941
942		@par Complexity
943		Constant.
944
945		@par Exception Safety
946		No-throw guarantee.
947		*/
948		inline
949		const_reverse_iterator
950		crbegin() const noexcept;
951
952		/** Return a reverse iterator to the element following the last element of the reversed container.
953
954		The pointed-to element corresponds to the element
955		preceding the first element of the non-reversed container.
956		The element acts as a placeholder; attempting
957		to access it results in undefined behavior.
958
959		@par Complexity
960		Constant.
961
962		@par Exception Safety
963		No-throw guarantee.
964		*/
965		inline
966		reverse_iterator
967		rend() noexcept;
968
969		/** Return a const reverse iterator to the element following the last element of the reversed container.
970
971		The pointed-to element corresponds to the element
972		preceding the first element of the non-reversed container.
973		The element acts as a placeholder; attempting
974		to access it results in undefined behavior.
975
976		@par Complexity
977		Constant.
978
979		@par Exception Safety
980		No-throw guarantee.
981		*/
982		inline
983		const_reverse_iterator
984		rend() const noexcept;
985
986		/** Return a const reverse iterator to the element following the last element of the reversed container.
987
988		The pointed-to element corresponds to the element
989		preceding the first element of the non-reversed container.
990		The element acts as a placeholder; attempting
991		to access it results in undefined behavior.
992
993		@par Complexity
994		Constant.
995
996		@par Exception Safety
997		No-throw guarantee.
998		*/
999		inline
1000		const_reverse_iterator
1001		crend() const noexcept;
1002
1003		//------------------------------------------------------
1004		//
1005		// Capacity
1006		//
1007		//------------------------------------------------------
1008
1009		/** Return the number of elements in the array.
1010
1011		This returns the number of elements in the array.
1012		The value returned may be different from the number
1013		returned from @ref capacity.
1014
1015		@par Complexity
1016		Constant.
1017
1018		@par Exception Safety
1019		No-throw guarantee.
1020		*/
1021		inline
1022		std::size_t
1023		size() const noexcept;
1024
1025		/** Return the maximum number of elements any array can hold.
1026
1027		The maximum is an implementation-defined number.
1028		This value is a theoretical limit; at runtime,
1029		the actual maximum size may be less due to
1030		resource limits.
1031
1032		@par Complexity
1033		Constant.
1034
1035		@par Exception Safety
1036		No-throw guarantee.
1037		*/
1038		static
1039		inline
1040		constexpr
1041		std::size_t
1042		max_size() noexcept;
1043
1044		/** Return the number of elements that can be held in currently allocated memory.
1045
1046		This number may be larger than the value returned
1047		by @ref size().
1048
1049		@par Complexity
1050		Constant.
1051
1052		@par Exception Safety
1053		No-throw guarantee.
1054		*/
1055		inline
1056		std::size_t
1057		capacity() const noexcept;
1058
1059		/** Check if the array has no elements.
1060
1061		Returns `true` if there are no elements in the
1062		array, i.e. @ref size() returns 0.
1063
1064		@par Complexity
1065		Constant.
1066
1067		@par Exception Safety
1068		No-throw guarantee.
1069		*/
1070		inline
1071		bool
1072		empty() const noexcept;
1073
1074		/** Increase the capacity to at least a certain amount.
1075
1076		This increases the @ref capacity() to a value
1077		that is greater than or equal to `new_capacity`.
1078		If `new_capacity > capacity()`, new memory is
1079		allocated. Otherwise, the call has no effect.
1080		The number of elements and therefore the
1081		@ref size() of the container is not changed.
1082		\n
1083		If new memory is allocated, all iterators
1084		including any past-the-end iterators, and all
1085		references to the elements are invalidated.
1086		Otherwise, no iterators or references are
1087		invalidated.
1088
1089		@par Complexity
1090		At most, linear in @ref size().
1091
1092		@par Exception Safety
1093		Strong guarantee.
1094		Calls to `memory_resource::allocate` may throw.
1095
1096		@param new_capacity The new capacity of the array.
1097
1098		@throw `boost::system::system_error` `new_capacity > max_size()`.
1099		*/
1100		inline
1101		void
1102		reserve(std::size_t new_capacity);
1103
1104		/** Request the removal of unused capacity.
1105
1106		This performs a non-binding request to reduce the
1107		capacity to the current size. The request may or
1108		may not be fulfilled. If reallocation occurs, all
1109		iterators including any past-the-end iterators,
1110		and all references to the elements are invalidated.
1111		Otherwise, no iterators or references are
1112		invalidated.
1113
1114		@par Complexity
1115		At most, linear in @ref size().
1116
1117		@par Exception Safety
1118		No-throw guarantee.
1119		*/
1120		BOOST_JSON_DECL
1121		void
1122		shrink_to_fit() noexcept;
1123
1124		//------------------------------------------------------
1125		//
1126		// Modifiers
1127		//
1128		//------------------------------------------------------
1129
1130		/** Clear the contents.
1131
1132		Erases all elements from the container. After this
1133		call, @ref size() returns zero but @ref capacity()
1134		is unchanged. All references, pointers, or iterators
1135		referring to contained elements are invalidated. Any
1136		past-the-end iterators are also invalidated.
1137
1138		@par Complexity
1139		Linear in @ref size().
1140
1141		@par Exception Safety
1142		No-throw guarantee.
1143		*/
1144		BOOST_JSON_DECL
1145		void
1146		clear() noexcept;
1147
1148		/** Insert elements before the specified location.
1149
1150		This inserts a copy of `v` before `pos`.
1151		If `capacity() < size() + 1`, a reallocation
1152		occurs first, and all iterators and references
1153		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		Constant plus linear in `std::distance(pos, end())`.
1160
1161		@par Exception Safety
1162		Strong guarantee.
1163		Calls to `memory_resource::allocate` may throw.
1164
1165		@param pos Iterator before which the content will
1166		be inserted. This may be the @ref end() iterator.
1167
1168		@param v The value to insert. A copy will be made
1169		using container's associated `boost::container::pmr::memory_resource`.
1170
1171		@return An iterator to the inserted value
1172		*/
1173		BOOST_JSON_DECL
1174		iterator
1175		insert(
1176		const_iterator pos,
1177		value const& v);
1178
1179		/** Insert elements before the specified location.
1180
1181		This inserts `v` before `pos` via move-construction.
1182		If `capacity() < size() + 1`, a reallocation occurs
1183		first, and all iterators and references are
1184		invalidated.
1185		Otherwise, only the iterators and references from
1186		the insertion point forward are invalidated. All
1187		past-the-end iterators are also invalidated.
1188
1189		@par Complexity
1190		Constant plus linear in `std::distance(pos, end())`.
1191
1192		@par Exception Safety
1193		Strong guarantee.
1194		Calls to `memory_resource::allocate` may throw.
1195
1196		@param pos Iterator before which the content will
1197		be inserted. This may be the @ref end() iterator.
1198
1199		@param v The value to insert. Ownership of the
1200		value will be transferred via move construction,
1201		using the container's
1202		associated `boost::container::pmr::memory_resource`.
1203
1204		@return An iterator to the inserted value
1205		*/
1206		BOOST_JSON_DECL
1207		iterator
1208		insert(
1209		const_iterator pos,
1210		value&& v);
1211
1212		/** Insert elements before the specified location.
1213
1214		This inserts `count` copies of `v` before `pos`.
1215		If `capacity() < size() + count`, a reallocation
1216		occurs first, and all iterators and references are
1217		invalidated.
1218		Otherwise, only the iterators and references from
1219		the insertion point forward are invalidated. All
1220		past-the-end iterators are also invalidated.
1221
1222		@par Complexity
1223		Linear in `count + std::distance(pos, end())`.
1224
1225		@par Exception Safety
1226		Strong guarantee.
1227		Calls to `memory_resource::allocate` may throw.
1228
1229		@param pos Iterator before which the content will
1230		be inserted. This may be the @ref end() iterator.
1231
1232		@param count The number of copies to insert.
1233
1234		@param v The value to insert. Copies will be made
1235		using the container's
1236		associated `boost::container::pmr::memory_resource`.
1237
1238		@return An iterator to the first inserted value,
1239		or `pos` if `count == 0`.
1240		*/
1241		BOOST_JSON_DECL
1242		iterator
1243		insert(
1244		const_iterator pos,
1245		std::size_t count,
1246		value const& v);
1247
1248		/** Insert elements before the specified location.
1249
1250		The elements in the range `{first, last)` are
1251		inserted in order.
1252		If `capacity() < size() + std::distance(first, last)`,
1253		a reallocation occurs first, and all iterators and
1254		references are invalidated.
1255		Otherwise, only the iterators and references from
1256		the insertion point forward are invalidated. All
1257		past-the-end iterators are also invalidated.
1258
1259		@par Precondition
1260		`first` and `last` are not iterators into `*this`.
1261
1262		@par Constraints
1263		@code
1264		not std::is_convertible_v<InputIt, value>
1265		@endcode
1266
1267		@par Mandates
1268		@code
1269		std::is_constructible_v<value, std::iterator_traits<InputIt>::reference>
1270		@endcode
1271
1272		@par Complexity
1273		Linear in `std::distance(first, last) + std::distance(pos, end())`.
1274
1275		@par Exception Safety
1276		Strong guarantee.
1277		Calls to `memory_resource::allocate` may throw.
1278
1279		@return An iterator to the first inserted value, or
1280		`pos` if `first == last`.
1281
1282		@param pos Iterator before which the content will
1283		be inserted. This may be the @ref end() iterator.
1284
1285		@param first An input iterator pointing to the first
1286		element to insert, or pointing to the end of the range.
1287
1288		@param last An input iterator pointing to the end
1289		of the range.
1290
1291		@tparam InputIt a type satisfying the requirements
1292		of __InputIterator__.
1293		*/
1294		template<
1295		class InputIt
1296		#ifndef BOOST_JSON_DOCS
1297		,class = typename std::enable_if<
1298		std::is_constructible<value,
1299		typename std::iterator_traits<
1300		InputIt>::reference>::value>::type
1301		#endif
1302		>
1303		iterator
1304		insert(
1305		const_iterator pos,
1306		InputIt first, InputIt last);
1307
1308		/** Insert elements before the specified location.
1309
1310		The elements in the initializer list `init` are
1311		inserted in order.
1312		If `capacity() < size() + init.size()`,
1313		a reallocation occurs first, and all iterators and
1314		references are invalidated.
1315		Otherwise, only the iterators and references from
1316		the insertion point forward are invalidated. All
1317		past-the-end iterators are also invalidated.
1318
1319		@par Complexity
1320		Linear in `init.size() + std::distance(pos, end())`.
1321
1322		@par Exception Safety
1323		Strong guarantee.
1324		Calls to `memory_resource::allocate` may throw.
1325
1326		@param pos Iterator before which the content will
1327		be inserted. This may be the @ref end() iterator.
1328
1329		@param init The initializer list to insert
1330
1331		@return An iterator to the first inserted value, or
1332		`pos` if `init.size() == 0`.
1333		*/
1334		BOOST_JSON_DECL
1335		iterator
1336		insert(
1337		const_iterator pos,
1338		std::initializer_list<value_ref> init);
1339
1340		/** Insert a constructed element in-place.
1341
1342		Inserts a new element into the container directly before
1343		`pos`. The element is constructed using placement-new
1344		with the parameter `std::forward<Arg>(arg)`.
1345		If `capacity() < size() + 1`,
1346		a reallocation occurs first, and all iterators and
1347		references are invalidated.
1348		Otherwise, only the iterators and references from
1349		the insertion point forward are invalidated. All
1350		past-the-end iterators are also invalidated.
1351
1352		@par Complexity
1353		Constant plus linear in `std::distance(pos, end())`.
1354
1355		@par Exception Safety
1356		Strong guarantee.
1357		Calls to `memory_resource::allocate` may throw.
1358
1359		@param pos Iterator before which the element will
1360		be inserted. This may be the @ref end() iterator.
1361
1362		@param arg The argument to forward to the @ref value
1363		constructor.
1364
1365		@return An iterator to the inserted element
1366		*/
1367		template<class Arg>
1368		iterator
1369		emplace(
1370		const_iterator pos,
1371		Arg&& arg);
1372
1373		/** Erase elements from the container.
1374
1375		The element at `pos` is removed.
1376
1377		@par Complexity
1378		Constant plus linear in `std::distance(pos, end())`
1379
1380		@par Exception Safety
1381		No-throw guarantee.
1382
1383		@param pos Iterator to the element to remove
1384
1385		@return Iterator following the last removed element.
1386		If the iterator `pos` refers to the last element,
1387		the @ref end() iterator is returned.
1388		*/
1389		BOOST_JSON_DECL
1390		iterator
1391		erase(const_iterator pos) noexcept;
1392
1393		/** Erase elements from the container.
1394
1395		The elements in the range `{first, last)` are removed.
1396
1397		@par Complexity
1398		Linear in `std::distance(first, end())`
1399
1400		@par Exception Safety
1401		No-throw guarantee.
1402
1403		@param first An iterator pointing to the first
1404		element to erase, or pointing to the end of the range.
1405
1406		@param last An iterator pointing to one past the
1407		last element to erase, or pointing to the end of the
1408		range.
1409
1410		@return Iterator following the last removed element.
1411		If the iterator `last` refers to the last element,
1412		the @ref end() iterator is returned.
1413		*/
1414		BOOST_JSON_DECL
1415		iterator
1416		erase(
1417		const_iterator first,
1418		const_iterator last) noexcept;
1419
1420		/** Add an element to the end.
1421
1422		This appends a copy of `v` to the container's
1423		elements.
1424		If `capacity() < size() + 1`, a reallocation
1425		occurs first, and all iterators and references
1426		are invalidated. Any past-the-end iterators are
1427		always invalidated.
1428
1429		@par Complexity
1430		Amortized constant.
1431
1432		@par Exception Safety
1433		Strong guarantee.
1434		Calls to `memory_resource::allocate` may throw.
1435
1436		@param v The value to insert. A copy will be made using the container's
1437		associated `boost::container::pmr::memory_resource`.
1438		*/
1439		BOOST_JSON_DECL
1440		void
1441		push_back(value const& v);
1442
1443		/** Add an element to the end.
1444
1445		This appends `v` to the container's elements via
1446		move-construction.
1447		If `capacity() < size() + 1`, a reallocation
1448		occurs first, and all iterators and references
1449		are invalidated. Any past-the-end iterators are
1450		always invalidated.
1451
1452		@par Complexity
1453		Amortized constant.
1454
1455		@par Exception Safety
1456		Strong guarantee.
1457		Calls to `memory_resource::allocate` may throw.
1458
1459		@param v The value to insert. Ownership of the value will be
1460		transferred via move construction, using the container's
1461		associated `boost::container::pmr::memory_resource`.
1462		*/
1463		BOOST_JSON_DECL
1464		void
1465		push_back(value&& v);
1466
1467		/** Append a constructed element in-place.
1468
1469		Appends a new element to the end of the container's
1470		list of elements.
1471		The element is constructed using placement-new
1472		with the parameter `std::forward<Arg>(arg)`.
1473		If `capacity() < size() + 1`,
1474		a reallocation occurs first, and all iterators and
1475		references are invalidated.
1476		Otherwise, only the iterators and references from
1477		the insertion point forward are invalidated. All
1478		past-the-end iterators are also invalidated.
1479
1480		@par Complexity
1481		Amortized constant.
1482
1483		@par Exception Safety
1484		Strong guarantee.
1485		Calls to `memory_resource::allocate` may throw.
1486
1487		@param arg The argument to forward to the @ref value
1488		constructor.
1489
1490		@return A reference to the inserted element
1491		*/
1492		template<class Arg>
1493		value&
1494		emplace_back(Arg&& arg);
1495
1496		/** Remove the last element
1497
1498		The last element of the container is erased.
1499
1500		@par Precondition
1501		`not empty()`
1502
1503		@par Exception Safety
1504		No-throw guarantee.
1505		*/
1506		BOOST_JSON_DECL
1507		void
1508		pop_back() noexcept;
1509
1510		/** Change the number of elements stored.
1511
1512		Resizes the container to contain `count` elements.
1513		If `capacity() < size() + count`, a reallocation
1514		occurs first, and all iterators and references
1515		are invalidated. Any past-the-end iterators are
1516		always invalidated.
1517
1518		@li If `size() > count`, the container is reduced
1519		to its first `count` elements.
1520
1521		@li If `size() < count`, additional null values
1522		are appended.
1523
1524		@par Complexity
1525		Linear in `abs(size() - count)`, plus the cost of
1526		reallocation if @ref capacity() is less than `count`.
1527
1528		@par Exception Safety
1529		Strong guarantee.
1530		Calls to `memory_resource::allocate` may throw.
1531
1532		@param count The new size of the container.
1533		*/
1534		BOOST_JSON_DECL
1535		void
1536		resize(std::size_t count);
1537
1538		/** Change the number of elements stored.
1539
1540		Resizes the container to contain `count` elements.
1541		If `capacity() < size() + count`, a reallocation
1542		occurs first, and all iterators and references
1543		are invalidated. Any past-the-end iterators are
1544		always invalidated.
1545
1546		@li If `size() > count`, the container is reduced
1547		to its first `count` elements.
1548
1549		@li If `size() < count`, additional copies of `v`
1550		are appended.
1551
1552		@par Complexity
1553		Linear in `abs(size() - count)`, plus the cost of
1554		reallocation if @ref capacity() is less than `count`.
1555
1556		@par Exception Safety
1557		Strong guarantee.
1558		Calls to `memory_resource::allocate` may throw.
1559
1560		@param count The new size of the container.
1561
1562		@param v The @ref value to copy into the new elements.
1563		*/
1564		BOOST_JSON_DECL
1565		void
1566		resize(
1567		std::size_t count,
1568		value const& v);
1569
1570		/** Swap the contents.
1571
1572		Exchanges the contents of this array with another
1573		array. Ownership of the respective
1574		`boost::container::pmr::memory_resource` objects is not transferred.
1575
1576		@li If `*other.storage() == *this->storage()`,
1577		ownership of the underlying memory is swapped in
1578		constant time, with no possibility of exceptions.
1579		All iterators and references remain valid.
1580
1581		@li If `*other.storage() != *this->storage()`,
1582		the contents are logically swapped by making copies,
1583		which can throw. In this case all iterators and
1584		references are invalidated.
1585
1586		@par Complexity
1587		Constant or linear in @ref size() plus `other.size()`.
1588
1589		@par Exception Safety
1590		Strong guarantee.
1591		Calls to `memory_resource::allocate` may throw.
1592
1593		@param other The value to swap with.
1594		If `this == &other`, this function call has no effect.
1595		*/
1596		BOOST_JSON_DECL
1597		void
1598		swap(array& other);
1599
1600		/** Exchange the given values.
1601
1602		Exchanges the contents of the array `lhs` with another array `rhs`.
1603		Ownership of the respective `boost::container::pmr::memory_resource`
1604		objects is not transferred.
1605
1606		@li If `*lhs.storage() == *rhs.storage()`,
1607		ownership of the underlying memory is swapped in
1608		constant time, with no possibility of exceptions.
1609		All iterators and references remain valid.
1610
1611		@li If `*lhs.storage() != *rhs.storage()`,
1612		the contents are logically swapped by making a copy,
1613		which can throw. In this case all iterators and
1614		references are invalidated.
1615
1616		@par Effects
1617		@code
1618		lhs.swap( rhs );
1619		@endcode
1620
1621		@par Complexity
1622		Constant or linear in `lhs.size() + rhs.size()`.
1623
1624		@par Exception Safety
1625		Strong guarantee.
1626		Calls to `memory_resource::allocate` may throw.
1627
1628		@param lhs The array to exchange.
1629
1630		@param rhs The array to exchange.
1631		If `&lhs == &rhs`, this function call has no effect.
1632
1633		@see @ref array::swap
1634		*/
1635		friend
1636		void
1637	1	swap(array& lhs, array& rhs)
1638		{
1639	1	lhs.swap(rhs);
1640	1	}
1641
1642		/** Return `true` if two arrays are equal.
1643
1644		Arrays are equal when their sizes are
1645		the same, and they are element-for-element
1646		equal in order.
1647
1648		@par Effects
1649		`return std::equal( lhs.begin(), lhs.end(), rhs.begin(), rhs.end() );`
1650
1651		@par Complexity
1652		Constant or linear in `lhs.size()`.
1653
1654		@par Exception Safety
1655		No-throw guarantee.
1656		*/
1657		// inline friend speeds up overload resolution
1658		friend
1659		bool
1660	88	operator==(
1661		array const& lhs,
1662		array const& rhs) noexcept
1663		{
1664	88	return lhs.equal(rhs);
1665		}
1666
1667		/** Return `true` if two arrays are not equal.
1668
1669		Arrays are equal when their sizes are
1670		the same, and they are element-for-element
1671		equal in order.
1672
1673		@par Effects
1674		`return ! std::equal( lhs.begin(), lhs.end(), rhs.begin(), rhs.end() );`
1675
1676		@par Complexity
1677		Constant or linear in `lhs.size()`.
1678
1679		@par Exception Safety
1680		No-throw guarantee.
1681		*/
1682		// inline friend speeds up overload resolution
1683		friend
1684		bool
1685	9	operator!=(
1686		array const& lhs,
1687		array const& rhs) noexcept
1688		{
1689	9	return ! (lhs == rhs);
1690		}
1691
1692		/** Serialize @ref array to an output stream.
1693
1694		This function serializes an `array` as JSON into the output stream.
1695
1696		@return Reference to `os`.
1697
1698		@par Complexity
1699		Constant or linear in the size of `arr`.
1700
1701		@par Exception Safety
1702		Strong guarantee.
1703		Calls to `memory_resource::allocate` may throw.
1704
1705		@param os The output stream to serialize to.
1706
1707		@param arr The value to serialize.
1708		*/
1709		BOOST_JSON_DECL
1710		friend
1711		std::ostream&
1712		operator<<(
1713		std::ostream& os,
1714		array const& arr);
1715
1716		private:
1717		template<class It>
1718		using iter_cat = typename
1719		std::iterator_traits<It>::iterator_category;
1720
1721		template<class InputIt>
1722		array(
1723		InputIt first, InputIt last,
1724		storage_ptr sp,
1725		std::input_iterator_tag);
1726
1727		template<class InputIt>
1728		array(
1729		InputIt first, InputIt last,
1730		storage_ptr sp,
1731		std::forward_iterator_tag);
1732
1733		inline
1734		std::size_t
1735		growth(std::size_t new_size) const;
1736
1737		BOOST_JSON_DECL
1738		void
1739		reserve_impl(
1740		std::size_t new_capacity);
1741
1742		BOOST_JSON_DECL
1743		value&
1744		push_back(
1745		pilfered<value> pv);
1746
1747		BOOST_JSON_DECL
1748		iterator
1749		insert(
1750		const_iterator pos,
1751		pilfered<value> pv);
1752
1753		template<class InputIt>
1754		iterator
1755		insert(
1756		const_iterator pos,
1757		InputIt first, InputIt last,
1758		std::input_iterator_tag);
1759
1760		template<class InputIt>
1761		iterator
1762		insert(
1763		const_iterator pos,
1764		InputIt first, InputIt last,
1765		std::forward_iterator_tag);
1766
1767		BOOST_JSON_DECL
1768		bool
1769		equal(array const& other) const noexcept;
1770		};
1771
1772		} // namespace json
1773		} // namespace boost
1774
1775		// std::hash specialization
1776		#ifndef BOOST_JSON_DOCS
1777		namespace std {
1778		template <>
1779		struct hash< ::boost::json::array > {
1780		BOOST_JSON_DECL
1781		std::size_t
1782		operator()(::boost::json::array const& ja) const noexcept;
1783		};
1784		} // std
1785		#endif
1786
1787		// Must be included here for this file to stand alone
1788		#include <boost/json/value.hpp>
1789
1790		// includes are at the bottom of <boost/json/value.hpp>
1791
1792		#endif
1793