Sorting has always been a common algorithm in the data structure, the sorting algorithm provided by STL is very rich, how to use effective use is worth discussion. I didn't find the translation of Terms 31 on the Internet, so I translated it myself. --Winter
How to sort? There are several ways to make me a few ways.
Once the programmer needs to be sorted by the container element, the Sort algorithm will appear immediately in his mind (maybe some programmers will think of QSort, but after reading the terms 46, they will give up the idea of using QSORT, turn the Sort Algorithm) .
Sort is a very good algorithm, but when you don't really need it, it is actually a waste. Sometimes you don't need a complete sort (referred to as full sorting). For example, you have a VECTOR container containing widget objects (Widget means "small pendant"), and you want to give you the best customers in 20 widgets, then you need to do it. These 20 quality widget elements, the remaining do not need to care about their order. At this time, you need some sort (relative to full sorting), just in the algorithm, there is a veritable partial sort function function: Partial_Sort:
The quality of BOOL QualityCompare (Const Widget & lh, Const Widget & rhs) {// LHS is not more than RHS's quality difference, otherwise returns false} ... partial_sort (widgets.begin (), // The best quality 20 element widgets. Begin () 20, // Sequential Put widgets.end (), QualityCompare) in widgets container; ... // Use widgets ...
By calling partial_sort, 20 elements starting in the container are the best 20 widgets you need, and arrange them in order, the quality row is widgets [0], followed by widgets [1], push it. This way you can give your best customers to you the best customers. The second widget can be given to the next customer, it is convenient, it is more convenient to be behind.
If you just want to give this 20 quality Widget gift to you the best 20 customers, don't need to give them one by one, Partial_sort is here to look small. Because here, you only need to find these 20 elements without need to sort them itself. At this time, you need not partial_sort, but nth_element.
The nth_element sorting algorithm is just sorted a range, and the correct element is placed on the NTH_Element sequence, which is the nth_element, which is the nth_element. Is the same element. When the NTH_ELEMENT function runs, the elements should not appear in the position N after the full sorting, and the elements in front of the position N do not appear behind the N. It sounds some puzzle, mainly I have to use my language to describe the functionality of NTH_EEMENT. Don't worry, I will explain why, now let us see how Nth_Element is how to make the best 20 widget gifts in the vector container: nth_element (widgets.begin (), // Place the best quality 20 elements in widgets.begin () 20, // widgets container front, widgets.end (), // but does not care about these 20 elements QualityCompare; // The order inside itself
You can see that call nth_element functions and call Partial_Sort functions are inherently different, the only difference is that Partial_Sort is arranged in the top 20 elements, while nth_element does not have their internal order. Both algorithms have achieved the same function: 20 elements of quality in the VECTOR container in quality:
This caused an important issue: If the element is the same element, how will the sorting algorithm handle? The quality of 12 elements is 1 (best level), 15 elements of the quality level of 2 (quality times), if you want to choose 20 the best Widget, first select 12 quality 1 elements Then, then 8 elements of 8 mass 2 are selected from 15. How to select 8 in 15 in 15, which is based on? In other words, when multiple elements have the same comparison value, how does the sorting algorithm determine who?
For Partial_Sort and NTH_Element algorithms, you can't control them, how do they want to row for more than the same elements (see Terms 19, understand the definition of two values). In our example, face the elements that need to be 2-level 2 to TOP 20, they will be arbitrarily selected. This also has its truth: if you ask 20 quality widgets, some Widget's quality is the same, when you get 20 elements at least less than the remaining quality, this has reached your request, you I can't complain about anything.
If you are all sort, you can get more control. Some sort algorithms are "stable", in a "stable" sort algorithm, if the two elements have the same value, their relative positions will remain unchanged after sorting. For example, if Widget A is before Widget B, and there is the same quality level, the "stable" sorting algorithm ensures that Widget A is still before Widget B after sorting. Instead of "stability" sorting algorithm can not guarantee this.
Partial_sort and nth_element are not a "stable" sort algorithm, the real "stable" sorting algorithm is Stable_Sort, you know that it is "stable" from the name. If you need to guarantee the relative position of the same element while sorting, you'd better use Stable_Sort, not providing the corresponding "stable" version for the Partial_Sort and NTH_Element algorithms in STL. Speaking of nth_element, the name is really blamed, but the function is a lot, in addition to letting you find a Top N element that is unrelated, it also finds a range of mediatives, or finds the value of a certain percentage point.
Vector
// The following code is used to get the iterator goalposition = begin widgets.size () / 2; // The element to be found should // The center of the vector. Nth_Element (Begin, GoalPosition, End, // Locate Medium QualityCompare); // ... // GoalPosition Now points to medium-value elements // The following code is used to get the quality of the elements of 75% Vector
... // GoalPosition Now points to 75% of the elements of the quality.
When you need to put a collection from disorders into order, you can choose sort, stable_sort, or partial_sort, when you only need to get top n or elements in a particular location, you can use nth_element. Maybe sometimes your needs are less than nth_element, for example: You don't need to get the top 20 widgets with the best quality, but only need to identify Widgets with a quality level of 1 or level 2. Of course, you can sort the entire vector in accordance with the quality level of Widget, then find the element of the first quality level below the level 2. The problem is that the whole sort is too resource, and most of the work is useless. In this case, it is best to choose the partition algorithm. Partition just gives you a range, putting the elements that match the specific condition in this section. For example, the element of Widget is equally equal to the widget of the level 2 is placed on the front end of the Widget container, and we can define a function for identifying the Widget quality level:
Bool HasacceptableQuality (const widget & w) {// If W is equal to or better than 2, return true, otherwise return false}
Then paste this judgment function to the partion algorithm: vector
In this way, all elements between iterator widgets.begin () and iterator Goodend are elements that meet demand: their quality grade is better or equal to 2. The quality level of the elements between goodend to widgets.end () will be lower than the quality level 2. If you care about the relative position of the same element of the quality level, you can choose the Stable_Partition algorithm to replace Partition.
It is necessary to pay attention to the sort, stable_sort, partial_sort, and nth_element algorithms need to be parameters with random iteratory (random accessiterators), so these algorithms can only be used for VECTOR, STRING, Deque, and Array containers, for standard associated containers Map, SET, MULTMAP, MULTSET, etc., these algorithms are necessary, these containers itself compare function makes all elements in the container to be arranged in an orderly manner. For container LIST, it seems that these sorting algorithms can be used, which is not available (the type of Iterator is not a random iterator), but it can be used to bring the sort function Sort with the list (interesting is List :: The Sort function is the same as a "stable" sort function). If you want to use partial_sort or nth_element to a LIST container, you can only use it indirectly. One optional method is to copy the elements in the list to the container with a random iterator, and then use these algorithms; the other is to generate a container containing list :: Iterator, direct List :: Iterator is sorted, then you will receive the element referred to by List :: Iterator; the third method, by means of an ordered container containing Iterator, then repeatedly connects the elements in the list to the location you want to link. See it, you can choose how much it is. Partition and Stable_Partition functions are different from sort, stable_sort, partial_sort, nth_element, requirement is not so strict, and the input parameters only need to be bidirectional iterator. So you can use the Partition and Stable_Partition algorithm for all standard sequence containers.
Let us sumize your sorting operation:
To make full sorting for Vector, String, Deque, or Array container, you can choose sort or stable_sort; if you only need to get Top N elements in Vector, String, Deque, or Array container, part sorting partial_sort is the first choice. For Vector, String, Deque, or Array container, you need to find the elements of the northern location or you need to get Top N and does not have the internal order in top n, nth_element is ideal; if you need to be selected from a standard sequence container or Array Separates a certain condition or does not satisfy a certain condition, you'd better use partition or stable_partition; if you use the list container, you can use the Partition and Stable_Partition algorithm directly, you can use List :: Sort instead of Sort and Stable_sort sort. If you need to get the sorting effect of Partial_Sort or Nth_Element, you have to use it indirectly. As mentioned above, there are several ways to choose.
In addition, you can use standard related containers to ensure that all elements in the container are in order during operation. You can also consider non-standard STL container priority_queue, which can also ensure that its elements are all in all operations (Priority_Queue belongs to a part of the STL, but according to "STL" definition, you need STL containers to support iterators, Priority_Queue does not support iterators, so it cannot be referred to as a standard STL container).
At this time you may ask: "How is performance?" Very good question. Generalized speaking, the more work, the longer the time, the longer the time, the "stable" sequencing algorithm is more than the "non-stable" sexual order algorithm. We can sort the sorting algorithms discussed in this article in accordance with its resource (time and space), and the less resources are consumed in front: 1. Partition 2. Stable_Partition 3. Nth_Element 4. Partial_Sort 5. Sort 6. Stable_sort
The basis for choosing these algorithms is your needs instead of their performance. If you can choose an algorithm to meet your needs (if you use some sorting instead of full sorting), you will not only express your intentions, but also use STL efficiently. More STL Articles to see STL Learning Website
Related article: Effective STL Chinese version (Daquan) Effective STL English electronic version Download Terfeter 8: Do not put auto_ptr into the container
