Standard Template Library: Standard Template Library( STL)

1. Sequential container: vector, list. It is mainly used for iterative operations.
2. Associated container: map, set. It is mainly used to quickly find the element value in the container.

Generic algorithms provide many operations that can act on container classes and array types. These elements are called generics because they are independent of the type of operation they want.

Generic algorithm achieves the purpose of "being independent of the type of operation object" through function template technology. The realization of "independent of the operation container" is not to operate directly on the container. Instead, a pair of iterators (first and last) are used to indicate the range of elements we want to iterate.

3.1 the arithmetic of pointers

Given a vector and a value, if the value is in the vector, return a pointer to the value; Otherwise, it returns 0. Here is the code:

1. Processing integers

int* find(const vector<int> &vec, int value) {
	for (int i = 0; i < vec.size(); i++)
		if (vec[i] == value)
			return &vec[i];
	return 0;
}

1. More types can be processed -- provided that the type defines an equality operator

template <typename elemType>
elemType* find(const vector<elemType> &vec, const elemType &value) {
	for (int i = 0; i < vec.size(); i++)
		if (vec[i] == value)
			return &vec[i];
	return 0;
}

1. Without overloading, the function can handle any type of element in vector and array at the same time -- provided that the equality operator of this type is defined

• First understand how array is passed into the function and how array is returned by the function

int min(int array[24]) {...}

It seems that 1.min() can only accept an array with 24 elements? wrong! We can pass an array of any size to min ().
2. Pass in by value transfer? wrong! When the [array] is passed to or returned by the function, only the [address] of the first element will be passed.

• The following min() function declaration is much more precise

int min(int *array) {...}

Because we only know the first address of array without passing in the size of array, we have to write its own min() function for arrays of different sizes.

• ➀ add a parameter to indicate the size of the array

template <typename elemType>
elemType* find(const elemType *array, int size, const elemType &value); 

• ➁ pass in another address to indicate the end point of array read operation (this value is called * * "pacesetter" * *)

template <typename elemType>
elemType* find(const elemType *array, const elemType *sentinel, const elemType &value); 

After the above operation, array completely disappears from the parameter list.
Access elements through subscripts:

template <typename elemType>
elemType* find(const elemType *array, int size, const elemType &value) {
	if (!array || size < 1)
		return 0;
	for (int i = 0; i < size; i++)
		if (array[i] == value)// You can use the subscript operator on pointers
			return &array[i];
	return 0;
}

Direct access to elements through pointers:

template <typename elemType>
elemType* find(const elemType *array, int size, const elemType &value) {
	if (!array || size < 1)
		return 0;
	for (int i = 0; i < size; i++, array++)// array + +: arithmetic operation of pointer
		if (*array == value)// Retrieve its value with * array
			return &array[i];
	return 0;
}

The following code completely removes the declaration of array from the parameter list, and the second pointer parameter acts as a model:

template <typename elemType>
elemType* find(const elemType *first, const elemType *last, const elemType &value) {
	if (!first || !last)// Note: first is the address of the first element, and last is [the next address of the last element]
		return 0;
	// When first is not equal to last, value is compared with the element referred to by first.
	// If the two are equal, first is returned; otherwise, first is incremented by 1 to point to the next element.
	for (; first != last; first++)
		if (*first == value)
			return first;
	return 0;
}

How do I call find()?

int    ia[8] = {1, 1, 2, 3, 5, 8, 13, 21};
double da[6] = {1.5, 2.0, 2.5, 3.0, 3.5, 4.0};
string sa[4] = {"pooh", "piglet", "eeyore", "tigger"};

int    *pi = find(ia, ia + 8, ia[3]);
double *pd = find(da, da + 6, da[3]);
string *ps = find(sa, sa + 4, sa[3]);

Like array, vector stores all its elements in a piece of continuous memory.
However, vector can be empty, but array is not.

If svec is empty, the following code will generate a runtime error:

find(&svec[0], &svec[svec.size()], search_value);

Therefore, we can make a judgment first:

vector<string> svec;
if (!svec.empty()) { ... }

Generally, we wrap the operation of "taking the address of the first element" as a function:

template <typename elemType>
inline elemType* begin(const vector<elemType> &vec) {
	return vec.empty() ? 0 : &vec[0];
}

The function corresponding to the above begin() function is end(). The end() function will return 0 or the next address of the last element of the vector.
In this way, we have a safe and universal way to apply find() to any vector.

find(begin(svec), end(svec), search_value);

