1// Pair implementation -*- C++ -*- 
2 
3// Copyright (C) 2001-2019 Free Software Foundation, Inc. 
4// 
5// This file is part of the GNU ISO C++ Library. This library is free 
6// software; you can redistribute it and/or modify it under the 
7// terms of the GNU General Public License as published by the 
8// Free Software Foundation; either version 3, or (at your option) 
9// any later version. 
10 
11// This library is distributed in the hope that it will be useful, 
12// but WITHOUT ANY WARRANTY; without even the implied warranty of 
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 
14// GNU General Public License for more details. 
15 
16// Under Section 7 of GPL version 3, you are granted additional 
17// permissions described in the GCC Runtime Library Exception, version 
18// 3.1, as published by the Free Software Foundation. 
19 
20// You should have received a copy of the GNU General Public License and 
21// a copy of the GCC Runtime Library Exception along with this program; 
22// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 
23// <http://www.gnu.org/licenses/>. 
24 
25/* 
26 * 
27 * Copyright (c) 1994 
28 * Hewlett-Packard Company 
29 * 
30 * Permission to use, copy, modify, distribute and sell this software 
31 * and its documentation for any purpose is hereby granted without fee, 
32 * provided that the above copyright notice appear in all copies and 
33 * that both that copyright notice and this permission notice appear 
34 * in supporting documentation. Hewlett-Packard Company makes no 
35 * representations about the suitability of this software for any 
36 * purpose. It is provided "as is" without express or implied warranty. 
37 * 
38 * 
39 * Copyright (c) 1996,1997 
40 * Silicon Graphics Computer Systems, Inc. 
41 * 
42 * Permission to use, copy, modify, distribute and sell this software 
43 * and its documentation for any purpose is hereby granted without fee, 
44 * provided that the above copyright notice appear in all copies and 
45 * that both that copyright notice and this permission notice appear 
46 * in supporting documentation. Silicon Graphics makes no 
47 * representations about the suitability of this software for any 
48 * purpose. It is provided "as is" without express or implied warranty. 
49 */ 
50 
51/** @file bits/stl_pair.h 
52 * This is an internal header file, included by other library headers. 
53 * Do not attempt to use it directly. @headername{utility} 
54 */ 
55 
56#ifndef _STL_PAIR_H 
57#define _STL_PAIR_H 1 
58 
59#include <bits/move.h> // for std::move / std::forward, and std::swap 
60 
61#if __cplusplus >= 201103L 
62#include <type_traits> // for std::__decay_and_strip too 
63#endif 
64 
65namespace std _GLIBCXX_VISIBILITY(default) 
66{ 
67_GLIBCXX_BEGIN_NAMESPACE_VERSION 
68 
69 /** 
70 * @addtogroup utilities 
71 * @{ 
72 */ 
73 
74#if __cplusplus >= 201103L 
75 /// piecewise_construct_t 
76 struct piecewise_construct_t { explicit piecewise_construct_t() = default; }; 
77 
78 /// piecewise_construct 
79 _GLIBCXX17_INLINE constexpr piecewise_construct_t piecewise_construct = 
80 piecewise_construct_t(); 
81 
82 // Forward declarations. 
83 template<typename...> 
84 class tuple; 
85 
86 template<std::size_t...> 
87 struct _Index_tuple; 
88 
89 // Concept utility functions, reused in conditionally-explicit 
90 // constructors. 
91 // See PR 70437, don't look at is_constructible or 
92 // is_convertible if the types are the same to 
93 // avoid querying those properties for incomplete types. 
94 template <bool, typename _T1, typename _T2> 
95 struct _PCC 
96 { 
97 template <typename _U1, typename _U2> 
98 static constexpr bool _ConstructiblePair() 
99 { 
100 return __and_<is_constructible<_T1, const _U1&>, 
101 is_constructible<_T2, const _U2&>>::value; 
102 } 
103 
104 template <typename _U1, typename _U2> 
105 static constexpr bool _ImplicitlyConvertiblePair() 
106 { 
107 return __and_<is_convertible<const _U1&, _T1>, 
108 is_convertible<const _U2&, _T2>>::value; 
109 } 
110 
111 template <typename _U1, typename _U2> 
112 static constexpr bool _MoveConstructiblePair() 
113 { 
114 return __and_<is_constructible<_T1, _U1&&>, 
115 is_constructible<_T2, _U2&&>>::value; 
116 } 
117 
118 template <typename _U1, typename _U2> 
119 static constexpr bool _ImplicitlyMoveConvertiblePair() 
120 { 
121 return __and_<is_convertible<_U1&&, _T1>, 
122 is_convertible<_U2&&, _T2>>::value; 
123 } 
124 
125 template <bool __implicit, typename _U1, typename _U2> 
126 static constexpr bool _CopyMovePair() 
127 { 
128 using __do_converts = __and_<is_convertible<const _U1&, _T1>, 
129 is_convertible<_U2&&, _T2>>; 
130 using __converts = typename conditional<__implicit, 
131 __do_converts, 
132 __not_<__do_converts>>::type; 
133 return __and_<is_constructible<_T1, const _U1&>, 
134 is_constructible<_T2, _U2&&>, 
135 __converts 
136 >::value; 
137 } 
138 
139 template <bool __implicit, typename _U1, typename _U2> 
140 static constexpr bool _MoveCopyPair() 
141 { 
142 using __do_converts = __and_<is_convertible<_U1&&, _T1>, 
143 is_convertible<const _U2&, _T2>>; 
144 using __converts = typename conditional<__implicit, 
145 __do_converts, 
146 __not_<__do_converts>>::type; 
147 return __and_<is_constructible<_T1, _U1&&>, 
148 is_constructible<_T2, const _U2&&>, 
149 __converts 
150 >::value; 
151 } 
152 }; 
153 
154 template <typename _T1, typename _T2> 
155 struct _PCC<false, _T1, _T2> 
156 { 
157 template <typename _U1, typename _U2> 
158 static constexpr bool _ConstructiblePair() 
159 { 
160 return false; 
161 } 
162 
163 template <typename _U1, typename _U2> 
164 static constexpr bool _ImplicitlyConvertiblePair() 
165 { 
166 return false; 
167 } 
168 
169 template <typename _U1, typename _U2> 
170 static constexpr bool _MoveConstructiblePair() 
171 { 
172 return false; 
173 } 
174 
175 template <typename _U1, typename _U2> 
176 static constexpr bool _ImplicitlyMoveConvertiblePair() 
177 { 
178 return false; 
179 } 
180 }; 
181 
182 // PR libstdc++/79141, a utility type for preventing 
183 // initialization of an argument of a disabled assignment 
184 // operator from a pair of empty braces. 
185 struct __nonesuch_no_braces : std::__nonesuch { 
186 explicit __nonesuch_no_braces(const __nonesuch&) = delete; 
187 }; 
188#endif // C++11 
189 
190 template<typename _U1, typename _U2> class __pair_base 
191 { 
192#if __cplusplus >= 201103L 
193 template<typename _T1, typename _T2> friend struct pair; 
194 __pair_base() = default; 
195 ~__pair_base() = default; 
196 __pair_base(const __pair_base&) = default; 
197 __pair_base& operator=(const __pair_base&) = delete; 
198#endif // C++11 
199 }; 
200 
201 /** 
202 * @brief Struct holding two objects of arbitrary type. 
203 * 
204 * @tparam _T1 Type of first object. 
205 * @tparam _T2 Type of second object. 
206 */ 
207 template<typename _T1, typename _T2> 
208 struct pair 
209 : private __pair_base<_T1, _T2> 
210 { 
211 typedef _T1 first_type; /// @c first_type is the first bound type 
212 typedef _T2 second_type; /// @c second_type is the second bound type 
213 
214 _T1 first; /// @c first is a copy of the first object 
215 _T2 second; /// @c second is a copy of the second object 
216 
217 // _GLIBCXX_RESOLVE_LIB_DEFECTS 
218 // 265. std::pair::pair() effects overly restrictive 
219 /** The default constructor creates @c first and @c second using their 
220 * respective default constructors. */ 
221#if __cplusplus >= 201103L 
222 template <typename _U1 = _T1, 
223 typename _U2 = _T2, 
224 typename enable_if<__and_< 
225 __is_implicitly_default_constructible<_U1>, 
226 __is_implicitly_default_constructible<_U2>> 
227 ::value, bool>::type = true> 
228#endif 
229 _GLIBCXX_CONSTEXPR pair() 
230 : first(), second() { } 
231 
232#if __cplusplus >= 201103L 
233 template <typename _U1 = _T1, 
234 typename _U2 = _T2, 
235 typename enable_if<__and_< 
236 is_default_constructible<_U1>, 
237 is_default_constructible<_U2>, 
238 __not_< 
239 __and_<__is_implicitly_default_constructible<_U1>, 
240 __is_implicitly_default_constructible<_U2>>>> 
241 ::value, bool>::type = false> 
242 explicit constexpr pair() 
243 : first(), second() { } 
244#endif 
245 
246 /** Two objects may be passed to a @c pair constructor to be copied. */ 
247#if __cplusplus < 201103L 
248 pair(const _T1& __a, const _T2& __b) 
249 : first(__a), second(__b) { } 
250#else 
251 // Shortcut for constraining the templates that don't take pairs. 
252 using _PCCP = _PCC<true, _T1, _T2>; 
253 
254 template<typename _U1 = _T1, typename _U2=_T2, typename 
255 enable_if<_PCCP::template 
256 _ConstructiblePair<_U1, _U2>() 
257 && _PCCP::template 
258 _ImplicitlyConvertiblePair<_U1, _U2>(), 
259 bool>::type=true> 
260 constexpr pair(const _T1& __a, const _T2& __b) 
261 : first(__a), second(__b) { } 
262 
263 template<typename _U1 = _T1, typename _U2=_T2, typename 
264 enable_if<_PCCP::template 
265 _ConstructiblePair<_U1, _U2>() 
266 && !_PCCP::template 
267 _ImplicitlyConvertiblePair<_U1, _U2>(), 
268 bool>::type=false> 
269 explicit constexpr pair(const _T1& __a, const _T2& __b) 
270 : first(__a), second(__b) { } 
271#endif 
272 
273 /** There is also a templated copy ctor for the @c pair class itself. */ 
274#if __cplusplus < 201103L 
275 template<typename _U1, typename _U2> 
276 pair(const pair<_U1, _U2>& __p) 
277 : first(__p.first), second(__p.second) { } 
278#else 
279 // Shortcut for constraining the templates that take pairs. 
280 template <typename _U1, typename _U2> 
281 using _PCCFP = _PCC<!is_same<_T1, _U1>::value 
282 || !is_same<_T2, _U2>::value, 
283 _T1, _T2>; 
284 
285 template<typename _U1, typename _U2, typename 
286 enable_if<_PCCFP<_U1, _U2>::template 
287 _ConstructiblePair<_U1, _U2>() 
288 && _PCCFP<_U1, _U2>::template 
289 _ImplicitlyConvertiblePair<_U1, _U2>(), 
290 bool>::type=true> 
291 constexpr pair(const pair<_U1, _U2>& __p) 
292 : first(__p.first), second(__p.second) { } 
293 
294 template<typename _U1, typename _U2, typename 
295 enable_if<_PCCFP<_U1, _U2>::template 
296 _ConstructiblePair<_U1, _U2>() 
297 && !_PCCFP<_U1, _U2>::template 
298 _ImplicitlyConvertiblePair<_U1, _U2>(), 
299 bool>::type=false> 
300 explicit constexpr pair(const pair<_U1, _U2>& __p) 
301 : first(__p.first), second(__p.second) { } 
302 
303 constexpr pair(const pair&) = default; 
304 constexpr pair(pair&&) = default; 
305 
306 // DR 811. 
307 template<typename _U1, typename 
308 enable_if<_PCCP::template 
309 _MoveCopyPair<true, _U1, _T2>(), 
310 bool>::type=true> 
311 constexpr pair(_U1&& __x, const _T2& __y) 
312 : first(std::forward<_U1>(__x)), second(__y) { } 
313 
314 template<typename _U1, typename 
315 enable_if<_PCCP::template 
316 _MoveCopyPair<false, _U1, _T2>(), 
317 bool>::type=false> 
318 explicit constexpr pair(_U1&& __x, const _T2& __y) 
319 : first(std::forward<_U1>(__x)), second(__y) { } 
320 
321 template<typename _U2, typename 
322 enable_if<_PCCP::template 
323 _CopyMovePair<true, _T1, _U2>(), 
324 bool>::type=true> 
325 constexpr pair(const _T1& __x, _U2&& __y) 
326 : first(__x), second(std::forward<_U2>(__y)) { } 
327 
328 template<typename _U2, typename 
329 enable_if<_PCCP::template 
330 _CopyMovePair<false, _T1, _U2>(), 
331 bool>::type=false> 
332 explicit pair(const _T1& __x, _U2&& __y) 
333 : first(__x), second(std::forward<_U2>(__y)) { } 
334 
335 template<typename _U1, typename _U2, typename 
336 enable_if<_PCCP::template 
337 _MoveConstructiblePair<_U1, _U2>() 
338 && _PCCP::template 
339 _ImplicitlyMoveConvertiblePair<_U1, _U2>(), 
340 bool>::type=true> 
341 constexpr pair(_U1&& __x, _U2&& __y) 
342 : first(std::forward<_U1>(__x)), second(std::forward<_U2>(__y)) { } 
343 
344 template<typename _U1, typename _U2, typename 
345 enable_if<_PCCP::template 
346 _MoveConstructiblePair<_U1, _U2>() 
347 && !_PCCP::template 
348 _ImplicitlyMoveConvertiblePair<_U1, _U2>(), 
349 bool>::type=false> 
350 explicit constexpr pair(_U1&& __x, _U2&& __y) 
351 : first(std::forward<_U1>(__x)), second(std::forward<_U2>(__y)) { } 
352 
353 
354 template<typename _U1, typename _U2, typename 
355 enable_if<_PCCFP<_U1, _U2>::template 
356 _MoveConstructiblePair<_U1, _U2>() 
357 && _PCCFP<_U1, _U2>::template 
358 _ImplicitlyMoveConvertiblePair<_U1, _U2>(), 
359 bool>::type=true> 
360 constexpr pair(pair<_U1, _U2>&& __p) 
361 : first(std::forward<_U1>(__p.first)), 
362 second(std::forward<_U2>(__p.second)) { } 
363 
364 template<typename _U1, typename _U2, typename 
365 enable_if<_PCCFP<_U1, _U2>::template 
366 _MoveConstructiblePair<_U1, _U2>() 
367 && !_PCCFP<_U1, _U2>::template 
368 _ImplicitlyMoveConvertiblePair<_U1, _U2>(), 
369 bool>::type=false> 
370 explicit constexpr pair(pair<_U1, _U2>&& __p) 
371 : first(std::forward<_U1>(__p.first)), 
372 second(std::forward<_U2>(__p.second)) { } 
373 
374 template<typename... _Args1, typename... _Args2> 
375 pair(piecewise_construct_t, tuple<_Args1...>, tuple<_Args2...>); 
376 
377 pair& 
378 operator=(typename conditional< 
379 __and_<is_copy_assignable<_T1>, 
380 is_copy_assignable<_T2>>::value, 
381 const pair&, const __nonesuch_no_braces&>::type __p) 
382 { 
383 first = __p.first; 
384 second = __p.second; 
385 return *this; 
386 } 
387 
388 pair& 
389 operator=(typename conditional< 
390 __and_<is_move_assignable<_T1>, 
391 is_move_assignable<_T2>>::value, 
392 pair&&, __nonesuch_no_braces&&>::type __p) 
393 noexcept(__and_<is_nothrow_move_assignable<_T1>, 
394 is_nothrow_move_assignable<_T2>>::value) 
395 { 
396 first = std::forward<first_type>(__p.first); 
397 second = std::forward<second_type>(__p.second); 
398 return *this; 
399 } 
400 
401 template<typename _U1, typename _U2> 
402 typename enable_if<__and_<is_assignable<_T1&, const _U1&>, 
403 is_assignable<_T2&, const _U2&>>::value, 
404 pair&>::type 
405 operator=(const pair<_U1, _U2>& __p) 
406 { 
407 first = __p.first; 
408 second = __p.second; 
409 return *this; 
410 } 
411 
412 template<typename _U1, typename _U2> 
413 typename enable_if<__and_<is_assignable<_T1&, _U1&&>, 
414 is_assignable<_T2&, _U2&&>>::value, 
415 pair&>::type 
416 operator=(pair<_U1, _U2>&& __p) 
417 { 
418 first = std::forward<_U1>(__p.first); 
419 second = std::forward<_U2>(__p.second); 
420 return *this; 
421 } 
422 
423 void 
424 swap(pair& __p) 
425 noexcept(__and_<__is_nothrow_swappable<_T1>, 
426 __is_nothrow_swappable<_T2>>::value) 
427 { 
428 using std::swap; 
429 swap(first, __p.first); 
430 swap(second, __p.second); 
431 } 
432 
433 private: 
434 template<typename... _Args1, std::size_t... _Indexes1, 
435 typename... _Args2, std::size_t... _Indexes2> 
436 pair(tuple<_Args1...>&, tuple<_Args2...>&, 
437 _Index_tuple<_Indexes1...>, _Index_tuple<_Indexes2...>); 
438#endif 
439 }; 
440 
441#if __cpp_deduction_guides >= 201606 
442 template<typename _T1, typename _T2> pair(_T1, _T2) -> pair<_T1, _T2>; 
443#endif 
444 
445 /// Two pairs of the same type are equal iff their members are equal. 
446 template<typename _T1, typename _T2> 
447 inline _GLIBCXX_CONSTEXPR bool 
448 operator==(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y) 
449 { return __x.first == __y.first && __x.second == __y.second; } 
450 
451 /// <http://gcc.gnu.org/onlinedocs/libstdc++/manual/utilities.html> 
452 template<typename _T1, typename _T2> 
453 inline _GLIBCXX_CONSTEXPR bool 
454 operator<(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y) 
455 { return __x.first < __y.first 
456 || (!(__y.first < __x.first) && __x.second < __y.second); } 
457 
458 /// Uses @c operator== to find the result. 
459 template<typename _T1, typename _T2> 
460 inline _GLIBCXX_CONSTEXPR bool 
461 operator!=(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y) 
462 { return !(__x == __y); } 
463 
464 /// Uses @c operator< to find the result. 
465 template<typename _T1, typename _T2> 
466 inline _GLIBCXX_CONSTEXPR bool 
467 operator>(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y) 
468 { return __y < __x; } 
469 
470 /// Uses @c operator< to find the result. 
471 template<typename _T1, typename _T2> 
472 inline _GLIBCXX_CONSTEXPR bool 
473 operator<=(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y) 
474 { return !(__y < __x); } 
475 
476 /// Uses @c operator< to find the result. 
477 template<typename _T1, typename _T2> 
478 inline _GLIBCXX_CONSTEXPR bool 
479 operator>=(const pair<_T1, _T2>& __x, const pair<_T1, _T2>& __y) 
480 { return !(__x < __y); } 
481 
482#if __cplusplus >= 201103L 
483 /// See std::pair::swap(). 
484 // Note: no std::swap overloads in C++03 mode, this has performance 
485 // implications, see, eg, libstdc++/38466. 
486 template<typename _T1, typename _T2> 
487 inline 
488#if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11 
489 // Constrained free swap overload, see p0185r1 
490 typename enable_if<__and_<__is_swappable<_T1>, 
491 __is_swappable<_T2>>::value>::type 
492#else 
493 void 
494#endif 
495 swap(pair<_T1, _T2>& __x, pair<_T1, _T2>& __y) 
496 noexcept(noexcept(__x.swap(__y))) 
497 { __x.swap(__y); } 
498 
499#if __cplusplus > 201402L || !defined(__STRICT_ANSI__) // c++1z or gnu++11 
500 template<typename _T1, typename _T2> 
501 typename enable_if<!__and_<__is_swappable<_T1>, 
502 __is_swappable<_T2>>::value>::type 
503 swap(pair<_T1, _T2>&, pair<_T1, _T2>&) = delete; 
504#endif 
505#endif // __cplusplus >= 201103L 
506 
507 /** 
508 * @brief A convenience wrapper for creating a pair from two objects. 
509 * @param __x The first object. 
510 * @param __y The second object. 
511 * @return A newly-constructed pair<> object of the appropriate type. 
512 * 
513 * The standard requires that the objects be passed by reference-to-const, 
514 * but LWG issue #181 says they should be passed by const value. We follow 
515 * the LWG by default. 
516 */ 
517 // _GLIBCXX_RESOLVE_LIB_DEFECTS 
518 // 181. make_pair() unintended behavior 
519#if __cplusplus >= 201103L 
520 // NB: DR 706. 
521 template<typename _T1, typename _T2> 
522 constexpr pair<typename __decay_and_strip<_T1>::__type, 
523 typename __decay_and_strip<_T2>::__type> 
524 make_pair(_T1&& __x, _T2&& __y) 
525 { 
526 typedef typename __decay_and_strip<_T1>::__type __ds_type1; 
527 typedef typename __decay_and_strip<_T2>::__type __ds_type2; 
528 typedef pair<__ds_type1, __ds_type2> __pair_type; 
529 return __pair_type(std::forward<_T1>(__x), std::forward<_T2>(__y)); 
530 } 
531#else 
532 template<typename _T1, typename _T2> 
533 inline pair<_T1, _T2> 
534 make_pair(_T1 __x, _T2 __y) 
535 { return pair<_T1, _T2>(__x, __y); } 
536#endif 
537 
538 /// @} 
539 
540_GLIBCXX_END_NAMESPACE_VERSION 
541} // namespace std 
542 
543#endif /* _STL_PAIR_H */ 
544