C++语法基础--泛型算法（generic algorithm)--对容器排序的算法sort(),stable_sort(),unique()

快来打我* 2022-01-09 21:11 166阅读 0赞

**1.sort  
Sorts the elements in the range \[first,last) into ascending order.  
The elements are compared using operator< for the first version, and comp for the second.  
Equivalent elements are not guaranteed to keep their original relative order**

**原型：**

**default：  
template <class RandomAccessIterator>  
void sort (RandomAccessIterator first, RandomAccessIterator last);  
custom：  
template <class RandomAccessIterator, class Compare>  
void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);  
解析：  
first, last：  
Random-access iterators to the initial and final positions of the sequence to be sorted.  
comp ：  
Binary function that accepts two elements in the range as arguments, and returns a value convertible to bool.**

**Example:**

**int main ()  
\{  
int myints\[\] = \{11,2,10,9,3,7,13,6\};  
vector<int> myvector (myints, myints+8);  
  
  
// using default comparison (operator <):  
sort (myvector.begin(), myvector.begin()+4);  //(2,9,10,11),3,7,13,6   
  
// using function as comp  
sort (myvector.begin()+4, myvector.end(), myfunction); // 2,9,10,11,(3,6,7,13)  
  
  
 return 0;  
\}  
  
  
  
  
  
  
2.stable\_sort  
同sort(),但stable\_sort是稳定的算法，即排序后容器内相等元素相对位置不变  
（例：假设排序前相等元素a1在a2前面，排序后a1还是在a2前面）  
  
  
3.unique  
Removes all but the first element from every consecutive(连续的) group of equivalent elements in the range \[first,last).  
The function uses operator== to compare the pairs of elements (or pred, in version (2)).**

**原型：**

**equality ：  
template <class ForwardIterator>  
ForwardIterator unique (ForwardIterator first, ForwardIterator last);  
predicate ：  
template <class ForwardIterator, class BinaryPredicate>  
ForwardIterator unique (ForwardIterator first, ForwardIterator last,  
BinaryPredicate pred);  
解析：  
 first, last：  
Forward iterators to the initial and final positions of the sequence of move-assignable elements.  
pred ：  
Binary function that accepts two elements in the range as argument, and returns a value convertible to bool.  
该算法等效于：  
 template <class ForwardIterator>  
ForwardIterator unique (ForwardIterator first, ForwardIterator last)  
\{  
if (first==last) return last;  
  
  
ForwardIterator result = first;  
while (++first != last)  
\{  
if (!(\*result == \*first)) // or: if (!pred(\*result,\*first)) for version (2)  
\*(++result)=\*first;  
\}  
return ++result;  
\}  
  
  
Tips:  
从上面的等效算法中可以看出：unique并没有删除容器内的元素，一般情况下，unique会搭配sort（）函数先排序  
，再用容器的resize()函数重新调整大小（截断容器后面的元素），以达到保留容器内唯一元素的目的。**

**Example:**

**bool myfunction (int i, int j) \{  
return (i==j);  
\}  
  
  
int main () \{  
int myints\[\] = \{1,1,1,2,2,3,3,1,2,3\};  
std::vector<int> myvector (myints,myints+10);  
  
sort(myvector.begin(),myvector.end());//1,1,1,1,2,2,2,3,3,3   
  
 // using default comparison:  
 vector<int>::iterator it;  
 it=unique (myvector.begin(), myvector.end());  //1,2,3,1,2,2,2,3,3,3**

**myvector.resize(it-myvector.begin());//1,2,3**

**// myvector contains:  
  
 for (it=myvector.begin(); it!=myvector.end(); ++it)  
 \{   
cout << ' ' << \*it; //1,2,3  
 \}  
  
 // using predicate comparison:  
 unique (myvector.begin(), myvector.end(), myfunction);  // (no changes)  
  
  
 return 0;  
\}**