Now, let's extend find() so that it also supports the list categories provided by the standard library.

List is also a container. The elements of the list are linked with each other by a set of pointers: the forward pointer points to the next element; The backward pointer points to the previous element.
The arithmetic operator of pointer is not applicable to list, because the arithmetic operation of pointer must first assume that all elements are stored in continuous space.

We don't need to provide another find() function to support list. In fact, except for the parameter list, the implementation of find() doesn't need to be changed at all.
The solution to this problem is to provide a layer of abstraction on the behavior of the underlying pointer, instead of the original "pointer direct operation" mode of the program. We put the processing of the underlying pointer in this abstraction layer, so that users do not have to face the pointer operation directly.

3.2 understanding making sense of iterators

Iterators and pointers: iterators are a generalization of pointers, providing indirect access to objects. Iterators are for containers and pointer types are for arrays.

How is this abstraction layer implemented? Yes, we need a set of objects, which can provide operators such as built-in operators (+ +, *, = =,! =), and allow us to provide only one implementation code for these operators.
Next, we need to design a set of iterator class es, so that we can use "the same syntax as pointer" to write the program.
If both first and last are iterator s of the list, we can write as follows:

// Both first and last are iterator class object s
while (first != last) {// inequality operator
	cout << *first << ' ';// dereference operator
	++first;// increment operator
}

The above operation seems to take first and last as pointers.
The difference is that the dereference (lifting, *) operator, inequality (inequality,! =) operator and increment (increment, + +) operator are provided by the relevant inline functions in the iterator class (generic pointer class).
Each standard container is provided with an operation function named begin(), which returns an iterator and points to the first element; Another end() function returns an iterator that points to the next position of the last element. Therefore, no matter how the iterator object is defined at this moment, the following operations are performed on the iterator: assign, compare, increment and dereference:

for (iter = svec.begin(); iter != svec.end(); iter++)
	cout << *iter << ' ';

For the iterator object in the above code, some information should be provided in the definition of iterator:
(1) The type of iteration object (a container) used to determine how to access the next element;
(2) The element type referred to by the iterator, which is used to determine the return value of the iterator collection operation.

These are some descriptions and explanations of how the iterator object should be defined.
Let's take a look at the iterator object in the standard library:

vector<string> svec;
vector<string>::iterator iter = svec.begin();

Here iter is defined as an iterator, pointing to a vector whose element type is string. Its initial value points to the first element of svec.:: Indicates that this iterator is a nested [nested] type within the definition of string vector.
For const vector, we use const_iterator for traversal:

const vector<string> cs_vec;
vector<string>::const_iterator iter = cs_vec.begin();

const_ The iterator allows us to read the elements of the vector, but does not allow any write operations.
To obtain the element value through the iterator, use the general pointer collection method:

cout << "string value of element: " << *iter;

Similarly, if you want to call the operation provided by the string element at the bottom through iter, you can use the arrow operator:

cout << "size of element " + *iter + " is " + iter->size();

The following is the re implemented display() function:

template <typename elemType>
void display(const vector<elemType> &vec, ostream &os) {
	vector<elemType>::const_iterator iter = vec.begin();
	vector<elemType>::const_iterator end_it = vec.end();
	for (; iter != end_it; iter++)// If vec is empty, iter is equal to end_it's over
		os << *iter << ' ';
	os << endl;
}

Now re implement find() to support two forms at the same time: ➀ a pair of pointers; ➁ a pair of iterator s pointing to a container. The following codes are applicable to ➀ or ➁:

template <typename iteratorType, typename elemType>
iteratorType find(iteratorType first, iteratorType last, const elemType &value) {
	for (; first != last; first++)
		if (value == *first)
			return first;
	return last;
}

Now you can use the revamped find() to handle array, vector and list:

const int asize = 8;
int ia[asize] = {1, 1, 2, 3, 5, 8, 13, 21};
vector<int> ivec(ia, ia + asize);
list<int> ilist(ia, ia + asize);

int *pia = find(ia, ia + asize, 1024);
if (pia != ia + asize)
	// eureka......
vector<int>::iterator it;
it = find(ivec.begin(), ivec.end(), 1024);
if (it != ivec.end())
	// eureka......
list<int>::iterator iter;
iter = find(ilist.begin(), ilist.end(), 1024);
if (iter != ilist.end())
	// eureka......

If the user wants to give a different meaning to the equality operator, the elasticity of this find() is not enough. How can we increase its elasticity?
Solution 1: pass in a function pointer to replace the original fixed equality operator.
Solution 2: use the so-called function object (this is a special class).

