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