Arrays: Methods & Functions - Язык программирования C++ для спортивного программирования
Arrays: Methods & Functions
Arrays: Methods & Functions
Introduction
In the previous lesson, we learned how to declare arrays, access elements using indices from 0 to n−1, and write manual loops to traverse, sum, or modify values.
While manual loops are important for understanding the basics, C++ provides a collection of built-in functions in <algorithm> and <numeric>. These functions allow us to perform common array operations—such as sorting, reversing, swapping, filling, and summing—much faster, with cleaner code, and without off-by-one errors.
In this lesson, we will focus exclusively on standard arrays and learn how to use these essential functions on whole arrays and subsegments.
Core concept: Ranges with Pointers [a, a + n)
Standard library functions in C++ operate on a half-open range, denoted as [start,end).
The pointer points to the included in the operation.
start
first element
The end pointer points to the position immediately after the last element.
For a 0-indexed array a containing n elements (a[0],a[1],…,a[n−1]):
a points to the first element a[0].
a + n points right after the last element a[n−1].
Therefore, to process the entire array of size n, we pass the range a, a + n.
Operating on a subsegment
We can also apply standard functions to only a specific part of an array. To operate on elements from index l to index r (inclusive), the range is:
[a+l,a+r+1)
a + l is the starting cell a[l].
a + r + 1 is one position past a[r].
Essential Standard Functions for Arrays
1. swap(a[i], a[j])
The swap function exchanges the values of two elements in O(1) constant time.
2. reverse(a, a + n)
The reverse function reverses the order of elements in a range in O(n) linear time.
To reverse the entire array:
To reverse only a subsegment from index l to index r:
3. sort(a, a + n)
The sort function rearranges elements in non-decreasing order in O(nlogn) time.
To sort the entire array in ascending order:
To sort in descending order (from largest to smallest):
To sort only a subsegment from index l to index r:
4. fill(a, a + n, value)
The fill function sets every element in a range to a chosen value in O(n) time.
This is especially useful for resetting frequency or boolean presence arrays:
5. count(a, a + n, target)
The count function counts how many times a target value appears in the array in O(n) time.
6. accumulate(a, a + n, 0LL)
From the <numeric> library, accumulate calculates the total sum of elements across a range in O(n) time.
Note: Always use 0LL as the initial value when sums can exceed the 32-bit integer limit.
Examples & Problem Patterns
Example 1: Cyclic shift by k positions (The 3-Reverse Trick)
Given an array of n integers, rotate all elements to the right by k positions cyclically.
Example:
Approach and solution
Rotating an array to the right by k positions can be achieved in O(n) time and O(1) extra memory using three reverse calls:
Reverse the first k elements ([0,k−1]): [5, 4]o[4, 5].
Reverse the remaining n−k elements ([k,n−1]): [3, 2, 1]o[1, 2, 3].
Result: [4, 5, 1, 2, 3].
Algorithm:
Implementation:
Example 2: Checking if an array is a palindrome
Given an array of n integers, determine if the array reads the same forward and backward. Print YES if it is a palindrome, or NO otherwise.
Example:
Approach and solution
We copy array a into array b, reverse array b using reverse(b, b + n), and check if every element a[i] equals b[i].
Algorithm:
Implementation:
Example 3: Difference between k-th largest and k-th smallest
Given an array of n integers and an integer k (1≤k≤n), find the difference between the k-th largest and k-th smallest element.
Example:
Explanation: The sorted array is [3, 8, 9, 12, 15, 20]. The 2nd smallest is 8 (a[1]) and the 2nd largest is 15 (a[4]). Difference: 15−8=7.
Approach and solution
Sort the array in ascending order using sort(a, a + n).
The k-th smallest element is at index k−1: a[k−1].
The k-th largest element is at index n−k: a[n−k].
Print a[n−k]−a[k−1].
Algorithm:
Implementation:
Example 4: Swap first and last elements
Given an array of n integers, swap the first element and the last element using swap(), and print the resulting array.
Example:
Approach and solution
The first element is at index 0 (a[0]) and the last element is at index n−1 (a[n−1]). We exchange their values with swap(a[0], a[n - 1]).
Algorithm:
Implementation:
Example 5: Multiple test cases with fill()
You are given t test cases. In each testcase, you receive n numbers (each between 1 and 100). Count how many distinct numbers appear in that testcase.
Example:
Approach and solution
We use a boolean presence array seen[101]. Before processing each testcase, we reset all elements to false using fill(seen, seen + 101, false). Then we mark numbers and count distinct values.
Algorithm:
Implementation:
Quick Reference Summary Table
Operation
Syntax on Array a[n]
Syntax on Subsegment [l,r]
Time Complexity
First Element
a[0]
a[l]
O(1)
Last Element
a[n-1]
a[r]
O(1)
Swap
swap(a[i], a[j])
swap(a[i], a[j])
O(1)
Reverse
reverse(a, a + n)
reverse(a + l, a + r + 1)
O(n)
Sort (Ascending)
sort(a, a + n)
sort(a + l, a + r + 1)
O(nlogn)
Sort (Descending)
sort(a, a + n, greater<int>())
sort(a + l, a + r + 1, greater<int>())
O(nlogn)
Fill with Value
fill(a, a + n, val)
fill(a + l, a + r + 1, val)
O(n)
Count Value
count(a, a + n, val)
count(a + l, a + r + 1, val)
O(n)
Sum of Elements
accumulate(a, a + n, 0LL)
accumulate(a + l, a + r + 1, 0LL)
O(n)
Input:
5 2
1 2 3 4 5
Output:
4 5 1 2 3
1. Read n and k.
2. Read a[0..n-1].
3. Set k = k % n.
4. reverse(a, a + n).
5. reverse(a, a + k).
6. reverse(a + k, a + n).
7. Print a[0..n-1].
Input:
5
1 3 7 3 1
Output:
YES
1. Read n.
2. Read a[0..n-1].
3. Copy a[0..n-1] to b[0..n-1].
4. reverse(b, b + n).
5. Check if all a[i] == b[i].
6. If equal, print YES. Otherwise, print NO.
Input:
6 2
15 3 9 20 8 12
Output:
7
1. Read n and k.
2. Read a[0..n-1].
3. sort(a, a + n).
4. Print a[n - k] - a[k - 1].
1. Read t.
2. For each testcase:
1. Read n.
2. fill(seen, seen + 101, false).
3. For each of the n numbers x:
1. Set seen[x] = true.
4. Count how many values in seen[1..100] are true.
5. Print the count.
int a[5] ={10, 20, 30, 40, 50};// Swap the first and last elements:swap(a[0], a[4]);// Array becomes: {50, 20, 30, 40, 10}
int a[5] ={1, 2, 3, 4, 5};reverse(a, a + 5);// Array becomes: {5, 4, 3, 2, 1}
int a[6] ={10, 20, 30, 40, 50, 60};// Reverse elements from index 1 to 4 (values 20, 30, 40, 50):reverse(a + 1, a + 5);// Array becomes: {10, 50, 40, 30, 20, 60}
int a[5] ={40, 10, 50, 20, 30};sort(a, a + 5);// Array becomes: {10, 20, 30, 40, 50}
int a[5] ={40, 10, 50, 20, 30};sort(a, a + 5, greater<int>());// Array becomes: {50, 40, 30, 20, 10}
// Sorts only elements between index l and r inclusive:sort(a + l, a + r + 1);
int a[5];fill(a, a + 5, 7);// Array becomes: {7, 7, 7, 7, 7}
bool seen[100];fill(seen, seen + 100, false);
int a[6] ={3, 1, 4, 1, 5, 1};int ones = count(a, a + 6, 1);// ones is 3
#include <numeric>int a[5] ={10, 20, 30, 40, 50};long long total = accumulate(a, a + 5, 0LL);// total is 150
#include <iostream>#include <algorithm>using namespace std;int main(){ int n, k; cin >> n >> k; int a[n]; for(int i = 0; i < n; i++){ cin >> a[i];} k = k % n; reverse(a, a + n); reverse(a, a + k); reverse(a + k, a + n); for(int i = 0; i < n; i++){ cout << a[i]<< ' ';} cout << endl; return 0;}
#include <iostream>#include <algorithm>using namespace std;int main(){ int n; cin >> n; int a[n], b[n]; for(int i = 0; i < n; i++){ cin >> a[i]; b[i] = a[i];} reverse(b, b + n); bool is_palindrome = true; for(int i = 0; i < n; i++){ if(a[i] != b[i]){ is_palindrome = false; break;}} if(is_palindrome){ cout << "YES"<< endl;} else{ cout << "NO"<< endl;} return 0;}
#include <iostream>#include <algorithm>using namespace std;int main(){ int n, k; cin >> n >> k; int a[n]; for(int i = 0; i < n; i++){ cin >> a[i];} sort(a, a + n); int k_smallest = a[k - 1]; int k_largest = a[n - k]; cout << k_largest - k_smallest << endl; return 0;}
#include <iostream>#include <algorithm>using namespace std;int main(){ int n; cin >> n; int a[n]; for(int i = 0; i < n; i++){ cin >> a[i];} swap(a[0], a[n - 1]); for(int i = 0; i < n; i++){ cout << a[i]<< ' ';} cout << endl; return 0;}
#include <iostream>#include <algorithm>using namespace std;int main(){ int t; cin >> t; bool seen[101]; while(t--){ int n; cin >> n; fill(seen, seen + 101, false); for(int i = 0; i < n; i++){ int x; cin >> x; seen[x] = true;} int distinct_count = 0; for(int v = 1; v <= 100; v++){ if(seen[v]){ distinct_count = distinct_count + 1;}} cout << distinct_count << endl;} return 0;}