The next goal is to evolve the existing find() version into a generic algorithm.
The standard library provides more than 60 generic algorithms (in fact, nearly 75).
● search algorithm: find (), count(), adjacent_find(),find_if(),count_if(),binary_search(),find_first_of().
● sorting and ordering algorithms: merge(), partial_sort(),partition(),random_shuffle(),reverse(),rotate(),sort().
● copy, deletion and substitution algorithms: copy(), remove(), remove_if(),replace(),replace_if(),swap(),unique().
● relational algorithms: equal(), includes(), mismatch().
● generation and mutation algorithms: fill(), for_each(),generate(),transform().
● numerical algorithm: accmulate(), adjacent_difference(),partial_sum(),inner_product().
● set algorithm:_ union(),set_difference().

3.3 operations common to all containers

The following are the common operations of all container classes (and string classes):
● equality(= =) and inequality(! =) operators, return true or false.
● assignment(=) operator to copy one container to another.
● empty() will return true when the container has no elements, otherwise false.
● size() returns the number of elements currently held in the container.
● clear() deletes all elements.

void comp(vector<int> &v1, vector<int> &v2) {
	if (v1 == v2) return;
	if (v1.empty() || v2.empty()) return;
	vector<int> t;
	t = v1.size() > v2.size() ? v1 : v2;
	t.clear();
}

Each container provides functions of begin(), end(), insert(), erase():
● begin() returns an iterator that points to the first element of the container.
● end() returns an iterator, pointing to the next position of the last element of the container.
● insert() inserts a single or a range of elements into the container.
● erase() deletes a single element in the container or an element in a range.
●push_back(): insert an element at the end;
●pop_back(): delete the last element;
● insert(): insert one or more elements at a certain position;

3.4 using the sequential containers

A group of containers used to maintain the same order and type of elements.
vector and list are the two main sequential containers.
Vector stores elements in a contiguous block of memory. Each element in the vector is stored at a fixed offset from the starting point.

Random access to a vector -- for example, take its 5th element, then its 17th element, and then its 9th element -- is quite efficient.
If you insert an element anywhere instead of the end of the vector, it is inefficient. Because each element at the right end of the insertion position must be copied and moved to the right in turn. Similarly, deleting any element other than the last element of the vector is also inefficient.

List stores its contents in double linked rather than continuous memory, so it can perform forward or backward operations. Each element in the list contains three fields: value, back pointer (pointing to the previous element), and front pointer (pointing to the next element).

It is efficient to insert or delete elements in any position of the list. Because the list itself only needs to set the back pointer and front pointer appropriately.
Random access to the list is inefficient. For example, to access the 5th, 17th and 9th elements in turn, you must traverse all the elements in between.

The third sequential container is deque.

deque behaves quite similar to vector -- it stores elements in continuous memory.
Unlike vector, deque is more efficient for inserting and deleting the front-end elements.
deque is ideal if you want to insert elements at the front of the container and perform an end delete operation.

To use a sequential container, you must first include the relevant header file, which is one of the following three:

#include <vector>
#include <list>
#include <deque>

There are five ways to define sequential container objects:
➊ empty container:

list<string> slist;
vector<int> ivec;

➋ generate containers of a specific size: (each element takes the default value as the initial value.)

list<int> ilist(1024);
vector<string> svec(32);

➌ generate containers of a specific size and specify initial values for each element:

vector<int> ivec(10, -1);
list<string> slist(16, "unassigned");

➍ generate containers through a pair of iterator s:

int ia[8] = {1, 1, 2, 3, 5, 8, 13, 21};
vector<int> fib(ia, ia + 8);

➎ generate a new container according to a container: (copy the elements in the original container as the initial value of the new container.)

list<string> slist;// Empty container
list<string> slist2(slist);// Copy slist to Slit2

Unique functions of list and deque: push_front(),pop_front().
pop_back() and pop_ The two operation functions front () do not return the value of the deleted element.

To read the value of the front most element, use: front()
To read the value of the end element, use: back()

#include <deque>
deque<int> a_line;
int ival;
while (cin >> ival) {
	a_line.push_back(ival);// Insert ival into a_line end
	int curr_value = a_line.front();// Read a_ The value of the topmost element of line
	// ...  Do something
	a_line.pop_front();// Delete a_line frontmost element
}

In addition to the general insert function (), each container also supports four deformations:
➊

