### 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 );