Home | Projects | Notes > C++ Programming > Sequence Container - std::vector

Sequence Container - `std::vector`

`std::vector`

Declared in the <vector> header file.
Dynamic size
- Can expand and contract as needed which is handled automatically by the STL.
- Elements are stored in continguous memory, like an array.
- As the std::vector expands a new larger area in memory is allocated and the current elements are moved to it.
Direct element access - Constant time: O(1)
Rapid insertion and deletion at the back - Constant time: O(1)
Insertion or deletion of elements (elsewhere) - Linear time: O(n)
All iterators are available but may become invalid.
- Iterator invalidation can occur when a std::vector resizes and allocates new memory to accommodate additional elements.

Initialization and Assignment


13
1
// Initialization
2
std::vector<int> v1{1, 2, 3, 4, 5};
3
std::vector<int> v2(10, 500);   // ten 500s
4

5
// Initialization
6
std::vector<std::string> v2{
7
    std::string{"Kyungjae"},
8
    "Sunny",    // C-style string will be converted to a std::string.
9
    std::string{"Yena"}
10
};
11

12
// Assignment via initializer list
13
v1 = {2, 4, 6, 8, 10};

Common Methods

For more information, see cppreference.com.


x
1
std::vector<int> v1{1, 2, 3, 4, 5};
2
std::vector<int> v2{10, 20, 30, 40, 50};
3

4
std::cout << v1.size();     // 5
5
std::cout << v1.capacity(); // 5
6
std::cout << v1.max_size(); // A very large number
7
std::cout << v1.at(0);      // 1 (Supports out-of-bounds check)
8
std::cout << v1[1];         // 2 (Does not support out-of-bounds check)
9
std::cout << v1.front();    // 1 (Returns reference to the first element)
10
std::cout << v1.back();     // 5 (Returns reference to the last element)
11
std::cout << v1.empty();    // 0 (false)
12

13
std::sort(v1.begin(), v1.end());
14

15
auto it = std::find(v1.begin(), v1.end(), 3);
16
v1.insert(it, 10);          // 1, 2, 10, 3, 4, 5
17

18
it = std::find(v1.begin(), v1.end(), 4);
19
v1.insert(it, v2.begin(), v2.end());
20
    // 1, 2, 10, 3, 10, 20, 30, 40, 50, 4, 5
21

22
v1.swap(v2);                // Swaps the two vectors

capacity(): Returns the number of elements the vector can hold before needing to allocate more memory. When this capacity is exceeded, the vector expands dynamically.
max_size(): Returns the maximum number of elements a vector can theoretically hold on the current system. This is typically a very large number and depends on system and implementation limits.


7
1
person p{"Kyungjae", 30};
2
std::vector<person> v;
3

4
v.push_back(p);                 // Add p to the back (copy is made)
5
v.pop_back();                   // Remove the last element (p in this case)
6
v.push_back(person{"Yena", 5}); // Add a temporary object using move semantics
7
v.emplace_back("Sunny", 20);    // Construct the object in-place. Very efficient!

L4: Remember, all standard container classes store copies of the elements they hold. So in this case, a copy of p is made.
L6: Creates a temporary (unnamed) person object and adds it to the vector using move semantics.
L7: Constructs the person object directly in place using the constructor. Very efficient - no moves, no copies. It’s built exactly where it needs to be. Use this!

Project: Usage of `std::array`


328
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4

5
class person
6
{
7
public:
8
    person() = default;
9
    person(std::string name, int age)
10
        : name{name}, age{age}
11
    {}
12
    // When using the STL with your custom class, always ensure that you 
13
    // overload `operator<` and `operator==`, as they are commonly used by
14
    // STL algorithms and containers.
15
    bool operator<(const person &rhs) const
16
    {
17
        return this->age < rhs.age;
18
    }
19
    bool operator==(const person &rhs) const 
20
    {
21
        return (this->name == rhs.name && this->age == rhs.age);
22
    }
23
    
24
private:
25
    friend std::ostream& operator<<(std::ostream &os, const person &p);
26
    std::string name;
27
    int age;
28
};
29