iterator insert(iterator position, elemType value)
take value insert position Before. It will return a iterator，Points to the inserted element.
------------------------
The following code will ival insert ilist And maintain its increasing order:
list<int> ilist;
// ...  Fill ilist
list<int>::iterator it = ilist.begin();
while (it != ilist.end) {
	if (*it >= ival) {
		ilist.insert(it, ival);
		break;
	}
	++it;
}
if (it == ilist.end())
	ilist.push_back(ival);

➋

iterator insert(iterator position, int count, elemType value)
stay position Insert before count Elements whose values are the same as value Same————————————————————————————————————————————————
Example:
string sval("Part Two");
list<string> slist;
// ...  Fill slist
list<string>::iterator it = find(slist.begin(), slist.end(), sval);
slist.insert(it, 8, string("dummy"));

➌

void insert(iterator1 position, iterator2 first, iterator2 last)
stay position Insert before[first,last)Each element marked.
------------------------
Example:
int ia1[7] = {1, 1, 2, 3, 5, 55, 89};
int ia2[4] = {8, 13, 21, 34};
list<int> elems(ia1, ia1 + 7);
list<int>::iterator it = find(elems.begin(), elems.end(), 55);
elems.insert(it, ia2, ia2 + 4);

➍

iterator insert(iterator position)
stay position Insert element before. The initial value of an element is the default value of its type.

In addition to the generic delete function erase(), each container also supports two deformations:
➊

iterator erase(iterator posit)
delete posit Refers to the element.
------------------------
For example, delete slist The value of the first element in is str"Elements of:
list<string>::iterator it = find(slist.begin(), slist.end(), str);
slist.erase(it);// The returned iterator object points to the next location of the last element deleted.

➋

iterator erase(iterator first, iterator last)
Delete Division[first,last)Elements in scope.
------------------------
For example, put slist The element value in is str"And "element value is" sval"Delete all elements between the two elements:
list<string>::iterator first = slist.begin(), last = slist.end();
list<string>::iterator it1 = find(first, last, str);
list<string>::iterator it2 = find(first, last, sval);
slist.erase(it1, it2);// The returned iterator object points to the next location of the last element deleted.

list does not support the offset operation of iterator, which is why we can't write: slist erase(it1, it1 + num_tries); The reason why it1 and it2 must be passed into erase().

Here is a complete example:

// inserting into a list
#include <iostream>
#include <list>
#include <vector>
int main () {
  std::list<int> mylist;
  std::list<int>::iterator it;
  // set some initial values:
  for (int i=1; i<=5; ++i) 
  	mylist.push_back(i); // 1 2 3 4 5
  it = mylist.begin();
  ++it;// it points now to number 2
  mylist.insert(it, 10);// 1 10 2 3 4 5
  // "it" still points to number 2
  mylist.insert(it, 2, 20);// 1 10 20 20 2 3 4 5
  --it;// it points now to the second 20
  std::vector<int> myvector(2, 30);
  mylist.insert(it, myvector.begin(), myvector.end());
  // 1 10 20 30 30 20 2 3 4 5
  std::cout << "mylist contains:";
  for (it=mylist.begin(); it!=mylist.end(); ++it)
  	std::cout << ' ' << *it;
  std::cout << '\n';
  return 0;
}

mylist contains: 1 10 20 30 30 20 2 3 4 5

3.5 using the generic algorithms

To use a generic algorithm, you must first include a header file:

#include <algorithm>

We use vector to store the sequence, so as to practice the application of generic algorithm.
If the given value already exists in the sequence, is_elem() returns true, otherwise false.
Here are four possible generic search algorithms:
➊ find() is used to search for a value in an unordered collection. The search scope is marked by iterator [first, last]. If the target is found, find() returns an iterator pointing to the value, otherwise it returns an iterator pointing to last.
➋binary_search() is used to search for ordered collections. If the target is found, return true; Otherwise, false is returned.
binary_search() is more efficient than find(), because find() belongs to linear search and is less efficient than binary search.
➌ count() returns the number of elements with equal values.
➍ search() compares whether a subsequence exists in a container. For example, given the sequence {1, 3, 5, 7, 2, 9}, if you search for the subsequence {5, 7, 2}, search() will return an iterator pointing to the beginning of the subsequence. If the subsequence does not exist, an iterator is returned pointing to the end of the container.

Fibonacci sequence is an increasing sequence, so binary_search() is the best choice:

#include <algorithm>
bool is_elem(vector<int> &vec, int elem) {
	// If elem=34, it means the 9th element of Fibonacci sequence
	// Our vector only stores the first six elements: 1, 1, 2, 3, 5, 8, so the search operation is unsuccessful
	// Calling binary_ Before searching(), you must check whether you need to extend the vector
	return binary_search(vec.begin(), vec.end(), elem);
}

