The sequence containers can be sorted, and once you have done this you can use methods to search for items, to merge containers, or to get the difference between the containers. The sort function will order the items in a range according to the < operator or a predicate that you provide. If there are items that are equal in the range, then the order of these items after the sort is not guaranteed; if this order is important, you should call the stable_sort function instead. If you want to preserve the input range and copy the sorted items into another range, you use the confusingly named partial_sort_copy function. This is not a partial sort. This function is passed iterators to the input range and iterators for the output range, so you have to ensure that output range has a suitable capacity.
You can check if a range is sorted by calling the is_sorted function, and this will iterate through all items and return false if it finds an item that is not in sorted order, in which case you can locate the first item that is out of sort order by calling the is_sorted_until function.
As the name suggests, the partial_sort function does not place every item in its exact order relative to every other item. Instead, it will create two groups, or partitions, where the first partition will have the smallest items (not necessarily in any order) and the other partition will have the biggest items. You are guaranteed that the smallest items are in the first partition. To call this function you pass three iterators, two of which are the range to sort, and the third is a position somewhere between the other two that indicates the boundary before which are the smallest values.
vector<int> vec{45,23,67,6,29,44,90,3,64,18};
auto middle = vec.begin() + 5;
partial_sort(vec.begin(), middle, vec.end());
cout << "smallest items" << endl;
for_each(vec.begin(), middle, [](int i) {cout << i << " "; });
cout << endl; // 3 6 18 23 29
cout << "biggest items" << endl;
for_each(middle, vec.end(), [](int i) {cout << i << " "; });
cout << endl; // 67 90 45 64 44
In this example there is a vector of ten items, so we define the middle iterator as five items from the beginning (this is just a choice, it could be some other value depending on how many items you want to obtain). In this example, you can see that the five smallest items have been sorted to the first half and the last half have the biggest items.
The oddly named nth_element function acts like partial_sort. You provide an iterator to the nth element and the function ensures that first n items in the range are the smallest. The nth_element function is faster than partial_sort, and, although you are guaranteed that the items before the nth element are less than or equal to the nth element, there are no other guarantees of the sort order within the partitions.
The partial_sort and nth_element functions are versions of partitioned sort functions. The partition function is a more generic version. You pass this function a range and a predicate that determines in which of the two partitions an item will be placed. The items that meet the predicate will be put in the first partition of the range, and the other items will be placed in the range following the first partition. The first item of the second partition is called the partition point and it is returned from the partition function, but you can calculate it later by passing iterators to the partitioned range and the predicate to the partition_point function. The partition_copy function will also partition values, but it will leave the original range untouched and put the values in a range that has been already allocated. These partition functions do not guarantee the order of equivalent items, and if this order is important then you should call the stable_partitian function. Finally, you can determine if a container is partitioned by calling the is_partitioned function.
The shuffle function will rearrange the items in a container into a random order. This function needs a uniform random number generator from the <random> library. For example, the following will fill a container with ten integers and then place them in a random order:
vector<int> vec;
for (int i = 0; i < 10; ++i) vec.push_back(i);
random_device rd;
shuffle(vec.begin(), vec.end(), rd);
A heap is a partially sorted sequence in which the first item is always the largest, and items are added and removed from the heap in logarithmic time. Heaps are based upon sequence containers and, oddly, rather than the Standard Library providing an adapter class, you have to use function calls on an existing container. To create a heap from an existing container, you pass the range iterators to the make_heap function, which will order the container as a heap.
You can then add new items to the container using its push_back method, but each time you do this you have to call push_heap to re-order the heap. Similarly, to get an item from the heap you call the front method on the container and then remove the item by calling the pop_heap function, which ensures that the heap is kept ordered. You can test to see if a container is arranged as a heap by calling is_heap, and if the container is not entirely arranged as a heap you can get an iterator to the first item that does not satisfy the heap criteria by calling is_heap_until. Finally, you can sort a heap into a sorted sequence with sort_heap.
Once you have sorted a container, there are functions that you can call to get information about the sequence. The lower_bound and upper_bound methods have already been described for containers, and the functions behave in the same way: lower_bound returns the position of the first element that has a value greater than or equal to the value provided and upper_bound returns the position of the next item that is greater than the value provided. The includes function tests to see if one sorted range contains the items in a second sorted range.
The functions beginning with set_ will combine two sorted sequences into a third, container. The set_difference function will copy the items that are in the first sequence but not in the second sequence. This is not a symmetric action because it does not include the items that are in the second sequence but not in the first. If you want a symmetric difference, then you should call the set_symmetric_difference function. The set_intersection will copy the items that are in both sequences. The set_union function will combine the two sequences. There is another function that will combine two sequences, which is the merge function. The difference between these two functions is that with the set_union function, if an item is in both of the sequences, there will only be one copy put in the results container, whereas with merge there will be two copies in the results container.
If a range is sorted, then you can call the equal_range function to obtain the range of elements that are equivalent to a value passed to the function or a predicate. This function returns a pair of iterators that represent the range of values in the container.
The final method that needs a sorted container is binary_search. This function is used to test if a value is in the container. The function is passed iterators indicating the range to test and a value, and it will return true if there is an item in the range equal to that value (you can provide a predicate to perform this equality test).