YouTipCpp Libs Algorithm
The `` header file in the C++ standard library provides a set of algorithms for manipulating containers (such as arrays, vectors, lists, etc.). These algorithms include sorting, searching, copying, comparing, etc., and they are important tools for writing efficient, reusable code.
The `` header file defines a set of template functions that can be applied to any type of container as long as the container supports iterators. These algorithms typically accept two or more iterators as parameters, indicating the start and end positions of the operation.
### Syntax
Most functions in `` follow this basic syntax:
algorithm_name(container.begin(), container.end(), ...);
Here, `container` is a container object, and `begin()` and `end()` are member functions of the container that return iterators pointing to the beginning and end of the container.
## Examples
### 1. Sorting Algorithm
Function: sort
Definition: Sorts elements in a container.
Syntax:
sort(container.begin(), container.end(), compare_function);
Here, compare_function is an optional comparison function for custom sorting.
## Example
#include
#include
#include
int main(){
std::vector numbers ={5, 2, 9, 1, 5, 6};
std::sort(numbers.begin(), numbers.end());
for(int num : numbers){
std::cout<< num <<" ";
}
std::cout<< std::endl;
return 0;
}
Output:
1 2 5 5 6 9
std::partial_sort: Sorts a partial range, with the first n elements being sorted.
std::partial_sort(vec.begin(), vec.begin() + 3, vec.end());
std::stable_sort: Stable sort, preserves the relative order of equal elements.
std::stable_sort(vec.begin(), vec.end());
### 2. Search Algorithm
Function: find
Definition: Finds the first element in a container that matches a given value.
Syntax:
auto it = find(container.begin(), container.end(), value);
If found, it will point to the matching element; if not found, it will be equal to container.end().
## Example
#include
#include
#include
int main(){
std::vector numbers ={1, 2, 3, 4, 5};
auto it = std::find(numbers.begin(), numbers.end(), 3);
if(it != numbers.end()){
std::cout<<"Found: "<<*it << std::endl;
}else{
std::cout<<"Value not found."< 3; });
### 3. Copy Algorithm
Function: copy
Definition: Copies elements from one range to another container or array.
Syntax:
copy(source_begin, source_end, destination_begin);
Example:
## Example
#include
#include
#include
int main(){
std::vector source ={1, 2, 3, 4, 5};
int destination;
std::copy(source.begin(), source.end(), destination);
for(int i =0; i <5;++i){
std::cout<< destination<<" ";
}
std::cout<< std::endl;
return 0;
}
Output:
1 2 3 4 5
### 4. Comparison Algorithm
Function: equal
Definition: Compares whether two containers or two ranges are equal.
Syntax:
bool result = equal(first1, last1, first2);orbool result = equal(first1, last1, first2, compare_function);
## Example
#include
#include
#include
int main(){
std::vector v1 ={1, 2, 3, 4, 5};
std::vector v2 ={1, 2, 3, 4, 5};
bool are_equal = std::equal(v1.begin(), v1.end(), v2.begin());
std::cout<<(are_equal ?"Vectors are equal.":"Vectors are not equal.")<< std::endl;
return 0;
}
Output:
Vectors are equal.
### 5. Modification Algorithms
std::reverse: Reverses the order of elements in a range.
std::reverse(vec.begin(), vec.end());
std::fill: Assigns a value to all elements in a specified range.
std::fill(vec.begin(), vec.end(), 0); // Set all elements to 0
std::replace: Replaces a certain value in a range with another value.
std::replace(vec.begin(), vec.end(), 1, 99); // Replace all 1s with 99
std::copy: Copies elements from one range to another range.
std::vector vec2(6); std::copy(vec.begin(), vec.end(), vec2.begin());
### 6. Permutation Algorithms
std::next_permutation: Generates the next permutation in lexicographical order, returns false if there is no next permutation.
std::vector vec = {1, 2, 3};do { for (int n : vec) std::cout << n << " "; std::cout << std::endl;} while (std::next_permutation(vec.begin(), vec.end()));
std::prev_permutation: Generates the previous permutation in lexicographical order.
std::prev_permutation(vec.begin(), vec.end());
### 7. Merge Algorithms
std::merge: Merges two sorted ranges into one sorted range.
std::vector vec1 = {1, 3, 5}; std::vector vec2 = {2, 4, 6}; std::vector result(6); std::merge(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), result.begin());
std::inplace_merge: Merges two sorted sub-ranges within a single range.
std::inplace_merge(vec.begin(), middle, vec.end());
### 8. Set Algorithms
std::set_union: Computes the union of two sorted sets.
std::vector result(10);auto it = std::set_union(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), result.begin()); result.resize(it - result.begin());
std::set_intersection: Computes the intersection of two sorted sets.
auto it = std::set_intersection(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), result.begin()); result.resize(it - result.begin());
std::set_difference: Computes the difference of two sets.
auto it = std::set_difference(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), result.begin()); result.resize(it - result.begin());
### 9. Other Useful Algorithms