Calling binary_ Before searching (), you must make sure that there are enough elements in the sequence. That is, elem must be within this sequence.
There is a generic algorithm max_element(), passing a pair of iterator s to it will return the maximum value within this range.

#include <algorithm>
extern bool grow_vec(vector<int>&, int);
bool is_elem(vector<int> &vec, int elem) {
	int max_value = max_element(vec.begin(), vec.end());
	if (max_value < elem)
		return grow_vec(vec, elem);
	if (max_value == elem)
		return true;
	return binary_search(vec.begin(), vec.end(), elem);
}

grow_vec() will continue to add the elements of the sequence to the vector one by one until the added value is greater than or equal to elem.
Since our vector elements are arranged incrementally, int max_value = vec.empty()? 0 : vec[vec.size()-1].

binary_search() requires that its objects must be sorted, which is the responsibility of the programmer.
If we are not sure whether we have sorted, we can make a copy of the container first:

vector<int> temp(vec.size());
copy(vec.begin(), vec.end(), temp.begin());
// Then, sort the new container first, and then call binary_search()
sort(temp.begin(), temp.end());
return binary_search(temp.begin(), temp.end(), elem);

3.6 how to design a generic algorithm

Task: there is an integer vector. We must return a new vector containing all values less than 10 in the original vector.
A quick solution that lacks flexibility:

vector<int> less_than(const vector<int> &vec, int less_than_val) {// Less here_ than_ val=10
	vector<int> nvec;
	for (int i = 0; i < vec.size(); i++)
		if (vec[ix] < less_than_val)
			nvec.push_back(vec[i]);
	return nvec;
}

It may be less than 10, greater than 10, or equal to 10, and the number of 10 may also change. Now the function name is filter:

vector<int> filter(const vector<int> &vec, int filter_value, bool (*pred)(int, int)) {
	vector<int> nvec;
	for (int i = 0; i < vec.size(); i++)
		// Call the function referred to in pred. Compare vec[i] and filter_value. 
		if (pred(vec[i], filter_value))
			nvec.push_back(vec[i]);
	return nvec;
}
// Function satisfying function pointer
bool less_than(int v1, int v2) {
	return v1 < v2 ? true : false;
}
bool greater_than(int v1, int v2) {
	return v1 > v2 ? true : false;
}

The following is how to use the filter() function:

vector<int> big_vec;
int value;
// ... Fill big_vec and value
vector<int> lt_10 = filter(big_vec, value, less_than);

Let's find all elements equal to 10: (count_occurs(): do not view any element more than twice)

int count_occurs(const vector<int> &vec, int val) {
	vector<int>::const_iterator iter = vec.begin();
	int occurs_count = 0;
	while ((iter = find(iter, vec.end(), val))!= vec.end()) {
		++occurs_count;
		++iter;// Point to the next element
	}
	return occurs_count;

Function Object

The standard library defines some function objects in advance. The so-called function object is an instance object of a class that overloads the function call operator. In this way, the function object can be used as a general function.

We define the function of object as an independent function. But why?
Mainly for efficiency. We can make the call operator inline to eliminate the extra cost of "calling a function through a function pointer".

The standard library defines a group of function object s in advance, which are divided into:
Arithmetic operation, relational operation and logical operation.
The type in the following list will be replaced with built-in type or class type in actual use:

.	.
6 arithmetic operations	plus< type>，minus< type>，negate< type>，multiplies< type>，divides< type>，modules< type>
6 relational operations	less< type>，less_equal< type>，greater< type>，greater_equal< type>，equal_to< type>，not_equal_to< type>
3 logical operations	logical_and< type>，logical_or< type>，logic_not< type>

To use a pre-defined function object, you must first include the relevant header file:

#include <functional>

By default, sort() is arranged in ascending order. We arrange elements in descending order:

sort(vec.begin(), vec.end(), greater<int>());

Greater < int > () will generate an unnamed class template object and pass it to sort().
binary_search() expects its search objects to be sorted first. In order to search vector correctly, it must be passed to a function object for vector sorting:

binary_search(vec.begin(), vec.end(), elem, greater<int>());

We can do other operations on Fibonacci sequence, such as adding each element to itself, multiplying itself, being added to the corresponding Pell sequence, and so on. One way is to use the generic algorithm transform() with plus < int > and multiplies < int >.
The parameters we must pass to transform() are:
➀ a pair of iterator s, indicating the range of elements to be converted;
➁ an iterator, the element will be applied to the transformation;
➂ an iterator, the position (and the space behind it) is used to store the conversion results;
➃ a function object that represents the conversion operation we want to apply.
The following is how to add Pell sequence to Fibonacci sequence:

transform(fib.begin, fib.end,    //➀
          pell.begin(),          //➁
          fib_plus_pell.begin(), //➂
          plus<int>);            //➃

Function Object Adapter

Function object less < type > expects the outside world to pass in two values. If the first value is less than the second value, it returns true. In this case, each element must be compared with the value specified by the user. Ideally, we need to convert less < type > into an unary operator. This can be done by "binding its second parameter to a user specified value". In this way, less < type > will take out each element and compare it with the value specified by the user one by one.
Can you really do this? yes. The adapter provided by the standard library is born from this.

The function object adapter will modify the function object. The binder adapter will bind the parameters of the function object to a specific value to convert the binary function object into the unary function object. This is exactly what we need.

The standard library provides two binder adapter s:
bind1st will bind the specified value to the first operand; bind2nd binds the specified value to the second operand.

vector<int> filter<const vector<int> &vec, int val, less<int> &lt) {
	vector<int> nvec;
	vector<int>::const_iterator iter = vec.begin();
	while ((iter = find_if(iter, vec.end(), bind2nd(lt, val))) != vec.end()) {
		nvec.push_back(*iter);
		iter++;
	}
	return nvec;
}

