iterator

The container member () is generally provided by the function. Begin() / end() / begin() / cen() Call them to get iterators representing two endpoints. Functions with "c" prefix return constant iterators, but the specific type is best derived by automatic type:

vector<int> v = {1, 2, 3, 4, 5};
anto iter1 = v.begin();
auto iter2 = v.end();

//Global function, the effect is the same
auto iter3 = std::begin(v);
auto iter3 = std::end(v);

Like pointers, iterators can also go forward or backward, but it must not be assumed that they must support "+ +" - "operations. It is best to operate with functions:

advance(): the iterator advances or retreats by a specified number of steps
next()/prev(): get a position before and after the iterator, and the iterator itself does not move
distance(): calculates the distance between two iterators

std::array<int, 5> testArray{ 0, 1, 2, 3, 4 };
auto beginIter = testArray.begin();
auto endIter = testArray.end();

int dis = std::distance(beginIter, endIter);
std::cout << "distance " << dis << std::endl;

auto p = std::next(beginIter);
std::cout << "next is " << *p << std::endl;

std::advance(p, 2);
std::cout << "advance is " << *p << std::endl;

STL algorithm can only indirectly access containers and elements through iterators, so the processing range and ability of the algorithm are determined by the iterators.

inorder traversal

for_each:

vector<int> v = {3, 5, 1, 7, 10}; //Vector container

auto print = [](const auto& x)
{
    cout << x << ",";
};

for_each(cbegin(v), cend(v), print);

for_each(
    cbegin(v), cend(v),
    [](const auto& x)
    {
       cout << x << ",";
    }
);

C++17 new for_each_n. Containers can be traversed in different ways. Only the first n elements of the container need to be processed, which meets some special applications:

for_each_n(
    cbegin(v), 3, //Specify starting point and number
    [](const auto& x){
        ...
    }
);

Sorting algorithm

std::sort(begin(v), end(v));  //Quick sort


vector<int> v = {3, 5, 1, 7, 10, 99, 14};

//reverse existing order
std::reverse(begin(v), end(v), rand);

minstd_rand rand; //Random number generator
std::shuffle(begin(v), end(v), rand); //Random reordering elements

//TopN
std::partial_sort(begin(v), next(begin(v), 3), end(v)); //Top 3

//BestN
std::ntn_element(begin(v), next(begin(v), 3), end(v));  //Top 3. And do not reorder them

//median
auto mid_iter = next(begin(v), size(n) / 2);
std::ntn_element(begin(v), mid_iter, 3), end(v)); 
cout << "median is " << *mid_iter << endl;

//partition divides elements into two groups according to some rule
auto pos = std::partition(
    begin(v), end(v),
    [](const auto& x){
        return x > 9;
    }
);
for_each(begin(v), pos, print); //Output grouped data

//Min max find the first and last place
auto[mi, ma] = std::minmax_element(cbegin(v), cend(v)); 

When using these sorting algorithms, it should be noted that they have high requirements for iterators. They usually access iterators randomly, so it is best to call them on the sequence container array/vector.

If you sort the list, you should call the member function sort, which optimizes the linked list structure. The set/map itself has been sorted and operated directly. For unordered containers, do not use sorting algorithms.

Search algorithm

Binary search_ search

vector<int> v = {3, 5, 1, 7, 10, 99, 42};
std::sort(begin(v), end(v));

auto found = std::binary_search(cbegin(v), cend(v), 7); //Returns bool, which can only determine whether the element is present or not

Returns the first location greater than or equal to the value: std::lower_bound

decltype(cend(v)) pos; //Declare an iterator, using decltype
pos = std::lower_bound(cbegin(v), cend(v), 7);  //Find the first position greater than or equal to 7

found = (pos != cend(v)) && (*pos == 7);
assert(found);

pos = std::lower_bound(cbegin(v), cend(v), 9); 
found = (pos != cend(v)) && (*pos == 9);
assert(!found);

Returns the last location greater than the target value: std::upper_bound

pos = std::upper_bound(cbegin(v), cend(v), 9); //Find the first position greater than 9

Obtain the [lower_bound,upper_bound] interval: std::equal_range

auto [lower, upper] = std::equal_range(cbegin(v), cend(v), 7);

Find the location where the first specified element appears: find

vector<int> v = {1,9,11,3,5,7};  //Vector container

decltype(v.begin()) pos; //Declare an iterator, using decltype
pos = find(begin(v), end(v), 3); //Find the location of the first occurrence 3
assert(pos != end(v));

Use criteria to find: find_if

pos = std::find_if(begin(v), end(v), [](auto x){return x % 2 == 0; });

Find a subinterval: find_first_of

array<int, 2> arr = {3, 5}; //Array container
pos = std::find_first_of(begin(v), end(v), begin(arr), end(arr)); //Find a subinterval

Range algorithm

C++20 introduces a new range type, which is an abstract concept on the container. It can be understood as an iterator indicating the head and end positions, that is, pair < begin, end >, so that range itself contains enough information that can be used for algorithms. Most algorithms can work with only one range parameter. The standard algorithm named range:: and the algorithm named range:: in C + + use the same name, but the algorithm named range:: is very concise.

vector<int> v = {9, 5,2,3,1};
auto print = [](const auto &x){
    cout << x << ",";
}

namespaces ranges = std::ranges; //Namespace alias to simplify code
ranges::for_each(v, print); //Range for_each algorithm
ranges::count_if(v, [auto &x]{return x >= 5;}); //Range count_if algorithm
ranges::shuffle(v, rand); //Range random rearrangement element
ranges::stable_sort(v);  //The ranges remain in relative order
ranges::binary_search(v, 7);  //Range binary search
auto pos = ranges::lower_bound(v, 3); //Whether the range bisection search exists
ranges::partial_sort(v, next(begin(v), 3)); //Range partial sort

auto [mi, ma] = ranges::minmax_element(v); //Range lookup maximum and minimum

C++20 also introduces view, which is the view of container and has certain data operation ability. It also overloads "|" and can realize the series operation of multiple views. Located in namespace std::views.

• take: select the first N elements in the view
• drop: skip the first N elements in the view
• keys: select the first member in pair
• values: select the second member in pair
• Reverse: reverse all elements in the view
• Filter: use predicate function to filter out specific elements in the view

The use of view is very different from the traditional function call method:

vector<int> v ={3,7,2,4,9,6,8,1,5};
namespace views = std::views;
for(auto && x: v | views::drop(3) | views::reverse) //Pipe operators concatenate view operations
{
    cout << x << ",";  //Output 5,1,8,6,9,4
}

v | views::drop(3): indicates that drop acts on v, skipping the first three elements and leaving only the remaining elements, that is, {4,9,6,8,1,5}. After its operation, it still gets a view, so it can continue to use pipeline operation.

The following | views::reverse indicates the reverse operation. Reverse the previous view s and pass the final result to the for loop.

The above operation is equivalent to:

auto r1 = v | views::drop(3);
auto r2 = r1 | views::reverse;
ranges::for_each(r2, print);  //Call range algorithm output results

Further examples:

ranges::for_each(v | views::filter(
                   [](auto &x){
                     return x % 2 == 0; 
                   }),
   print
);  //Output 2,4,6,8

decltype(v) v2;
ranges::copy(v | views::take(3),  //Only the first three elements are taken
             back_inserter(v2));  //Insert element into new container

vector<pair<int, string>> pairs = {{1, "one"}, {2, "two"}, {3, "three"}};
ranges::for_each(
    pairs | views::take(2) | views::values,  //Take the first two elements and take the second member
    print    //Output one two
);