Effective STL: Item 44: Priority uses members of the same name with the generic algorithm

Item 44: Priority uses member functions with the generic algorithm

Some containers have a member function that is the same as the STL generic algorithm. Associated containers provide count (), find (), limited (), and equal_range (), and List provides remove (), remove_if (), unique (), sort (), merge (), and Reverse (). There are two reasons for this. First, the member function is faster. Second, they combine better with the container (especially related containers). That's because the generic algorithm and member functions of the same name are usually not the same thing in the same way.

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

Set S; // Create Set, PUT

... // 1,000,000 VALUES

// INTO IT

Set :: Iterator i = S.find (727); // USE FIND MEMBER

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

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

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

The Find () runs log for the member function, so regardless of whether 727 exists in the set, set :: find () simply performs no more than 40 comparisons to find it, while only 20 times. In contrast, the Find () of the generic algorithm runs linear times, so if the 727 is not in the SET, it needs to perform 1,000,000 comparisons. Even if 727 is in the SET, it is also necessary to perform 500,000 comparisons to locate it. The efficiency score is as follows:

Member's Find (): About 40 (worst) to approximately 20 (average)

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

Like the golf game, the score is low. As you can see, the results of the game have no controversy.

I have to express little caution for the number of comparisons required for member functions because it depends on the implementation of the associated container. Most of the realization is the use of red-black trees, one of the balanced trees, and the imbalance may reach 2 (That May Beal Of TWO). In such an implementation, the SET of one million elements is searched, and the maximum number of comparisons required is 38 times. But for most search situations, no more than 22 times. A complete balance tree is not required to exceed 21 comparisons, but in practice, the efficiency of complete balanced trees is not as good as red and black. This is why most STL implementations use red black trees.

The efficiency is not the only difference between the Find () and generic algorithm Find () of the member function. As explained by Item 19, the STL generic algorithm determines whether the two objects are the same, and Equality is Equality (WQ Note: Logic et al, uses Operator ==), and the associated container detects Equivalence (WQ Note: Mathematical Square, Two Elements Are Equal if Neither is Less Than The Other. Therefore, the generic algorithm Find () search 727 is logical, while the Find () of the member function is mathematical. The difference between logic equal and mathematical equivalents can result in successful search and unsuccessful search. For example, Item 19 demonstrates the use of a generic algorithm Find () to search for the Find () search for the member function! Therefore, if you manipulate the associated container, you should prioritize Find (), count (), Lower_Bound (), a function of the same name, not the generic algorithm of the same name, because these member function versions provide and other member functions Consistent behavior. The generic algorithm cannot provide such consistent behavior due to the difference between the logic equal and mathematical equalization. This difference is particularly obvious to MAP and Multimap because they accommodate the PAIR object, while their member functions only care about the Key section of the Pair object. Therefore, the member function count () only counts the number of PAIR objects that match the key value ("match", nature is naturally the meaning of the detection, etc.); the Value part of the Pair is ignored. The same is true for Find (), loWer_bound (), Upper_Bound (), and Equal_Range (). If you use a generic algorithm Find (), then it looks based on (a) logically equal and (b) all components of PAIR; the extensive algorithm's Find (), Lower_Bound () or the like is the same. To make the generic algorithm only focus on the Key section of the Pair, you must jump out of the limitations described in Item 23 (which introduces the method for testing the logic equivalent for mathematics).

On the other hand, if you really care, you can decide to use the skills in Item 23 to collaborate the logarithmic time search algorithm in Item 34. This is just a small price relative to performance. Furthermore, if you really care, you should consider the non-standard Hash container (described in Item 25), just, you will again face the difference between logic equal and mathematical.

For standard related containers, select member functions instead of generic algorithms, there are several benefits. First, you get the logarithmic time rather than the performance of linear times. Second, you judge that the two elements "the same" use is mathematical equal, which is the default definition of the associated container. Third, when manipulating MAP and MultiMap, you automatically processes the Key value rather than (Key, Value). These three gave a good reason to prioritize the members of the member.

Let us go to the member function of the List of the same name as the generic algorithm. The story here is almost about efficiency. Each generic algorithm is made by List (), remove_if (), unique (), sort (), merge (), and reverse ()) must copy objects, and the special version of List is not copied Anything; they just simply manipulate the pointers of the nodes connecting the List. The generic algorithm and the algorithm complexity of the member function are 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.

Keep in keeping in this very important: the behavior of the member function version of the List and the generic algorithm version of the same name, the behavior is often different. Such as Item 32, REMOVE (), remove_if (), and unique (), must be told to call the ERASE () function (if you really want to clear the object from the container); but List Remove (), remove_if () and unique () member functions really remove the elements, do not need to be called ERASE (). An important difference between the Sort () member function of generic algorithm sort () and List is: the former cannot be used for List. As a simple two-way Iterator, List's Iterator cannot pass to the generic algorithm sort (). There is also a huge difference between the Merge () generic algorithm and the list of List () members. This generic algorithm is not allowed to modify the source range, but List :: merge () can also modify its host list.

So, you understand. You should use the member function when you face the STL generic algorithm and the container member function. It is almost certainly more efficient, and it looks better with the usual behavior of the container.