bind2nd(less< int>, val); Val will be bound to the second parameter of less < int >. Thus, less < int > will compare each element with val. In the above example, the first operand is iter and the second operand is the fixed value val. true if iter < val.
find_if() is defined as follows:

template <class InputIterator, class UnaryPredicate>
InputIterator find_if(InputIterator first, InputIterator last, UnaryPredicate pred);
●first,last: Input iterators to the initial and final positions of the sequence. The scope of use is[first,last)，It contains first and last Between all elements, including first Points to the element, but does not include last Element pointing to.
●pred: Accepts elements within the scope as parameters and returns a value that can be converted to bool Unary function of the value of type. The value returned indicates whether the element is considered a match in the context of this function. A function cannot modify its parameters. It can be a function pointer or a function object(function object). 
●Return value: point to pred Do not return false Iterator for the first element in the scope of. If pred For all elements false，Then the function returns last. 
The behavior of this function template is equivalent to:
template<class InputIterator, class UnaryPredicate>
InputIterator find_if(InputIterator first, InputIterator last, UnaryPredicate pred) {
  while (first!=last) {
    if (pred(*first)) return first;
    ++first;
  }
  return last;
}

Let's look at a generic function find_ Example of if():

#include <iostream>     // std::cout
#include <algorithm>    // std::find_if
#include <vector>       // std::vector

bool IsOdd (int i) {
  return ((i%2)==1);
}

int main () {
  std::vector<int> myvector;
  myvector.push_back(10);
  myvector.push_back(25);
  myvector.push_back(40);
  myvector.push_back(55);

  std::vector<int>::iterator it = std::find_if (myvector.begin(), myvector.end(), IsOdd);
  std::cout << "The first odd value is " << *it << '\n';
  return 0;
}

The first odd value is 25

Take an example of bind2nd() and bind1st():

#include <iostream>
#include <functional>
#include <algorithm>
using namespace std;
int main () {
  int numbers[] = {10,-20,-30,40,-50};
  int cx;
  cx = count_if(numbers, numbers+5, bind2nd(less<int>(), 0));
  cout << "There are " << cx << " negative elements.\n";
  return 0;
}

There are 3 negative elements.

#include <iostream>
#include <functional>
#include <algorithm>
using namespace std;
int main () {
  int numbers[] = {10,20,30,40,50,10};
  int cx;
  cx = count_if(numbers, numbers+6, bind1st(equal_to<int>(), 10));
  cout << "There are " << cx << " elements that are equal to 10.\n";
  return 0;
}

There are 2 elements that are equal to 10.

How to eliminate the dependency between filter() and vector element type, and between filter() and vector container type, so as to make filter() more generic?

template <typename InputIterator, typename OutputInterator, typename ElemType, typename Comp>
OutputIterator filter(InputIterator first, InputIterator last, OutputIterator at, const ElemType &val, Comp pred) {
	while ((first = find_if(first, last, bind2nd(pred, val))) != last) {
		cout << "found value: " << *first << endl;
		*at++ = *first++;
	}
	return at;
}

