# Vector Part 3

Estimated reading: 14 minutes 63 Views

Example 1:

```#include <iostream>
#include <vector>
using namespace std;

int main() {
vector<int> v(5);  // Initialize vector v with size 5
int n = 0;

// Prompt the user to enter vector elements
cout << "Enter Vector Elements:\n";
for (size_t i = 0; i < v.size(); i++) {
cin >> v[i];  // Read input into vector element at index i

// Check if we're at the end of the vector
if (i == v.size() - 1) {
cout << "If you want to resize the list, enter the new size. Enter -1 to finish: ";
cin >> n;
if (n == -1)
break;
else
v.resize(n);  // Resize the vector to the new size entered by the user
}
}

// Output the elements of the vector
cout << "Vector elements are:\n";
for (size_t i = 0; i < v.size(); i++) {
cout << v[i] << endl;  // Output each element followed by a newline
}

return 0;
}
```

Here’s what each part of the code does:

• vector<int> v(5);: Initializes a vector v with size 5, containing default-initialized elements (all elements are initialized to zero in this case).
• Prompts the user to enter vector elements.
• Reads input from the user into the vector elements using a loop. After reading the last element, the code prompts the user to either resize the vector or exit the loop by entering -1.
• If the user enters a new size, the vector is resized accordingly using v.resize(n).
• Outputs the elements of the vector after the loop ends.

This code allows the user to dynamically resize the vector during input and then displays the elements of the vector.

Example 2:

```#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
vector<int> v = {5, 1, 2, 7, 0, 3};  // Initialize vector v with some unsorted integers

sort(v.begin(), v.end());  // Sort the elements of the vector in ascending order

// Output the sorted elements of the vector
for (auto it : v) {
cout << it << endl;  // Output each sorted element followed by a newline
}

return 0;
}
```

Here’s what each part of the code does:

• vector<int> v = {5, 1, 2, 7, 0, 3};: Initializes a vector v with six integers in an unsorted order.
• sort(v.begin(), v.end());: Sorts the elements of the vector v in ascending order using the std::sort algorithm. The sort function requires two iterators specifying the range to be sorted, which are v.begin() (pointing to the first element) and v.end() (pointing to one past the last element).
• for (auto it : v) { … }: This is a range-based for loop that iterates over the sorted vector v. It iterates through each element of the vector v in ascending order.
• cout << it << endl;: Within the loop, it prints each element it of the vector followed by a newline using cout.

So, the output of this code will be:

```0
1
2
3
5
7
```

It prints each element of the sorted vector v in ascending order, one element per line.

Example 3:

```#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
vector<int>v = {5, 1, 2, 7, 0, 3};
sort(v.rbegin(), v.rend());
for (auto it:v)
{
cout << it << endl;
}

return 0;
}
```

Here’s what each part of the code does:

• sort(v.rbegin(), v.rend());: Sorts the elements of the vector v in descending order using the std::sort algorithm with reverse iterators. The sort function requires two iterators specifying the range to be sorted, which are v.rbegin() (pointing to the last element, treated as the first for sorting) and v.rend() (pointing to one before the first element, treated as the last for sorting).

So, the output of this code will be:\

```7
5
3
2
1
0```

It prints each element of the sorted vector v in descending order, one element per line.

Example 4:

```#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
vector<int>v = {5, 1, 2, 7, 0, 3};
reverse(v.begin(), v.end());
for (auto it:v)
{
cout << it << endl;
}

return 0;
}
```
• reverse(v.begin(), v.end());: Reverses the elements of the vector v using the std::reverse algorithm. The reverse function requires two iterators specifying the range to be reversed, which are v.begin() (pointing to the first element) and v.end() (pointing to one past the last element).

So, the output of this code will be:

```3
0
7
2
1
5
```

It prints each element of the reversed vector v, one element per line.

Example 5:

```#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
vector<int> v = {5, 1, 2, 7, 0, 3};  // Initialize vector v with some integers

// Find and output the minimum element in the vector
cout << *min_element(v.begin(), v.end()) << endl;

// Find and output the maximum element in the vector
cout << *max_element(v.begin(), v.end()) << endl;

// Find and output the minimum element in the vector excluding the last two elements
cout << *min_element(v.begin(), v.end() - 2) << endl;

return 0;
}
```

Here’s what each part of the code does:

• vector<int> v = {5, 1, 2, 7, 0, 3};: Initializes a vector v with six integers in the given order.
• cout << *min_element(v.begin(), v.end()) << endl;: Finds the minimum element in the vector v using the std::min_element algorithm. The min_element function returns an iterator pointing to the minimum element, and * dereferences this iterator to obtain the value of the minimum element. The minimum element is then printed followed by a newline.
• cout << *max_element(v.begin(), v.end()) << endl;: Similar to above, this line finds and prints the maximum element in the vector v.
• cout << *min_element(v.begin(), v.end() – 2) << endl;: Finds the minimum element in the vector v excluding the last two elements. The range used for finding the minimum element is from v.begin() to v.end() – 2 (excluding the last two elements). The minimum element is then printed followed by a newline.

So, the output of this code will be:

```0
7
1
```

It prints the minimum element, maximum element, and minimum element excluding the last two elements of the vector v, each followed by a newline.

Example 6:

```#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
vector<int>v = {5, 1, 2, 7, 0, 3};

auto pair = minmax_element(v.begin(), v.end());
cout << *pair.first << endl;
cout << *pair.second << endl;

return 0;
}```

Here’s what each part of the code does:

• auto pair = minmax_element(v.begin(), v.end());: Finds both the minimum and maximum elements in the vector v using the std::minmax_element algorithm. This function returns a pair of iterators, where the first iterator points to the minimum element and the second iterator points to the maximum element.
• cout << *pair.first << endl;: Outputs the value of the minimum element by dereferencing the iterator pair.first.
• cout << *pair.second << endl;: Outputs the value of the maximum element by dereferencing the iterator pair.second.

So, the output of this code will be:

```0
7
```

It prints the minimum and maximum elements of the vector v, each followed by a newline.

Example 7:

```#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
vector<int> v = {5, 1, 2, 7, 0, 3};  // Initialize vector v with some integers

// Find the minimum element in the vector
auto it = min_element(v.begin(), v.end());

// Sort the elements of the vector up to (but not including) the minimum element
sort(v.begin(), it);

// Output the sorted elements of the vector
for (auto i : v) {
cout << i << endl;  // Output each sorted element followed by a newline
}

return 0;
}
```

Here’s what each part of the code does:

• auto it = min_element(v.begin(), v.end());: Finds the minimum element in the vector v using the std::min_element algorithm. This function returns an iterator pointing to the minimum element.
• sort(v.begin(), it);: Sorts the elements of the vector v up to (but not including) the minimum element found by min_element. It uses the std::sort algorithm with a range specified by iterators, from v.begin() to it. This sorts the elements before the minimum element.
• for (auto i : v) { … }: This is a range-based for loop that iterates over the sorted vector v. It iterates through each element of the vector v in sorted order.
cout << i << endl;: Within the loop, it prints each sorted element i of the vector followed by a newline using cout.

So, the output of this code will be:

```0
1
2
5
7
```

It prints each element of the vector v up to the minimum element, sorted in ascending order, each followed by a newline.

Example 8:

```#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool GreaterThanThree(int i) {
return i > 3;
}

int main() {
vector<int> v = {5, 1, 2, 7, 0, 3};  // Initialize vector v with some integers

// Sort the elements of the vector in ascending order
sort(v.begin(), v.end());

// Find the first element greater than 3 using find_if with GreaterThanThree as the predicate
auto it = find_if(v.begin(), v.end(), GreaterThanThree);

// Output all elements greater than 3
for (; it != v.end(); it++) {
cout << *it << endl;  // Output each element greater than 3 followed by a newline
}

return 0;
}
```

Here’s what each part of the code does:

• bool GreaterThanThree(int i): Defines a predicate function GreaterThanThree that returns true if the input integer i is greater than 3.
• vector<int> v = {5, 1, 2, 7, 0, 3};: Initializes a vector v with six integers.
• sort(v.begin(), v.end());: Sorts the elements of the vector v in ascending order using the std::sort algorithm.
• auto it = find_if(v.begin(), v.end(), GreaterThanThree);: Finds the first element greater than 3 in the sorted vector v using the std::find_if algorithm with the GreaterThanThree predicate function.
• for (; it != v.end(); it++) { … }: This is a for loop that iterates over the elements from the first element greater than 3 until the end of the vector. It outputs each element greater than 3 followed by a newline using cout.

So, the output of this code will be:

```5
7
```

It prints each element of the vector v that is greater than 3, each followed by a newline.

Example 9:

```#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool GreaterThanThree(int i)
{
return i > 3;
}
int main()
{
int arr[] = {10, 20, 30, 40, 50, 60, 70};
vector<int> v(7);
copy(arr, arr + 7, v.begin());
cout << "myvector contains: ";
for (auto it:v)
cout << it << " ";
return 0;
}
```

Here’s what each part of the code does:

