Sequential containers define only a few operations: in most cases, we can add and delete elements, access the first and last elements, determine whether the container is empty, and obtain an iterator pointing to the position after the first or last element.

We can imagine that users may also want to do many other useful operations: find a specific element, replace or delete a specific value, reorder elements, and so on.

The standard library does not define member functions for each container to implement these operations. Instead, a group of generic algorithm s are defined: they are called "algorithms" because they implement the public interfaces of some classical algorithms, such as sorting and search; They are called "generic" because they can be used for different types of elements and multiple container types.

10.1 general

Most algorithms are defined in the header file algorithm. The standard library also defines a set of numerical generic algorithms in numeric.

Generally, these algorithms do not directly operate on the container, but traverse an element range specified by two iterators. Usually, the algorithm traverses the range and performs some processing on each element. For example, suppose we have a vector of int and want to know whether the vector contains a specific value. The most convenient way to answer this question is to call the standard library algorithm find:

    vector<int> vec = { 1,2,34,5 };
	int val = 42;	//Value to find
	//If the desired element is found in the vec, the returned result points to it. Otherwise, the returned result is vec cend()
	auto result = find(vec.cbegin(), vec.cend(), val);

Since find operates on iterators, we can use the same find function to find values in any container. For example, you can use find to find a given value in a list of string s:

string val = "a value";
//This call looks up the string element in the list
auto result = find(lst.cbegin(), lst.cend(), val);

Similarly, since the pointer is like an iterator on a built-in array, we can use find to find the value in the array:

    int ia[] = { 24,132,23,127,109,46,210 };
	int val = 83;
	int *result = find(begin(ia), end(ia), val);

You can also find in the sub range of the sequence by passing the iterator (pointer) pointing to the position after the first and last elements of the sub range to find. For example, the following statement looks for a given element in ia[1], ia[2], and ia[3]:

    //Find elements from ia[1] to (but not including) ia[4]
	auto result = find(ia + 1, ia + 4, val);

How does the algorithm work

The job of find is to find a specific element in an unordered sequence of elements. Conceptually, find should perform the following steps:

1. Access the first element in the sequence.
2. Compare this element with the value we are looking for.
3. If this element matches the value we are looking for, find returns the value identifying this element.
4. Otherwise, find advances to the next element and repeats steps 2 and 3.
5. If the end of the sequence is reached, find should stop.
6. If find reaches the end of the sequence, it should return a value indicating that the element was not found. This value and the value returned in step 3 must have compatible types.

Iterators make the algorithm independent of containers

In the above find function flow, except step 2, other steps can be realized by iterator operation: element access can be realized by using iterator dereference operator; If a matching element is found, find can return an iterator pointing to the element; The iterator increment operator can be used to move to the next element; The tail iterator can be used to determine whether find reaches the end of a given sequence; Find can return a trailing iterator to indicate that the given element was not found.

But the algorithm depends on the operation of the element type

The use of iterators makes algorithms independent of container types, but most algorithms use operations on one (or more) element types.

Section 10.1 exercise

// Exercise 10.1: a function named count is defined in the header file algorithm, which is similar to find and takes a pair of iterators and a value as parameters.
// count returns the number of occurrences of the given value in the sequence. Write a program, read the int sequence, store it in the vector, and print how many element values are equal to the given value.
void countVal(const int val)
{
	
	int num;
	vector<int> vec;
	cout << "Please enter a sequence of integers ctrl+z End (input):";
	while (cin>>num)
	{
		vec.push_back(num);
	}
	cout << val << "An error occurred in the given sequence " << count(vec.cbegin(), vec.cend(), val) << " second" << endl;
}

// Exercise 10.2: redo the previous question, but read the string sequence and store it in the list.
void countString(const string & val)
{

	string word;
	list<string> lst;
	cout << "Please enter a sequence of integers ctrl+z End (input):";
	while (cin>>word)
	{
		lst.push_back(word);
	}
	cout << val << "An error occurred in the given sequence " << count(lst.cbegin(), lst.cend(), val) << " second" << endl;
}

10.2 initial generic algorithm

With a few exceptions, standard library algorithms operate on elements in a range. We call this element range "input range". Algorithms that accept an input range always use the first two parameters to represent the range, which are iterators pointing to the position after the first element and the tail element to be processed.

10.2.1 read only algorithm

Some algorithms only read the elements within their input range and never change the elements. find is such an algorithm, and so is the count function used above.

Another read-only algorithm is calculate, which is defined in the header file numeric. The accumulate function accepts three parameters. The first two indicate the range of elements to be summed, and the third parameter is the initial value of sum. Assuming that vec is a sequence of integers, then:

// Sum the elements in vec, and the initial value of sum is 0
int sum = accumulate(vec.cbegin(), vec.cend(), 0);

The third parameter of accumulate determines which addition operator is used in the function and the type of return value.

Algorithm and element type

Calculate takes the third parameter as the starting point of summation, which implies an assumption that the operation of adding element types to the types of and must be feasible. That is, the type of the element in the sequence must match or be convertible to the type of the third parameter.

The following is another example. Since string defines the + operator, we can connect all string elements in the vector by calling calculate:

string sum = accumulate(v.cbegin(), v.cend(), string(""));

Notice that we explicitly create a string with the third parameter. It is not allowed to pass an empty string as a string literal to the third parameter, which will lead to a compilation error.

//Error: the + operator is not defined on const char *
string sum = accumulate(v.cbegin(), v.cend(), "");

The reason is that if we pass a string literal, the type of object used to save and will be const char *. Since const char * has no + operator, this call will generate a compilation error.

Algorithm for operating two sequences

Another read-only algorithm is equal, which determines whether two sequences hold the same value. It compares each element in the first sequence with the corresponding element in the second sequence. Returns true if all corresponding elements are equal, otherwise false. This algorithm accepts three iterators: the first two (as before) represent the range of elements in the first sequence, and the third represents the first element of the second sequence.

// The number of elements in roster2 should be at least as many as roster1
equal(roster1.cbegin(), roster1.cend(), roster2.cbegin());