Now test the use of the above filter() on array and vector:

int main() {
	const int value = 8;
	const int elem_size = 8;
	int ia[elem_size] = {12, 8, 43, 0, 6, 21, 3, 7};
	vector<int> ivec(ia, ia + elem_size);
	// The following container is used to store the filtering results
	int ia2[elem_size];
	vector<int> ivec2(elem_size);
	
	cout << "filtering integer array for values less than 8\n";
	filter(ia, ia + elem_size, ia2, value, less<int>());

	cout << "filtering integer vector for values greater than 8\n";
	filter(ivec.begin(), ivec.end(), ivec2.begin(), value, greater<int>());
}

filtering integer array for values less than 8
found value: 0
found value: 6
found value: 3
found value: 7
filtering integer vector for values greater than 8
found value: 12
found value: 43
found value: 21

Another type of adapter is the so-called negator, which reverses the true or false value of function object.
not1 can reverse the true or false value of an unary function object, and not2 can reverse the true or false value of a binary function object.
For example, to find all elements greater than or equal to 10, you can reverse the operation result of function object less < int > ():

while ((iter = find_if(iter, vec.end(), not1(bind2nd(less<int>(), 10)))) != vec.end())

We also have other solutions, such as the following non template version:

vector<int> sub_vec(const vector<int> &vec, int val) {
	vector<int> local_vec(vec);// Operate on replicas
	sort(local_vec.begin(), local_vec.end());// Sort first
	vector<int>::iterator it = find_if(local_vec.begin(), local_vec.end(),
									   bind2nd(greater<int>(), val));
	local_vec.erase(it, local_vec.end());// Delete all elements from position to end
	return local_vec;
}

3.7 using a map

#include <map>
#include <string>
map<string, int> words;// map with string key and int value
words["vermeer"] = 1;// The easiest way to enter key/value

The following for loop prints all words and their occurrences:

map<string, int>::iterator it = words.begin();
for(; it != words.end(); ++it)
	cout << "key: " << it->first
		 << "value: " << it->second <<endl;

The map object has a member named first, which corresponds to the key;
Another member named second corresponds to value.

There are three ways to query whether a key exists in a map:
➊ use key as index

int count = 0;
if (!(count = words["vermeer"]))
	// vermeer does not exist in the word map

Disadvantages: if the key does not exist in the map, the key will be automatically added to the map, and the value will be set to the default value of its type.
➋ use the find() function of map

int count = 0;
map<string, int>::iterator it;
it = words.find("vermeer");
if (it != words.end())
	count = it->second;

➌ use the count() function of map (it returns the number of a specific item in the map)

int count = 0;
string search_word("vermeer");
if (words.count(search_word))// ok, it exists
	count = words[search_word];

If we need to store multiple copies of the same key value, we must use multimap.

3.8 using a set

#include<set>
#include<string>
set<string> word_exclusion;
string tword;
while (cin >> tword) {
	if (word_exclusion.count(tword))
		continue;
	words[tword]++;
}

For any key value, set can only store one copy. If you want to store multiple copies of the same key value, you must use multiset.
By default, set elements are arranged according to the default less than operator of their type, for example:

int ia[10] = {1, 3, 5, 8, 5, 3, 1, 5, 8, 1};
vector<int> vec(ia, ia + 10);
set<int> iset(vec.begin(), vec.end());
// The element of iset will be {1, 3, 5, 8}

Insert a single element:

iset.insert(ival);

Insert elements of a range:

iset.insert(vec.begin(), vec.end());

Iterate on set:

set<int>::iterator it = iset.begin();
for (; it != iset.end(); ++it)
	cout << *it << ' ';

There are many set related algorithms in generic algorithms: set_intersection(),set_union(),set_difference(),set_symmetric_difference().

3.9 how to use iterator inserters

The previous implementation of filter() assigns each eligible element in the source end (container) to the destination end (container):

while((first = find_if(first, last, bind2nd(pred, val))) != last)
	*at++ = *first++;

In this form, the container on the destination side must be large enough to store each element assigned. It is the programmer's responsibility whether at points to a valid container location after each increment of at.
"Ensure that the space of the end container pointed by at is large enough". The size of the end container may be too large or too small, which is a problem.
For example, make the size of the destination container equal to the size of the source container, but the destination container is too large.