30
// Overloading the insertion operator as a global function.
31
std::ostream& operator<<(std::ostream &os, const person &p)
32
{
33
    os << p.name << ":" << p.age;
34
    return os;
35
}
36

37
// Using for_each() and a lambda expression to print elements.
38
void print1(const std::vector<int> &v)
39
{
40
    std::cout << "[ ";
41
    std::for_each(v.begin(), v.end(), [](int n) { std::cout << n << " "; });
42
    std::cout << "]" << std::endl;
43
}
44

45
// Template function to print elements of any vector.
46
template <typename T>
47
void print2(const std::vector<T> &v)
48
{
49
    std::cout << "[ ";
50
    for (const auto &elem : v)
51
        std::cout << elem << " ";
52
    std::cout << "]" << std::endl;
53
}
54

55
void test1(void)
56
{
57
    std::cout << "\nTEST1" << std::endl;
58
    
59
    std::vector<int> v{1, 2, 3, 4, 5};
60
    print1(v);
61

62
    v = {2, 4, 5, 6};   // assignment using an initialization list
63
    print2(v);
64

65
    std::vector<int> v1(10, 100);   // ten 100s in the vector
66
        // Note: This is not an initialization list. We are calling the
67
        // overloaded constructor defined by the std::vector container.
68
    print2(v1);
69
}
70

71
// size(), max_size(), capacity(), shrink_to_fit(), reserve()
72
void test2(void)
73
{
74
    std::cout << "\nTEST2" << std::endl;
75

76
    std::vector<int> v{1, 2, 3, 4, 5};
77

78
    print1(v);
79
    std::cout << "\nv size: " << v.size() << std::endl;
80
    std::cout << "v max size: " << v.max_size() << std::endl;
81
    std::cout << "v capacity: " << v.capacity() << std::endl;
82

83
    // Typically when a vector exceeds its capacity, it will double its
84
    // capacity.
85
    v.push_back(6);
86
    print1(v);
87
    std::cout << "\nv size: " << v.size() << std::endl;
88
    std::cout << "v max size: " << v.max_size() << std::endl;
89
    std::cout << "v capacity: " << v.capacity() << std::endl;
90

91
    // shrink_to_fit() will shrink the amount of storage allocated to exactly
92
    // the vector size.
93
    v.shrink_to_fit();  // C++11
94
    print2(v);
95
    std::cout << "\nv size: " << v.size() << std::endl;
96
    std::cout << "v max size: " << v.max_size() << std::endl;
97
    std::cout << "v capacity: " << v.capacity() << std::endl;
98

99
    // reserve() will reserve a specified amount of storage. The capacity will
100
    // be adjusted to the passed value.
101
    v.reserve(100);
102
    print2(v);
103
    std::cout << "\nv size: " << v.size() << std::endl;
104
    std::cout << "v max size: " << v.max_size() << std::endl;
105
    std::cout << "v capacity: " << v.capacity() << std::endl;
106
}
107

108
// [], at()
109
void test3(void)
110
{
111
    std::cout << "\nTEST3" << std::endl;
112

113
    std::vector<int> v{1, 2, 3, 4, 5};
114
    print1(v);
115

116
    v[0] = 100;     // does NOT provide out-of-bounds check
117
    v.at(1) = 200;  // provides out-of-bounds check
118

119
    print2(v);
120
}
121

122
// push_back(), emplace_back()
123
void test4(void)
124
{
125
    std::cout << "\nTEST4" << std::endl;
126
    std::vector<person> v;
127

128
    person p1{"Kyungjae", 30};
129
    print2(v);
130

131
    v.push_back(p1);
132
    print2(v);
133

134
    v.push_back(person{"Sunny", 20});   // temporary object, move semantics
135
    print2(v);
136
    
137
    // Pass the argument we would've passed into the constructor. emplace_back()
138
    // will call the constructor for us and put the element at the back.
139
    v.emplace_back("Yena", 5);  // very efficient! highly recommended!
140
    print2(v);
141
}
142