• int arr[] = {10, 20, 30, 40, 50, 60, 70};: Initializes a C-style array arr with seven integers.
• vector<int> v(7);: Initializes a vector v with size 7.
• copy(arr, arr + 7, v.begin());: Copies elements from the C-style array arr to the vector v using the std::copy algorithm. The copy function requires three parameters: the beginning and end iterators of the source range (here, arr and arr + 7 representing the whole array), and the beginning iterator of the destination range (here, v.begin()).
• cout << “myvector contains: “;: Outputs a message indicating the start of the output.
• for (auto it : v) cout << it << ” “;: This is a range-based for loop that iterates over the elements of the vector v. It outputs each element of the vector followed by a space.

So, the output of this code will be:

```myvector contains: 10 20 30 40 50 60 70
```

Example 10:

```#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
vector<int> from_vector = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
vector<int> to_vector(15);
copy_backward(from_vector.begin(), from_vector.end(), to_vector.end());
cout << "to_vector contains: ";
for (auto i: to_vector)
cout << i << " ";
return 0;
}```

Here’s what each part of the code does:

• vector<int> from_vector = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};: Initializes a source vector from_vector with ten integers.
• vector<int> to_vector(15);: Initializes a target vector to_vector with size 15.
• copy_backward(from_vector.begin(), from_vector.end(), to_vector.end());: Copies elements from the source vector from_vector to the target vector to_vector in reverse order using the std::copy_backward algorithm. The copy_backward function requires three parameters: the beginning and end iterators of the source range (here, from_vector.begin() and from_vector.end() representing the whole vector), and the end iterator of the destination range (here, to_vector.end()).
• cout << “to_vector contains: “;: Outputs a message indicating the start of the output.
• for (auto i : to_vector) cout << i << ” “;: This is a range-based for loop that iterates over the elements of the target vector to_vector. It outputs each element of the target vector followed by a space.

So, the output of this code will be:

`to_vector contains: 0 0 0 0 0 1 2 3 4 5 6 7 8 9 10`

It prints each element of the target vector to_vector, which contains the elements of the source vector from_vector copied in reverse order, followed by a space. The initial elements of to_vector that were not overwritten by the copy operation are left unchanged (default-initialized to 0 in this case).

Example 11:

```#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;

int main() {
vector<int> v = {1, 2, 3, 4, 5};  // Initialize a vector v with five integers

// Copy elements from the vector v to the standard output (cout)
copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));

return 0;
}
```

Here’s what each part of the code does:

• copy(v.begin(), v.end(), ostream_iterator<int>(cout, ” “));: Copies elements from the vector v to the standard output (cout) using the std::copy algorithm and std::ostream_iterator. The copy function requires three parameters: the beginning and end iterators of the source range (here, v.begin() and v.end() representing the whole vector), and the output iterator (here, ostream_iterator<int>(cout, ” “)) that writes each copied element to the standard output with a space separator.

So, the output of this code will be:

```1 2 3 4 5
```

## Properties of vector

1. Add -> Back -> O(1):
This line indicates that adding an element to the back (end) of a vector has a time complexity of O(1), meaning it’s a constant-time operation. Vectors have dynamic memory allocation, and adding an element to the back typically involves appending the element to the end of the underlying contiguous memory block, which can be done in constant time.
2. Delete -> Back -> O(1):
Deleting an element from the back (end) of a vector also has a time complexity of O(1), which means it’s a constant-time operation. Removing the last element usually involves decrementing the size of the vector, and no reallocation or shifting of elements is required.
3. Add -> Any Where -> O(N):
Adding an element anywhere except the back of the vector, such as at the front or in the middle, has a time complexity of O(N). This is because inserting an element at an arbitrary position may require shifting all subsequent elements to make room for the new element, which takes linear time proportional to the number of elements shifted.
4. Delete -> Any Where -> O(N):
Similarly, deleting an element from anywhere except the back of the vector also has a time complexity of O(N). Removing an element from an arbitrary position may require shifting all subsequent elements to fill the gap left by the deleted element, which also takes linear time proportional to the number of elements shifted.
5. Access -> [] – at() -> O(1):
Accessing an element in a vector by index using the square brackets ([]) operator or the at() member function has a time complexity of O(1). This means that accessing any element in the vector takes constant time regardless of the size of the vector. Vectors provide constant-time random access because they store elements in a contiguous memory block, allowing for direct access to any element by its index.
6. Search -> find() -> O(log N):
Searching for an element in a sorted vector using the std::find() algorithm has a time complexity of O(log N) when the vector is sorted. This is because std::find() performs a binary search on the sorted vector, which has a logarithmic time complexity. However, it’s important to note that if the vector is not sorted, the time complexity of finding an element using std::find() would be O(N), as it performs a linear search.

Implemented as dynamic arrays

### Drawbacks:

1. Expensive reallocation
2. Requires Contiguous Memory