All generic algorithms that "copy elements", such as copy (), copy_backwards(),remove_copy(),replace_copy(),unique_copy() and so on are very similar to the implementation of filter(). Each algorithm accepts an iterator to mark the starting position of replication. Every element copied will be assigned, and the iterator will be incremented to the next position.

The standard library provides three insertion adapter s, which allow us to avoid using the assignment operator of the container:
●back_ The inserter () will push with the container_ The back() function replaces the assignment operator. For vector, this is a more suitable inserter. Incoming back_ The parameter of the inserter should be the container itself:

vector<int> result_vec;
unique_copy(ivec.begin(), ivec.end(), back_inserter(result_vec));

● the inserter will replace the assignment operator with the insert() function of the container, which accepts two parameters: a container and an iterator, pointing to the starting point of the insertion operation in the container.

vector<string> svec_res;
unique_copy(svec.begin(), svec.end(), inserter(svec_res, svec_res.end()));

●front_ The inserter () will push the container_ The front () function replaces assignment. This inserter is only applicable to list and deque.

list<int> ilist_clone;
copy(ilist.begin(), ilist.end(), front_inserter(ilist_clone));

The following re implements the above example:

int main() {
	const int value = 8;
	const int elem_size = 8;
	int ia[elem_size] = {12, 8, 43, 0, 6, 21, 3, 7};
	vector<int> ivec(ia, ia + elem_size);
	int ia2[elem_size];// Insert operation is not supported for built-in arrays
	vector<int> ivec2;
	cout << "filtering integer array for values less than 8\n";
	filter(ia, ia + elem_size, ia2, value, less<int>());
	cout << "filtering integer vector for values greater than 8\n";
	filter(ivec.begin(), ivec.end(),
	       back_inserter(ivec2), value, greater<int>());
}

filter() will assign each element to the destination vector in turn -- in this case, ivec2. Since the size of ivec2 is not set in this example, the assignment operation will produce a runtime error. However, once ivec2 is passed to the inserter adapter, the assignment of the element is replaced by the insertion operation. If we only insert elements at the end of the vector, the efficiency will be higher, so we choose back_inserter.

3.10 using the iostream iterators

New task: read a string of elements from the standard input device, store them in the vector, sort them, and finally write these strings back to the standard output device. The general solution is as follows:

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
	string word;
	vector<string> text;
	while (cin >> word)
		text.push_back(word);
	sort(text.begin(), text.end());
	for (i = 0; i < text.size(); ++i)
		cout << text[i] << ' ';
}

The standard library defines the iostream iterator class for input and output, which is called istream_iterator and ostream_iterator, which supports single type element reading and writing respectively.
First include header file:

#include <iterator>

Using istream_ The iterator reads the string from the standard input device. We need a pair of iterators: first and last to mark the element range.
first iterator:

istream_iterator<string> is(cin);

It defines is as an istream bound to a standard input device_ iterator.
last iterator:

istream_iterator<string> eof;

The last iterator indicates the next position of the last element to be read. For standard input devices, end of file means last. Just define istream_ When iterator does not specify an istream object for it, it represents end of file.

It can be used as follows: (back_inserter is selected because I don't know how much space to reserve for vector)

copy(is, eof, back_inserter(text));

We also need an ostream_iterator, which indicates the output position of the string element.

ostream_iterator<string> os(cout, " ");

The above is to define the os as an ostream bound to the standard output device_ iterator. The second parameter is the delimiter string constant.

It can be used as follows:

copy(text.begin(), text.end(), os);

copy() will write each element stored in text one by one to the ostream represented by os. Each element is separated by a space.

The following is the complete code:

#include <iostream>
#include <iterator>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
int main() {
	istream_iterator<string> is(cin);
	istream_iterator<string> eof;
	vector<string> text;
	copy(is, eof, back_inserter(text);
	sort(text.begin(), text.end());
	ostream_iterator<string> os(cout, " ");
	copy(text.begin(), text.end(), os);
}

If it is a file read-write, just set istream_ The iterator is bound to the ifstream object and the ostream_ The iterator can be bound to ofstream object:

#include <iostream>
#include <fstream>
#include <iterator>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
int main() {
	ifstream in_file("input_file.txt");
	ofstream out_file("output_file.txt");
	if (!in_file || !out_file) {
		cerr << "!! unable to open the necessary files.\n";
		return -1;
	}
	istream_iterator<string> is(in_file);
	istream_iterator<string> eof;
	vector<string> text;
	copy(is, eof, back_inserter(text));
	sort(text.begin(), text.end());
	ostream_iterator<string> os(out_file, " ");
	copy(text.begin(), text.end(), os);
}