Standard Template Library (STL) Essentials

The standard library provides tested containers and algorithms so contest code can focus on its mathematical idea. An iterator identifies a position in a container; algorithms often receive a half-open iterator range [first,last). This lesson uses vector with sort, reverse, find, count, min, max and swap. Knowing an operation’s input range, return value and complexity is more useful than memorizing a large template.

Prerequisites: Arrays, vectors, strings, functions and records.

Build the idea

1. 1. Read iterator ranges correctly

   a.begin() refers to the first element and a.end() is the position just AFTER the last. The empty vector has begin()==end(). Passing begin,end processes all elements, but dereferencing end is invalid. Random-access vector iterators support subtraction, so it−a.begin() gives an index. Other container iterators may not support that operation.

2. 2. Apply standard algorithms

   sort(a.begin(),a.end()) sorts ascending; reverse over the same range reverses element order. min(x,y) and max(x,y) return the smaller or larger value; they do not scan a whole vector. swap exchanges two objects. For a whole sequence, min_element and max_element are related tools, but their result must not be dereferenced on an empty range.

3. 3. Interpret search results

   find(begin,end,target) scans and returns an iterator to the first equal element, or end if absent. Check that sentinel before using the iterator. count returns how many equal elements occur, not their positions. Neither requires sorted input. A sorted array enables binary search, taught later, but sorting first also changes the meaning of “original index.”

4. 4. Trace the sample sequence

   Read [4,2,4,1,3] with target 4. Sorting gives [1,2,3,4,4]; count is 2 and find returns sorted index 3. Reversing produces [4,4,3,2,1]. The reported index is explicitly after sorting, not the original first occurrence at zero. A range-based loop such as for(int x:a) visits each value; for(int& x:a) permits modifying elements.

5. 5. Choose a container by the needed operations

   Vector stores indexed contiguous data; string stores characters. Queue, stack, sets, maps and heaps have different interfaces and are developed in Data Structures. The same algorithm is not compatible with every iterator: std::sort needs random-access iterators and cannot directly sort a linked list’s iterators. Include the declared headers instead of assuming another header happens to include them.

This is a complete program. Compile with C++17 and enter the input described below.

// Key idea: 5. Choose a container by the needed operations Vector stores indexed contiguous data;
// string stores characters.
#include<iostream>
#include<vector>
#include<algorithm>
int main(){
    int n,target;
    std::cin>>n>>target;
    std::vector<int>a(n);
    for(int&x:a){
        std::cin>>x;
    }
    std::sort(a.begin(),a.end());
    auto position=std::find(a.begin(),a.end(),target);
    int index=position==a.end()?-1:(int)(position-a.begin());
    std::cout<<std::count(a.begin(),a.end(),target)<<' '<<index<<'\n';
    std::reverse(a.begin(),a.end());
    for(int i=0;i<n;++i){
        std::cout<<a[i]<<(i+1==n?'\n':' ');
    }
    if(n==0){
        std::cout<<'\n';
    }
    int x=3,y=8;
    std::swap(x,y);
    std::cout<<std::min(x,y)<<' '<<std::max(x,y)<<'\n';
}

Complexity analysis

O(n log(n+1)) sorting comparisons dominates O(n) find/count/reverse passes. Total vector storage is O(n); std::sort’s auxiliary storage is implementation-dependent (commonly O(log n) stack), and the standard does not require a specific implementation. min/max/swap on ints are constant-time. Iterator categories can change costs for other containers.

Example input and output

Read n target (0≤n≤100000), then n int values. Print target count and first SORTED index (−1 if absent), descending values on one line, then min/max of the fixed pair 3,8 after swapping.

Input

5 4
4 2 4 1 3

Output

2 3
4 4 3 2 1
3 8

Ascending order places the first 4 at index 3. Reversal produces descending order, and swapping does not change the pair’s min/max.

Practical applications

Use standard algorithms when their semantics match the task; they reduce routine implementation errors. Still understand required ordering, iterator categories and complexity. Later sorting lessons implement algorithms manually to explain their behavior, while most contest solutions should use std::sort for general sorting.

Check your understanding

What does a.end() represent?

Put it into practice

Change the output to show the first target index before sorting too.