143
// front(), back(), pop_back()
144
void test5(void)
145
{
146
    std::cout << "\nTEST5" << std::endl;
147

148
    std::vector<person> v{
149
        {"Kyungjae", 30},
150
        {"Sunny", 20},
151
        {"Yena", 5}
152
    };
153

154
    print2(v);
155
    std::cout << "\nFront: " << v.front() << std::endl;
156
    std::cout << "Back: " << v.back() << std::endl;
157

158
    v.pop_back();   // removing the last element from a vector is O(1)
159
    print2(v);
160
}
161

162
// clear(), erase()
163
void test6(void)
164
{
165
    std::cout << "\nTEST6" << std::endl;
166

167
    std::vector<int> v{1, 2, 3, 4, 5};
168
    print1(v);
169

170
    v.clear();  // remove all elements
171
    print1(v);
172

173
    v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};// assignment using initialization list
174
    print1(v);
175
    v.erase(v.begin(), v.begin() + 2);  // remove a subset of elements
176
    print1(v);
177

178
    v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};// assignment using initialization list
179
    // erase all even numbers
180
    auto it = v.begin();
181
    while (it != v.end())
182
    {
183
        if (*it % 2 == 0)
184
        {
185
            v.erase(it);
186
        }
187
        else
188
        {
189
            it++;   // only increment if not erased!
190
        }
191
    }
192

193
    print1(v);
194
}
195

196
// swap()
197
void test7(void)
198
{
199
    std::cout << "\nTEST7" << std::endl;
200
    
201
    std::vector<int> v1{1, 2, 3, 4, 5};
202
    std::vector<int> v2{10, 20, 30, 40, 50};
203

204
    print1(v1);
205
    print1(v2);
206
    std::cout << std::endl;
207

208
    // To use swap, the continers must store data of the same type, but their
209
    // size can be different.
210
    v2.swap(v1);
211
    print1(v1);
212
    print1(v2);
213
}
214

215
// sort()
216
void test8(void)
217
{
218
    std::cout << "\nTEST8" << std::endl;
219

220
    std::vector<int> v{1, 32, 3, 50, 14};
221

222
    print1(v);
223
    std::sort(v.begin(), v.end());
224
    print1(v);
225

226
    // Note that the reverse() can be used to sort a vector in reverse order.
227
}
228

229
// copy(), copy_if(), back_inserter()
230
void test9(void)
231
{
232
    std::cout << "\nTEST9" << std::endl;
233

234
    // std::back_inserter constructs a back-insert iterator that inserts new
235
    // elements at the end of the container it is applied to. It's a special
236
    // type of output iterator and is very efficient!
237
    // There's also std::front_inserter, which can be used with containers like
238
    // std::deque and std::list.
239

240
    // Copy one list to another using an iterator and std::back_inserter.
241

242
    std::vector<int> v1{1, 2, 3, 4, 5};
243
    std::vector<int> v2{10, 20};
244

245
    print1(v1);
246
    print1(v2);
247
    std::cout << std::endl;
248

249
    // Copy the entire v1 and insert it to the end of v2.
250
    std::copy(v1.begin(), v1.end(), std::back_inserter(v2));
251
    print1(v1);
252
    print1(v2);
253
    std::cout << std::endl;
254

255
    // copy_if() the eGement is even
256
    v1 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
257
    v2 = {10, 20};
258

259
    print1(v1);
260
    print1(v2);
261
    std::cout << std::endl;
262

263
    // Use the following in the coding assessment. You'll get the job!
264
    std::copy_if(v1.begin(), v1.end(), std::back_inserter(v2),
265
        [](int n) { return n % 2 == 0; });  // even only!
266
    print1(v1);
267
    print1(v2);
268
}
269

270
// transform()
271
void test10(void)
272
{
273
    std::cout << "\nTEST10" << std::endl;
274

275
    // Transform over 2 ranges.
276
    std::vector<int> v1{1, 2, 3, 4, 5};
277
    std::vector<int> v2{10, 20, 30, 40, 50};
278
    std::vector<int> v3;
279
    
280
    // 1*10, 2*20, 3*30, 4*40, 5*50 and store the results in v3.
281
    std::transform(v1.begin(), v1.end(), v2.begin(), std::back_inserter(v3),
282
        [](int n1, int n2) { return n1 * n2; });
283
    
284
    print1(v3);    
285
}
286

287
// find(), insert()
288
void test11(void)
289
{
290
    std::cout << "\nTEST11" << std::endl;
291

292
    // Insert v2 into v1 before the element 5.
293
    std::vector<int> v1{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
294
    std::vector<int> v2{100, 200, 300, 400};
295
    
296
    print1(v1);    
297
    print1(v2);    
298
    std::cout << std::endl;
299

300
    auto it = std::find(v1.begin(), v1.end(), 5);
301
    if (it != v1.end())
302
    {
303
        std::cout << "Inserting..." << std::endl;
304
        v1.insert(it, v2.begin(), v2.end());
305
    }
306
    else
307
    {
308
        std::cout << "Error: 5 not found." << std::endl;
309
    }
310

311
    print1(v1);
312
}
313

314
int main(int argc, char *argv[])
315
{
316
    test1();
317
    test2();
318
    test3();
319
    test4();
320
    test5();
321
    test6();
322
    test7();
323
    test8();
324
    test9();
325
    test10();
326
    test11();
327
    return 0;
328
}


85
1

2
TEST1
3
[ 1 2 3 4 5 ]
4
[ 2 4 5 6 ]
5
[ 100 100 100 100 100 100 100 100 100 100 ]
6

7
TEST2
8
[ 1 2 3 4 5 ]
9

10
v size: 5
11
v max size: 2305843009213693951
12
v capacity: 5
13
[ 1 2 3 4 5 6 ]
14

15
v size: 6
16
v max size: 2305843009213693951
17
v capacity: 10
18
[ 1 2 3 4 5 6 ]
19

20
v size: 6
21
v max size: 2305843009213693951
22
v capacity: 6
23
[ 1 2 3 4 5 6 ]
24

25
v size: 6
26
v max size: 2305843009213693951
27
v capacity: 100
28

29
TEST3
30
[ 1 2 3 4 5 ]
31
[ 100 200 3 4 5 ]
32

33
TEST4
34
[ ]
35
[ Kyungjae:30 ]
36
[ Kyungjae:30 Sunny:20 ]
37
[ Kyungjae:30 Sunny:20 Yena:5 ]
38

39
TEST5
40
[ Kyungjae:30 Sunny:20 Yena:5 ]
41

42
Front: Kyungjae:30
43
Back: Yena:5
44
[ Kyungjae:30 Sunny:20 ]
45

46
TEST6
47
[ 1 2 3 4 5 ]
48
[ ]
49
[ 1 2 3 4 5 6 7 8 9 10 ]
50
[ 3 4 5 6 7 8 9 10 ]
51
[ 1 3 5 7 9 ]
52

53
TEST7
54
[ 1 2 3 4 5 ]
55
[ 10 20 30 40 50 ]
56

57
[ 10 20 30 40 50 ]
58
[ 1 2 3 4 5 ]
59

60
TEST8
61
[ 1 32 3 50 14 ]
62
[ 1 3 14 32 50 ]
63

64
TEST9
65
[ 1 2 3 4 5 ]
66
[ 10 20 ]
67

68
[ 1 2 3 4 5 ]
69
[ 10 20 1 2 3 4 5 ]
70

71
[ 1 2 3 4 5 6 7 8 9 10 ]
72
[ 10 20 ]
73

74
[ 1 2 3 4 5 6 7 8 9 10 ]
75
[ 10 20 2 4 6 8 10 ]
76

77
TEST10
78
[ 10 40 90 160 250 ]
79

80
TEST11
81
[ 1 2 3 4 5 6 7 8 9 10 ]
82
[ 100 200 300 400 ]
83

84
Inserting...
85
[ 1 2 3 4 100 200 300 400 5 6 7 8 9 10 ]

Sequence Container - std::vector

std::vector

Initialization and Assignment

Common Methods

Project: Usage of std::array

Sequence Container - `std::vector`

`std::vector`

Project: Usage of `std::array`