Effective STL Terms 44

Terms 44: Try to use member functions to replace the same name algorithm

Some containers have a member function that is the same as the STL algorithm. The associated container provides COUNT, FIND, LOWER_BOUND, UPPER_BOUND, and Equal_Range, and List provides Remove, Remove_iF, Unique, Sort, Merge, and Reverse. In most cases, you should use the member function instead of the algorithm. There are two reasons for this. First, the member function is faster. Second, they are better than algorithms (especially related containers). That's because the algorithm and member functions of the same name are usually not the same.

We start with the experiment of the associated container. If there is a set , it stores a million elements, and you want to find the first position of the element 727 (if present). There are two most natural ways to perform search:

Set S; // Establish set, put 1,000,000 data

... // Go in

Set :: Iterator i = S.find (727); // Using the Find member function

IF (i! = s.end ()) ...

Set :: Iterator i = Find (s.begin (), s.end (), 727); // Using a Find Algorithm

IF (i! = s.end ()) ...

The Find member function is spent on the time, so regardless of whether 727 exists in this set, set :: Find simply performs no more than 40 comparisons to find it, and generally only take about 20 times. Instead, the Find algorithm runs linear time, so if 727 is not in this set, it needs to perform 1,000,000 comparisons. Even if 727 is in this SET, it is also an average of 500,000 comparisons to find it. The efficiency score is as follows:

Find member: approximately 40 (worst) to approximately 20 (average)

Find algorithm: 1,000,000 (worst case) to 500,000 (average)

Like the golf game, the score is low. As you can see, this game is nothing to say.

I have to express little caution for the number of comparisons required for the Find member function, as it depends on the implementation of the associated container. Most of the realization is a kind of red-haircut-balance tree that may reach 2. In such an implementation, the number of SETs required for one million elements is 38 times. However, for most search situations, it only needs no more than 22 times. A complete balance tree is not required to exceed 21 comparisons, but in practice, the full balance tree is not as red and black. This is why most STL implementations use red black trees.

The efficiency is not the only difference between the Find member function and the Find algorithm. As explained in Terms 19, the STL algorithm determines whether the two objects are the same. It is to check whether they are equal, while the associated container is used to test their "identity" in equivalence (Equivalence). Therefore, the Find algorithm search 727 is equal, and the Find member function is equivalent. The difference between equal and equivalents may result in successful search and unsuccessful search. For example, the Terms 19 demonstrates that the Find algorithm is used in the associated container search failed to search for success! Therefore, if you use an associated container, you should try to use Find, Count, Lower_Bound, etc. in the form of member functions, rather than the generic algorithm of the same name, because these member function versions provide behavior that is consistent with other member functions. Due to equal and equivalents, generic algorithms cannot provide such consistency. This difference is particularly obvious to Map and Multimap because they are contained in pair object, while their member functions only care about the Key part of the object. Therefore, the count member function only counts the number of object pairs of the key value (so-called "match", naturally the detection equivalent); the Value part of the object is ignored. The same is true for members function find, lower_bound, upper_bound, and equal_range. But if you use a count algorithm, it looks for all components of (a) equal and (b) object pairs; generic algorithm Find, Lower_Bound, etc. To make the generic algorithm only focus on the Key section of the object pair, you must jump out of the limitations described in the terms 23 (there are methods of using equal test replacement equivalents).

On the other hand, if you really care about efficiency, you can use the skills in Terms 23, the logarithmic time search algorithm in the joint clause 34. This is just a small price relative to performance. Furthermore, if you really care, you should consider non-standard Hash containers (described in terms 25), just, you will once again face the difference between equal and equivalent.

For standard related containers, select member functions rather than the algorithms of the same name. First, you get the logarithmic time rather than the performance of linear times. Second, you judge that the two elements "the same" is equivalent, which is the default definition of the associated container. Third, when manipulating MAP and MultiMap, you can automatically process the key value rather than (key, value). These three gave the tinch, which prioritize the perfect use of the members.

Let us go to the List's member function as the algorithm. The story here is almost about efficiency. Each algorithm that is specialized by List (Remove, Remove_iF, Unique, Sort, Merge, and Reverse) must copy objects, and the special version of List has no copy; they just simply manipulate the pointer to the node of the List. The algorithm complexity of the algorithm and the member function is the same, but if the manipulation of the pointer is smaller than the cost of the copy object, the version of the List should provide better performance.

This is important to remember this: The behavior of the List member function and their algorithm's behavior are often different. As explained in Terms 32, if you really want to clear the object from the container, then call the REMOVE, REMOVE_IF, and UNIQUE algorithms, you must call the ERASE function; but the List's REMOVE, REMOVE_IF, and UNIQUE member functions really remove the element. There is no need to call ERAS later later.

An important difference between the Sort Algorithm and the Sort member function between the List is that the former cannot be used for List. As a simple two-way iterator, the iterator of the List cannot be passed to the Sort Algorithm. There is also a huge difference between the MERGE algorithm and the List's MERGE member function. This algorithm is restricted to modify the source range, but List :: Merge always modifies its host List. So, you understand. When you are facing a STL algorithm and the same name, you should try to use the member function as much as possible. It is almost certain that it is more efficient, and it looks better with the usual behavior of the container.