-
Notifications
You must be signed in to change notification settings - Fork 319
/
bslstl_vector.h
4761 lines (4149 loc) · 190 KB
/
bslstl_vector.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
// bslstl_vector.h -*-C++-*-
#ifndef INCLUDED_BSLSTL_VECTOR
#define INCLUDED_BSLSTL_VECTOR
#include <bsls_ident.h>
BSLS_IDENT("$Id: $")
//@PURPOSE: Provide an STL-compliant vector class.
//
//@CLASSES:
// bsl::vector: STL-compatible vector template
//
//@CANONICAL_HEADER: bsl_vector.h
//
//@SEE_ALSO: bslstl_deque
//
//@DESCRIPTION: This component defines a single class template, 'bsl::vector',
// implementing the standard sequential container, 'std::vector', holding a
// dynamic array of values of a template parameter type.
//
// An instantiation of 'vector' is an allocator-aware, value-semantic type
// whose salient attributes are its size (number of values) and the sequence of
// values the vector contains. If 'vector' is instantiated with a value type
// that is not value-semantic, then the vector will not retain all of its
// value-semantic qualities. In particular, if a value type cannot be tested
// for equality, then a 'vector' containing objects of that type cannot be
// tested for equality. It is even possible to instantiate 'vector' with a
// value type that does not have a copy-constructor, in which case the 'vector'
// will not be copyable.
//
// A vector meets the requirements of a sequential container with random access
// iterators in the C++ standard [vector]. The 'vector' implemented here
// adheres to the C++11 standard when compiled with a C++11 compiler, and makes
// the best approximation when compiled with a C++03 compiler. In particular,
// for C++03 we emulate move semantics, but limit forwarding (in 'emplace') to
// 'const' lvalues, and make no effort to emulate 'noexcept' or initializer
// lists.
//
///Requirements on 'VALUE_TYPE'
///----------------------------
// A 'vector' is a fully Value-Semantic Type (see {'bsldoc_glossary'}) only if
// the supplied 'VALUE_TYPE' template parameter is fully value-semantic. It is
// possible to instantiate a 'vector' with a 'VALUE_TYPE' parameter that does
// not have a full set of value-semantic operations, but then some methods of
// the container may not be instantiable. The following terminology, adopted
// from the C++11 standard, is used in the function documentation of 'vector'
// to describe a function's requirements for the 'VALUE_TYPE' template
// parameter. These terms are also defined in section [17.6.3.1] of the C++11
// standard. Note that, in the context of a 'vector' instantiation, the
// requirements apply specifically to the vector's entry type, 'value_type',
// which is an alias for 'VALUE_TYPE'.
//
///Glossary
///--------
//..
// Legend
// ------
// 'X' - denotes an allocator-aware container type (e.g., 'vector')
// 'T' - 'value_type' associated with 'X'
// 'A' - type of the allocator used by 'X'
// 'm' - lvalue of type 'A' (allocator)
// 'p' - address ('T *') of uninitialized storage for a 'T' within an 'X'
// 'rv' - rvalue of type (non-'const') 'T'
// 'v' - rvalue or lvalue of type (possibly 'const') 'T'
// 'args' - 0 or more arguments
//..
// The following terms are used to more precisely specify the requirements on
// template parameter types in function-level documentation.
//
//: *default-insertable*: 'T' has a default constructor. More precisely, 'T'
//: is 'default-insertable' into 'X' means that the following expression is
//: well-formed:
//: 'allocator_traits<A>::construct(m, p)'
//:
//: *move-insertable*: 'T' provides a constructor that takes an rvalue of type
//: (non-'const') 'T'. More precisely, 'T' is 'move-insertable' into 'X'
//: means that the following expression is well-formed:
//: 'allocator_traits<A>::construct(m, p, rv)'
//:
//: *copy-insertable*: 'T' provides a constructor that takes an lvalue or
//: rvalue of type (possibly 'const') 'T'. More precisely, 'T' is
//: 'copy-insertable' into 'X' means that the following expression is
//: well-formed:
//: 'allocator_traits<A>::construct(m, p, v)'
//:
//: *move-assignable*: 'T' provides an assignment operator that takes an rvalue
//: of type (non-'const') 'T'.
//:
//: *copy-assignable*: 'T' provides an assignment operator that takes an lvalue
//: or rvalue of type (possibly 'const') 'T'.
//:
//: *emplace-constructible*: 'T' is 'emplace-constructible' into 'X' from
//: 'args' means that the following expression is well-formed:
//: 'allocator_traits<A>::construct(m, p, args)'
//:
//: *erasable*: 'T' provides a destructor. More precisely, 'T' is 'erasable'
//: from 'X' means that the following expression is well-formed:
//: 'allocator_traits<A>::destroy(m, p)'
//:
//: *equality-comparable*: The type provides an equality-comparison operator
//: that defines an equivalence relationship and is both reflexive and
//: transitive.
//
///Memory Allocation
///-----------------
// The type supplied as a vector's 'ALLOCATOR' template parameter determines
// how that vector will allocate memory. The 'vector' template supports
// allocators meeting the requirements of the C++03 standard; in addition, it
// supports scoped-allocators derived from the 'bslma::Allocator' memory
// allocation protocol. Clients intending to use 'bslma'-style allocators
// should use the template's default 'ALLOCATOR' type: The default type for the
// 'ALLOCATOR' template parameter, 'bsl::allocator', provides a C++11
// standard-compatible adapter for a 'bslma::Allocator' object.
//
///'bslma'-Style Allocators
/// - - - - - - - - - - - -
// If the (template parameter) type 'ALLOCATOR' of a 'vector' instantiation' is
// 'bsl::allocator', then objects of that vector type will conform to the
// standard behavior of a 'bslma'-allocator-enabled type. Such a vector
// accepts an optional 'bslma::Allocator' argument at construction. If the
// address of a 'bslma::Allocator' object is explicitly supplied at
// construction, it is used to supply memory for the vector throughout its
// lifetime; otherwise, the vector will use the default allocator installed at
// the time of the vector's construction (see 'bslma_default'). In addition to
// directly allocating memory from the indicated 'bslma::Allocator', a vector
// supplies that allocator's address to the constructors of contained objects
// of the (template parameter) type 'VALUE_TYPE', if it defines the
// 'bslma::UsesBslmaAllocator' trait.
//
///Operations
///----------
// This section describes the run-time complexity of operations on instances
// of 'vector':
//..
// Legend
// ------
// 'V' - (template parameter) 'VALUE_TYPE' of the vector
// 'a', 'b' - two distinct objects of type 'vector<V>'
// 'rv' - modifiable rvalue of type 'vector<V>'
// 'n', 'm' - number of elements in 'a' and 'b', respectively
// 'k' - non-negative integer
// 'al' - an STL-style memory allocator
// 'i1', 'i2' - two iterators defining a sequence of 'V' objects
// 'il' - object of type 'std::initializer_list<V>'
// 'lil' - length of 'il'
// 'vt' - object of type 'VALUE_TYPE'
// 'rvt' - modifiable rvalue of type 'VALUE_TYPE'
// 'p1', 'p2' - two 'const' iterators belonging to 'a'
// distance(i1,i2) - the number of elements in the range [i1, i2)
//
// |-----------------------------------------+-------------------------------|
// | Operation | Complexity |
// |=========================================+===============================|
// | vector<V> a (default construction) | O[1] |
// | vector<V> a(al) | |
// |-----------------------------------------+-------------------------------|
// | vector<V> a(b) (copy construction) | O[n] |
// | vector<V> a(b, al) | |
// |-----------------------------------------+-------------------------------|
// | vector<V> a(rv) (move construction) | O[1] if 'a' and 'rv' use the |
// | vector<V> a(rv, al) | same allocator; O[n] otherwise|
// |-----------------------------------------+-------------------------------|
// | vector<V> a(k) | O[k] |
// | vector<V> a(k, al) | |
// | vector<V> a(k, vt) | |
// | vector<V> a(k, vt, al) | |
// |-----------------------------------------+-------------------------------|
// | vector<V> a(i1, i2) | O[distance(i1, i2)] |
// | vector<V> a(i1, i2, al) | |
// |-----------------------------------------+-------------------------------|
// | vector<V> a(il) | O[lil] |
// | vector<V> a(il, al) | |
// |-----------------------------------------+-------------------------------|
// | a.~vector<V>() (destruction) | O[n] |
// |-----------------------------------------+-------------------------------|
// | a.assign(k, vt) | O[k] |
// | a.assign(k, rvt) | |
// |-----------------------------------------+-------------------------------|
// | a.assign(i1, i2) | O[distance(i1, i2)] |
// |-----------------------------------------+-------------------------------|
// | a.assign(il) | O[lil] |
// |-----------------------------------------+-------------------------------|
// | get_allocator() | O[1] |
// |-----------------------------------------+-------------------------------|
// | a.begin(), a.end(), | O[1] |
// | a.cbegin(), a.cend(), | |
// | a.rbegin(), a.rend(), | |
// | a.crbegin(), a.crend() | |
// |-----------------------------------------+-------------------------------|
// | a.size() | O[1] |
// |-----------------------------------------+-------------------------------|
// | a.max_size() | O[1] |
// |-----------------------------------------+-------------------------------|
// | a.resize(k) | O[k] |
// | a.resize(k, vt) | |
// |-----------------------------------------+-------------------------------|
// | a.empty() | O[1] |
// |-----------------------------------------+-------------------------------|
// | a.reserve(k) | O[k] |
// |-----------------------------------------+-------------------------------|
// | a.shrink_to_fit() | O[n] |
// |-----------------------------------------+-------------------------------|
// | a[k] | O[1] |
// |-----------------------------------------+-------------------------------|
// | a.at(k) | O[1] |
// |-----------------------------------------+-------------------------------|
// | a.front() | O[1] |
// |-----------------------------------------+-------------------------------|
// | a.back() | O[1] |
// |-----------------------------------------+-------------------------------|
// | a.push_back(vt) | O[1] |
// | a.push_back(rvt) | |
// |-----------------------------------------+-------------------------------|
// | a.pop_back() | O[1] |
// |-----------------------------------------+-------------------------------|
// | a.emplace_back(args) | O[1] |
// |-----------------------------------------+-------------------------------|
// | a.emplace(p1, args) | O[1 + distance(p1, a.end())] |
// |-----------------------------------------+-------------------------------|
// | a.insert(p1, vt) | O[1 + distance(p1, a.end())] |
// | a.insert(p1, rvt) | |
// |-----------------------------------------+-------------------------------|
// | a.insert(p1, k, vt) | O[k + distance(p1, a.end())] |
// | a.insert(p1, k, rvt) | |
// |-----------------------------------------+-------------------------------|
// | a.insert(p1, i1, i2) | O[distance(i1, i2) |
// | | + distance(p1, a.end())] |
// |-----------------------------------------+-------------------------------|
// | a.insert(p1, il) | O[lil |
// | | + distance(p1, a.end())] |
// |-----------------------------------------+-------------------------------|
// | a.erase(p1) | O[1 + distance(p1, a.end())] |
// |-----------------------------------------+-------------------------------|
// | a.erase(p1, p2) | O[distance(p1, p2) |
// | | + distance(p1, a.end())] |
// |-----------------------------------------+-------------------------------|
// | a.swap(b), swap(a, b) | O[1] if 'a' and 'b' use the |
// | | same allocator; O[n + m] |
// | | otherwise |
// |-----------------------------------------+-------------------------------|
// | a.clear() | O[n] |
// |-----------------------------------------+-------------------------------|
// | a = b; (copy assignment) | O[n] |
// |-----------------------------------------+-------------------------------|
// | a = rv; (move assignment) | O[1] if 'a' and 'rv' use the |
// | | same allocator; O[n] otherwise|
// |-----------------------------------------+-------------------------------|
// | a = il; | O[lil] |
// |-----------------------------------------+-------------------------------|
// | a == b, a != b | O[n] |
// |-----------------------------------------+-------------------------------|
// | a < b, a <= b, a > b, a >= b | O[n] |
// |-----------------------------------------+-------------------------------|
//..
//
///Comparing a vector of floating point values
///-------------------------------------------
// The comparison operator performs a bit-wise comparison for floating point
// types ('float' and 'double'), which produces results for NaN, +0, and -0
// values that do not meet the guarantees provided by the standard.
// The 'bslmf::IsBitwiseEqualityComparable' trait for 'double' and 'float'
// types returns 'true' which is incorrect because a comparison with a NaN
// value is always 'false', and -0 and +0 are equal.
//..
// bsl::vector<double> v;
// v.push_back(bsl::numeric_limits<double>::quiet_NaN());
// ASSERT(v == v); // This assertion will *NOT* fail!
//..
// Addressing this issue, i.e., updating 'bslmf::IsBitwiseEqualityComparable'
// to return 'false' for floating point types, could potentially destabilize
// production software so the change (for the moment) has not been made.
//
///Usage
///-----
// In this section we show intended use of this component.
//
///Example 1: Creating a Matrix Type
///- - - - - - - - - - - - - - - - -
// Suppose we want to define a value-semantic type representing a dynamically
// resizable two-dimensional matrix.
//
// First, we define the public interface for the 'MyMatrix' class template:
//..
// template <class TYPE>
// class MyMatrix {
// // This value-semantic type characterizes a two-dimensional matrix of
// // objects of the (template parameter) 'TYPE'. The numbers of columns
// // and rows of the matrix can be specified at construction and, at any
// // time, via the 'reset', 'insertRow', and 'insertColumn' methods. The
// // value of each element in the matrix can be set and accessed using
// // the 'theValue', and 'theModifiableValue' methods respectively.
//
// public:
// // PUBLIC TYPES
//..
// Here, we create a type alias, 'RowType', for an instantiation of
// 'bsl::vector' to represent a row of 'TYPE' objects in the matrix. We create
// another type alias, 'MatrixType', for an instantiation of 'bsl::vector' to
// represent the entire matrix of 'TYPE' objects as a list of rows:
//..
// typedef bsl::vector<TYPE> RowType;
// // This is an alias representing a row of values of the (template
// // parameter) 'TYPE'.
//
// typedef bsl::vector<RowType> MatrixType;
// // This is an alias representing a two-dimensional matrix of values
// // of the (template parameter) 'TYPE'.
//
// private:
// // DATA
// MatrixType d_matrix; // matrix of values
// int d_numColumns; // number of columns
//
// // FRIENDS
// template <class T>
// friend bool operator==(const MyMatrix<T>&, const MyMatrix<T>&);
//
// public:
// // PUBLIC TYPES
// typedef typename MatrixType::const_iterator ConstRowIterator;
//
// // CREATORS
// MyMatrix(int numRows,
// int numColumns,
// bslma::Allocator *basicAllocator = 0);
// // Create a 'MyMatrix' object having the specified 'numRows' and
// // the specified 'numColumns'. All elements of the (template
// // parameter) 'TYPE' in the matrix will have the
// // default-constructed value. Optionally specify a
// // 'basicAllocator' used to supply memory. If 'basicAllocator' is
// // 0, the currently installed default allocator is used. The
// // behavior is undefined unless '0 <= numRows' and
// // '0 <= numColumns'
//
// MyMatrix(const MyMatrix& original,
// bslma::Allocator *basicAllocator = 0);
// // Create a 'MyMatrix' object having the same value as the
// // specified 'original' object. Optionally specify a
// // 'basicAllocator' used to supply memory. If 'basicAllocator' is
// // 0, the currently installed default allocator is used.
//
// //! ~MyMatrix = default;
// // Destroy this object.
//
// // MANIPULATORS
// MyMatrix& operator=(const MyMatrix& rhs);
// // Assign to this object the value of the specified 'rhs' object,
// // and return a reference providing modifiable access to this
// // object.
//
// void clear();
// // Remove all rows and columns from this object.
//
// void insertColumn(int columnIndex);
// // Insert, into this matrix, an column at the specified
// // 'columnIndex'. All elements of the (template parameter) 'TYPE'
// // in the column will have the default-constructed value. The
// // behavior is undefined unless '0 <= columnIndex <= numColumns()'.
//
// void insertRow(int rowIndex);
// // Insert, into this matrix, a row at the specified 'rowIndex'.
// // All elements of the (template parameter) 'TYPE' in the row will
// // have the default-constructed value. The behavior is undefined
// // unless '0 <= rowIndex <= numRows()'.
//
// TYPE& theModifiableValue(int rowIndex, int columnIndex);
// // Return a reference providing modifiable access to the element at
// // the specified 'rowIndex' and the specified 'columnIndex' in this
// // matrix. The behavior is undefined unless
// // '0 <= rowIndex < numRows()' and
// // '0 <= columnIndex < numColumns()'.
//
// // ACCESSORS
// int numRows() const;
// // Return the number of rows in this matrix.
//
// int numColumns() const;
// // Return the number of columns in this matrix.
//
// ConstRowIterator beginRow() const;
// // Return an iterator providing non-modifiable access to the
// // 'RowType' objects representing the first row in this matrix.
//
// ConstRowIterator endRow() const;
// // Return an iterator providing non-modifiable access to the
// // 'RowType' objects representing the past-the-end row in this
// // matrix.
//
// const TYPE& theValue(int rowIndex, int columnIndex) const;
// // Return a reference providing non-modifiable access to the
// // element at the specified 'rowIndex' and the specified
// // 'columnIndex' in this matrix. The behavior is undefined unless
// // '0 <= rowIndex < numRows()' and
// // '0 <= columnIndex < numColumns()'.
// };
//..
// Then we declare the free operator for 'MyMatrix':
//..
// // FREE OPERATORS
// template <class TYPE>
// MyMatrix<TYPE> operator==(const MyMatrix<TYPE>& lhs,
// const MyMatrix<TYPE>& rhs);
// // Return 'true' if the specified 'lhs' and 'rhs' objects have the same
// // value, and 'false' otherwise. Two 'MyMatrix' objects have the same
// // value if they have the same number of rows and columns and every
// // element in both matrices compare equal.
//
// template <class TYPE>
// MyMatrix<TYPE> operator!=(const MyMatrix<TYPE>& lhs,
// const MyMatrix<TYPE>& rhs);
// // Return 'true' if the specified 'lhs' and 'rhs' objects do not have
// // the same value, and 'false' otherwise. Two 'MyMatrix' objects do
// // not have the same value if they do not have the same number of rows
// // and columns or every element in both matrices do not compare equal.
//
// template <class TYPE>
// MyMatrix<TYPE> operator*(const MyMatrix<TYPE>& lhs,
// const MyMatrix<TYPE>& rhs);
// // Return a 'MyMatrix' objects that is the product of the specified
// // 'lhs' and 'rhs'. The behavior is undefined unless
// // 'lhs.numColumns() == rhs.numRows()'.
//..
// Now, we define the methods of 'MyMatrix':
//..
// // CREATORS
// template <class TYPE>
// MyMatrix<TYPE>::MyMatrix(int numRows,
// int numColumns,
// bslma::Allocator *basicAllocator)
// : d_matrix(numRows, basicAllocator)
// , d_numColumns(numColumns)
// {
// BSLS_ASSERT(0 <= numRows);
// BSLS_ASSERT(0 <= numColumns);
//
// for (typename MatrixType::iterator itr = d_matrix.begin();
// itr != d_matrix.end();
// ++itr) {
// itr->resize(d_numColumns);
// }
// }
// template <class TYPE>
// MyMatrix<TYPE>::MyMatrix(const MyMatrix& original,
// bslma::Allocator *basicAllocator)
// : d_matrix(original.d_matrix, basicAllocator)
// , d_numColumns(original.d_numColumns)
// {
// }
//..
// Notice that we pass the contained 'bsl::vector' ('d_matrix') the allocator
// specified at construction to supply memory. If the (template parameter)
// 'TYPE' of the elements has the 'bslalg_TypeTraitUsesBslmaAllocator' trait,
// this allocator will be passed by the vector to the elements as well.
//..
// // MANIPULATORS
// template <class TYPE>
// MyMatrix<TYPE>& MyMatrix<TYPE>::operator=(const MyMatrix& rhs)
// {
// d_matrix = rhs.d_matrix;
// d_numColumns = rhs.d_numColumns;
// }
//
// template <class TYPE>
// void MyMatrix<TYPE>::clear()
// {
// d_matrix.clear();
// d_numColumns = 0;
// }
//
// template <class TYPE>
// void MyMatrix<TYPE>::insertColumn(int colIndex) {
// for (typename MatrixType::iterator itr = d_matrix.begin();
// itr != d_matrix.end();
// ++itr) {
// itr->insert(itr->begin() + colIndex, TYPE());
// }
// ++d_numColumns;
// }
//
// template <class TYPE>
// void MyMatrix<TYPE>::insertRow(int rowIndex)
// {
// typename MatrixType::iterator itr =
// d_matrix.insert(d_matrix.begin() + rowIndex, RowType());
// itr->resize(d_numColumns);
// }
//
// template <class TYPE>
// TYPE& MyMatrix<TYPE>::theModifiableValue(int rowIndex, int columnIndex)
// {
// BSLS_ASSERT(0 <= rowIndex);
// BSLS_ASSERT(rowIndex < d_matrix.size());
// BSLS_ASSERT(0 <= columnIndex);
// BSLS_ASSERT(columnIndex < d_numColumns);
//
// return d_matrix[rowIndex][columnIndex];
// }
//
// // ACCESSORS
// template <class TYPE>
// int MyMatrix<TYPE>::numRows() const
// {
// return d_matrix.size();
// }
//
// template <class TYPE>
// int MyMatrix<TYPE>::numColumns() const
// {
// return d_numColumns;
// }
//
// template <class TYPE>
// typename MyMatrix<TYPE>::ConstRowIterator MyMatrix<TYPE>::beginRow() const
// {
// return d_matrix.begin();
// }
//
// template <class TYPE>
// typename MyMatrix<TYPE>::ConstRowIterator MyMatrix<TYPE>::endRow() const
// {
// return d_matrix.end();
// }
//
// template <class TYPE>
// const TYPE& MyMatrix<TYPE>::theValue(int rowIndex, int columnIndex) const
// {
// BSLS_ASSERT(0 <= rowIndex);
// BSLS_ASSERT(rowIndex < d_matrix.size());
// BSLS_ASSERT(0 <= columnIndex);
// BSLS_ASSERT(columnIndex < d_numColumns);
//
// return d_matrix[rowIndex][columnIndex];
// }
//..
// Finally, we defines the free operators for 'MyMatrix':
//..
// // FREE OPERATORS
// template <class TYPE>
// MyMatrix<TYPE> operator==(const MyMatrix<TYPE>& lhs,
// const MyMatrix<TYPE>& rhs)
// {
// return lhs.d_numColumns == rhs.d_numColumns &&
// lhs.d_matrix == rhs.d_matrix;
// }
//
// template <class TYPE>
// MyMatrix<TYPE> operator!=(const MyMatrix<TYPE>& lhs,
// const MyMatrix<TYPE>& rhs)
// {
// return !(lhs == rhs);
// }
//..
#include <bslscm_version.h>
#include <bslstl_algorithm.h>
#include <bslstl_compare.h>
#include <bslstl_hash.h>
#include <bslstl_iterator.h>
#include <bslstl_iteratorutil.h>
#include <bslstl_stdexceptutil.h>
#include <bslalg_arraydestructionprimitives.h>
#include <bslalg_arrayprimitives.h>
#include <bslalg_containerbase.h>
#include <bslalg_rangecompare.h>
#include <bslalg_synththreewayutil.h>
#include <bslalg_swaputil.h>
#include <bslalg_typetraithasstliterators.h>
#include <bslh_hash.h>
#include <bslma_allocator.h>
#include <bslma_allocatortraits.h>
#include <bslma_allocatorutil.h>
#include <bslma_autodestructor.h>
#include <bslma_isstdallocator.h>
#include <bslma_bslallocator.h>
#include <bslma_usesbslmaallocator.h>
#include <bslmf_enableif.h>
#include <bslmf_isbitwisemoveable.h>
#include <bslmf_isconvertible.h>
#include <bslmf_isfundamental.h>
#include <bslmf_isintegral.h>
#include <bslmf_issame.h>
#include <bslmf_matchanytype.h>
#include <bslmf_matcharithmetictype.h>
#include <bslmf_movableref.h>
#include <bslmf_nil.h>
#include <bslmf_typeidentity.h>
#include <bslmf_util.h> // 'forward(V)'
#include <bsls_assert.h>
#include <bsls_compilerfeatures.h>
#include <bsls_keyword.h>
#include <bsls_performancehint.h>
#include <bsls_platform.h>
#include <bsls_types.h>
#include <bsls_util.h> // 'forward<T>(V)'
#include <cstddef>
#if defined(BSLS_COMPILERFEATURES_SUPPORT_GENERALIZED_INITIALIZERS)
#include <initializer_list>
#endif
#ifndef BDE_DONT_ALLOW_TRANSITIVE_INCLUDES
#include <stdexcept>
#endif
#if BSLS_COMPILERFEATURES_SIMULATE_CPP11_FEATURES
// Include version that can be compiled with C++03
// Generated on Thu Oct 21 10:11:37 2021
// Command line: sim_cpp11_features.pl bslstl_vector.h
# define COMPILING_BSLSTL_VECTOR_H
# include <bslstl_vector_cpp03.h>
# undef COMPILING_BSLSTL_VECTOR_H
#else
namespace bsl {
// Forward declarations
template <class VALUE_TYPE, class ITERATOR>
class vector_UintPtrConversionIterator;
// ==================
// struct Vector_Util
// ==================
struct Vector_Util {
// This 'struct' provides a namespace for implementing the 'swap' member
// function of 'vector<VALUE_TYPE, ALLOCATOR>'. 'swap' can be implemented
// irrespective of the 'VALUE_TYPE' or 'ALLOCATOR' template parameters,
// which is why we implement it in this non-parameterized, non-inlined
// utility.
// CLASS METHODS
static std::size_t computeNewCapacity(std::size_t newLength,
std::size_t capacity,
std::size_t maxSize);
// Return a capacity that is at least the specified 'newLength' and at
// least the minimum of twice the specified 'capacity' and the
// specified 'maxSize'. The behavior is undefined unless
// 'capacity < newLength' and 'newLength <= maxSize'. Note that the
// returned value is always at most 'maxSize'.
static void swap(void *a, void *b);
// Exchange the value of the specified 'a' vector with that of the
// specified 'b' vector.
};
// ===================================
// class Vector_DeduceIteratorCategory
// ===================================
template <class BSLSTL_ITERATOR,
bool BSLSTL_NOTSPECIALIZED = is_fundamental<BSLSTL_ITERATOR>::value>
struct Vector_DeduceIteratorCategory {
// This 'struct' provides a primitive means to distinguish between iterator
// types and fundamental types, in order to dispatch to the correct
// implementation of a function template (or constructor template) passed
// two arguments of identical type. By default, it is assumed that any
// type that is not a fundamental type, as determined by the type trait
// 'bsl::is_fundamental', must be an iterator type. 'std::iterator_traits'
// is updated in C++17 to provide a SFINAE-friendly instantiation of the
// primary-template for types that do not provide all of the nested typedef
// names, but we cannot portably rely on such a scheme yet.
// PUBLIC TYPES
typedef typename bsl::iterator_traits<BSLSTL_ITERATOR>::iterator_category
type;
};
template <class BSLSTL_ITERATOR>
struct Vector_DeduceIteratorCategory<BSLSTL_ITERATOR, true> {
// This partial specialization of the 'struct' template for fundamental
// types provides a nested 'type' that is not an iterator category, so can
// be used to control the internal dispatch of function template overloads
// taking two arguments of the same type.
// PUBLIC TYPES
typedef BloombergLP::bslmf::Nil type;
};
// ======================================
// class vector_UintPtrConversionIterator
// ======================================
template <class TARGET, class ITERATOR, bool = is_integral<ITERATOR>::value>
struct vector_ForwardIteratorForPtrs {
// This metafunction provides an appropriate iterator adaptor for the
// specified (template parameter) type 'ITERATOR' in order to implement
// members of the 'vector' partial template specialization for vectors of
// pointers to the (template parameter) type 'TARGET'. The metafunction
// will return the original 'ITERATOR' type unless it truly is an iterator,
// using 'is_integral' as a proxy for testing that a type is NOT an
// iterator. This is needed to disambiguate only the cases of users
// passing '0' as a null-pointer value to functions requesting a number of
// identical copies of an element.
// PUBLIC TYPES
typedef ITERATOR type;
};
template <class TARGET, class ITERATOR>
struct vector_ForwardIteratorForPtrs<TARGET, ITERATOR, false> {
// This metafunction specialization provides an appropriate iterator
// adaptor for the specified (template parameter) type 'ITERATOR' in order
// to implement members of the 'vector' partial template specialization for
// vectors of pointers to the (template parameter) type 'TARGET'.
// PUBLIC TYPES
typedef vector_UintPtrConversionIterator<TARGET *, ITERATOR> type;
};
#if defined(BSLS_ASSERT_SAFE_IS_USED)
template <class BSLSTL_ITERATOR>
struct Vector_IsRandomAccessIterator :
bsl::is_same<typename Vector_DeduceIteratorCategory<BSLSTL_ITERATOR>::type,
bsl::random_access_iterator_tag>::type
{
};
// =======================
// class Vector_RangeCheck
// =======================
struct Vector_RangeCheck {
// This utility class provides a test-support facility to diagnose when a
// pair of iterators do *not* form a valid range. This support is offered
// only for random access iterators, and identifies only the case of two
// valid iterators into the same range forming a "reverse" range. Note
// that the two functions declared using 'enable_if' must be defined inline
// in the class definition due to a bug in the Microsoft C++ compiler (see
// 'bslmf_enableif').
// CLASS METHODS
template <class BSLSTL_ITERATOR>
static
typename bsl::enable_if<
!Vector_IsRandomAccessIterator<BSLSTL_ITERATOR>::value, bool>::type
isInvalidRange(BSLSTL_ITERATOR, BSLSTL_ITERATOR);
// Return 'false'. Note that we know of no way to identify an input
// iterator range that is guaranteed to be invalid.
template <class BSLSTL_ITERATOR>
static
typename bsl::enable_if<
Vector_IsRandomAccessIterator<BSLSTL_ITERATOR>::value, bool>::type
isInvalidRange(BSLSTL_ITERATOR first, BSLSTL_ITERATOR last);
// Return 'true' if 'last < first', and 'false' otherwise. The
// behavior is undefined unless both 'first' and 'last' are valid
// iterators that refer to the same range.
};
#endif
// ================
// class vectorBase
// ================
template <class VALUE_TYPE>
class vectorBase {
// This class describes the basic layout for a vector class, to be included
// into the 'vector' layout *before* the allocator (provided by
// 'bslalg::ContainerBase') to take better advantage of cache prefetching.
// It is parameterized by 'VALUE_TYPE' only, and implements the portion of
// 'vector' that does not need to know about its (template parameter) type
// 'ALLOCATOR' (in order to generate shorter debug strings). This class
// intentionally has *no* creators (other than the compiler-generated
// ones).
// PRIVATE TYPES
typedef BloombergLP::bslmf::MovableRefUtil MoveUtil;
// This 'typedef' is a convenient alias for the utility associated with
// movable references.
protected:
// PROTECTED DATA
VALUE_TYPE *d_dataBegin_p; // beginning of data storage (owned)
VALUE_TYPE *d_dataEnd_p; // one past the end of data storage
std::size_t d_capacity; // capacity of data storage in # of elements
public:
// PUBLIC TYPES
typedef VALUE_TYPE value_type;
typedef VALUE_TYPE& reference;
typedef VALUE_TYPE const& const_reference;
typedef VALUE_TYPE *iterator;
typedef VALUE_TYPE const *const_iterator;
typedef std::size_t size_type;
typedef std::ptrdiff_t difference_type;
typedef bsl::reverse_iterator<iterator> reverse_iterator;
typedef bsl::reverse_iterator<const_iterator> const_reverse_iterator;
public:
// CREATORS
vectorBase();
// Create an empty base object with no capacity.
// MANIPULATORS
void adopt(BloombergLP::bslmf::MovableRef<vectorBase> base);
// Adopt all outstanding memory allocations associated with the
// specified 'base' object. The behavior is undefined unless this
// object is in a default-constructed state.
// *** iterators ***
iterator begin() BSLS_KEYWORD_NOEXCEPT;
// Return an iterator providing modifiable access to the first element
// in this vector, or the past-the-end iterator if this vector is
// empty.
iterator end() BSLS_KEYWORD_NOEXCEPT;
// Return the past-the-end iterator providing modifiable access to this
// vector.
reverse_iterator rbegin() BSLS_KEYWORD_NOEXCEPT;
// Return a reverse iterator providing modifiable access to the last
// element in this vector, and the past-the-end reverse iterator if
// this vector is empty.
reverse_iterator rend() BSLS_KEYWORD_NOEXCEPT;
// Return the past-the-end reverse iterator providing modifiable access
// to this vector.
// *** element access ***
reference operator[](size_type position);
// Return a reference providing modifiable access to the element at the
// specified 'position' in this vector. The behavior is undefined
// unless 'position < size()'.
reference at(size_type position);
// Return a reference providing modifiable access to the element at the
// specified 'position' in this vector. Throw a 'std::out_of_range'
// exception if 'position >= size()'.
reference front();
// Return a reference providing modifiable access to the first element
// in this vector. The behavior is undefined unless this vector is not
// empty.
reference back();
// Return a reference providing modifiable access to the last element
// in this vector. The behavior is undefined unless this vector is not
// empty.
VALUE_TYPE *data() BSLS_KEYWORD_NOEXCEPT;
// Return the address of the modifiable first element in this vector,
// or a valid, but non-dereferenceable pointer value if this vector is
// empty.
// ACCESSORS
// *** iterators ***
const_iterator begin() const BSLS_KEYWORD_NOEXCEPT;
const_iterator cbegin() const BSLS_KEYWORD_NOEXCEPT;
// Return an iterator providing non-modifiable access to the first
// element in this vector, and the past-the-end iterator if this vector
// is empty.
const_iterator end() const BSLS_KEYWORD_NOEXCEPT;
const_iterator cend() const BSLS_KEYWORD_NOEXCEPT;
// Return the past-the-end (forward) iterator providing non-modifiable
// access to this vector.
const_reverse_iterator rbegin() const BSLS_KEYWORD_NOEXCEPT;
const_reverse_iterator crbegin() const BSLS_KEYWORD_NOEXCEPT;
// Return a reverse iterator providing non-modifiable access to the
// last element in this vector, and the past-the-end reverse iterator
// if this vector is empty.
const_reverse_iterator rend() const BSLS_KEYWORD_NOEXCEPT;
const_reverse_iterator crend() const BSLS_KEYWORD_NOEXCEPT;
// Return the past-the-end reverse iterator providing non-modifiable
// access to this vector.
// *** capacity ***
size_type size() const BSLS_KEYWORD_NOEXCEPT;
// Return the number of elements in this vector.
size_type capacity() const BSLS_KEYWORD_NOEXCEPT;
// Return the capacity of this vector, i.e., the maximum number of
// elements for which resizing is guaranteed not to trigger a
// reallocation.
bool empty() const BSLS_KEYWORD_NOEXCEPT;
// Return 'true' if this vector has size 0, and 'false' otherwise.
// *** element access ***
const_reference operator[](size_type position) const;
// Return a reference providing non-modifiable access to the element at
// the specified 'position' in this vector. The behavior is undefined
// unless 'position < size()'.
const_reference at(size_type position) const;
// Return a reference providing non-modifiable access to the element at
// the specified 'position' in this vector. Throw a
// 'bsl::out_of_range' exception if 'position >= size()'.
const_reference front() const;
// Return a reference providing non-modifiable access to the first
// element in this vector. The behavior is undefined unless this
// vector is not empty.
const_reference back() const;
// Return a reference providing non-modifiable access to the last
// element in this vector. The behavior is undefined unless this
// vector is not empty.
const VALUE_TYPE *data() const BSLS_KEYWORD_NOEXCEPT;
// Return the address of the non-modifiable first element in this
// vector, or a valid, but non-dereferenceable pointer value if this
// vector is empty.
};
// ============
// class vector
// ============
template <class VALUE_TYPE, class ALLOCATOR = allocator<VALUE_TYPE> >
class vector : public vectorBase<VALUE_TYPE>
, private BloombergLP::bslalg::ContainerBase<ALLOCATOR> {
// This class template provides an STL-compliant 'vector' that conforms to
// the 'bslma::Allocator' model. For the requirements of a vector class,
// consult the C++11 standard. In particular, this implementation offers
// the general rules that:
//
//: 1 A call to any method that would result in a vector having a size
//: or capacity greater than the value returned by 'max_size' triggers a
//: call to 'bslstl::StdExceptUtil::throwLengthError'.
//:
//: 2 A call to an 'at' method that attempts to access a position outside
//: of the valid range of a vector triggers a call to
//: 'bslstl::StdExceptUtil::throwOutOfRange'.
//
// Note that portions of the standard methods are implemented in
// 'vectorBase', which is parameterized on only 'VALUE_TYPE' in order to
// generate smaller debug strings.
//
// This class:
//: o supports a complete set of *value-semantic* operations
//: o except for 'BDEX' serialization
//: o is *exception-neutral*
//: o is *alias-safe*
//: o is 'const' *thread-safe*
// For terminology see {'bsldoc_glossary'}.
//
// In addition, the following members offer a full guarantee of rollback:
// if an exception is thrown during the invocation of 'push_back' or
// 'insert' with a single element at the end of a pre-existing object, the
// object is left in a valid state and its value is unchanged.
// PRIVATE TYPES
typedef BloombergLP::bslalg::ArrayPrimitives ArrayPrimitives;
// This 'typedef' is an alias for a utility class that provides many
// useful functions that operate on arrays.
typedef BloombergLP::bslmf::MovableRefUtil MoveUtil;
// This 'typedef' is a convenient alias for the utility associated with
// movable references.
typedef BloombergLP::bslma::AllocatorUtil AllocatorUtil;
// This 'typedef' is an alias for a utility class that provides many
// useful functions that operate on allocators.
typedef allocator_traits<ALLOCATOR> AllocatorTraits;
// This 'typedef' is an alias for the allocator traits type associated
// with this container.
public:
// PUBLIC TYPES
typedef VALUE_TYPE value_type;
typedef ALLOCATOR allocator_type;
typedef VALUE_TYPE& reference;
typedef const VALUE_TYPE& const_reference;
typedef typename AllocatorTraits::size_type size_type;
typedef typename AllocatorTraits::difference_type difference_type;
typedef typename AllocatorTraits::pointer pointer;
typedef typename AllocatorTraits::const_pointer const_pointer;
typedef VALUE_TYPE *iterator;
typedef VALUE_TYPE const *const_iterator;
typedef bsl::reverse_iterator<iterator> reverse_iterator;
typedef bsl::reverse_iterator<const_iterator> const_reverse_iterator;
private: