STL for C++

Today, when I was looking at a piece of code, I found that it was sorted in just one sentence, which is like this:

sort(rotateArray.begin(),rotateArray.end());

I was shocked, and then I checked sort Usage, usage of

sort function

Write your own O(n^2) sorting such as bubbles. Not only is the program prone to timeout, but it is also very likely to be written incorrectly.

There is a sort function in STL, which can directly sort the array, with a complexity of n*log2(n). To use this function, you need to include the header file.
This function can pass two parameters or three parameters. The first parameter is the first address of the interval to be sorted, and the second parameter is the next address of the end address of the interval.

In other words, the sorting interval is [a,b). To put it simply, there is an array int a[100]. To sort the elements from a[0] to a[99], just write sort(a, a+100). The default sorting method is ascending order.
  Take the question "AC Strategy" that I asked as an example. If you need to sort the elements from 0 to len-1 of the array t, just write sort(t,t+len);
 The same goes for sorting the vector v, sort (v.begin(),v.end());//This is exactly the usage I saw before
The sorted data type is not limited to integers, as long as it defines a type that is less than arithmetic, such as string class string.
If there is no data type defined for the less than operation, or if you want to change the sorting order, you must use the third parameter - the comparison function. The comparison function is a self-defined function, and the return value is bool type. It specifies what kind of relationship is "less than". If you want to sort the integer array just now in descending order, you can first define a comparison function cmp
bool cmp(int a, int b)
{
       return a>b;
}
    When sorting, just write sort(a, a+100 ,cmp);

Suppose you have defined a structure node
struct node{
int a;
int b;
double c;
}
There is an array of node type node arr[100], and you want to sort it : First sort by a value in ascending order, if a value is the same, then sort by b value in descending order, if b is still the same, sort by c in descending order.

You can write such a comparison function:

The following is a code snippet:

bool cmp(node x,node y)
{
     if(x.a!=y.a) return x.a
     if(x.b!=y.b) return x.b>y.b;
     return return x.c>y.c;

}

When sorting, write sort(arr,a+100,cmp);

qsort(s[0],n,sizeof(s[0 ]),cmp);
int cmp(const void *a,const void *b)
{
  return *(int *)a-*(int *)b;
}

1. For int type array Sorting

int num[100];

Sample:

int cmp ( const void *a, const void *b)
{
return *(int *)a - *(int *)b;
}

qsort(num,100,sizeof(num[0]),cmp);

2. Sort char type array (same as int type)

char word[100];

Sample:

int cmp( const void *a , const void *b )
{
return *(char *)a - *(int *)b;
}

qsort(word,100,sizeof(word[0]),cmp);

三, Sort the double type array (pay special attention)

double in[100];

int cmp( const void *a, const void *b)
{
return *(double *)a > *(double *) b ? 1 : -1;
}

qsort(in,100,sizeof(in[0]),cmp);

Fourth level sorting of structures

struct In
{
double data;
int other;
}s[100]

//Sort the structures according to the value of data from small to large. Regarding the sorting key data data in the structure, there can be many types. Refer to the above example and write

int cmp( const void * a ,const void *b)
{
return ((In *)a)->data - ((In *)b)->data ;
}

qsort(s,100,sizeof(s[0]) ,cmp);

5. Pair the structure

struct In
{
int x;
int y;
}s[100];

// Sort by x from small to large, when x is equal, y from small to large Sort from big to small

int cmp( const void *a, const void *b)
{
struct In *c = (In *)a;
struct In *d = (In *)b;
if(c- >x != d->x) return c->x - d->x;
else return d->y - c->y;
}

qsort(s,100,sizeof(s[0]) ,cmp);

6. Sort strings

struct In
{
int data;
char str[100];
}s[100];

//According to the dictionary of string str in the structure Sequential sorting

int cmp ( const void *a , const void *b )
{
return strcmp( ((In *)a)->str , ((In *)b)->str );
}

qsort(s,100,sizeof(s[0]),cmp);

7. Cmp for finding convex hull in computational geometry

int cmp(const void *a,const void *b) //The key cmp function is to sort all points except 1 point by rotation angle
{
struct point * c=(point *)a;
struct point *d=(point *)b;
if( calc(*c,*d,p[1]) else if( !calc(* c,*d,p[1]) && dis(c->x,c->y,p[1].x,p[1].y) x,d->y,p[1]. x,p[1].y)) //If it is on a straight line, put the far one in front
return 1;
else return -1;
}

Okay, after talking about so many uses of sort, Is anyone still confused about what STL is?

Let’s talk about what STL (content source network) is

1. General introduction

STL (Standard Template Library), the standard template library, is an industrial-strength, efficient C++ program library. It is included in the C++ Standard Library and is the latest and most revolutionary part of the ANSI/ISO C++ standard. This library contains many basic data structures and basic algorithms commonly used in computer science. It provides an extensible application framework for C++ programmers, which highly reflects the reusability of software.

From a logical level, STL embodies the idea of ​​generic programming and introduces many new terms, such as requirements, concepts, models, and containers. (container), algorithm (algorithmn), iterator (iterator), etc. Like polymorphism in OOP (object-oriented programming), generics are also a software reuse technology; From an implementation level, the entire STL is type parameterized Implemented, this method is based on a language feature that did not appear in the earlier C++ standard - template. If you check the source code of any version of STL, you will find that it is absolutely true that templates serve as the cornerstone of the entire STL. In addition, there are many new features of C++ that facilitate the implementation of STL;

2. The six major components of STL

Container (Container) is a data structure, such as list, vector, and deques , provided as a method of the template class. In order to access the data in the container, you can use the iterator output by the container class;

Iterator (Iterator) provides methods to access objects in the container. For example, you can use a pair of iterators to specify a range of objects in a list or vector. An iterator is just like a pointer. In fact, a C++ pointer is also an iterator. However, iterators can also be class objects that define operator*() and other pointer-like operator methods;

Algorithm is a template function used to operate data in a container. For example, STL uses sort() to sort data in a vector and find() to search for objects in a list. The functions themselves have nothing to do with the structure and type of the data they operate on, so they can be used from simple arrays to Used on any data structure of highly complex containers;

Function object (functor) is also called a function object (function object). It is actually a struct with an overloaded () operator. There is nothing special about it. Place

Iteration adapter (Adaptor)

Space allocator (allocator) The main work includes two parts 1. Creation and destruction of objects 2. Acquisition and release of memory

The following main discussions: containers, iterators, algorithms, adapters . For more details, please refer to C++ Primer

1. STL container

1) Sequence containers, each element has a fixed position - it depends on the insertion time and location, regardless of the element value. vector, deque, list;

Vectors: Place elements in a dynamic array for management. Elements can be accessed randomly (direct access using indexes). Adding or removing elements from the end of the array is very fast. However, it is more time-consuming to place elements in the middle or head;

Deques: is the abbreviation of "double-ended queue". Elements can be accessed randomly (direct access using index). It is very easy to add or remove elements from the head and tail of the array. fast. However, it is more time-consuming to insert elements in the middle or head;

Lists: doubly linked lists, do not provide random access (walk to the elements that need to be accessed in order, O(n)), and perform insertion or deletion operations at any position. Very fast, just adjust the pointer internally;

2) Associated containers (Associated containers), the position of elements depends on specific sorting criteria and has nothing to do with the insertion order, set, multiset, map, multimap;

Sets/Multisets: The internal elements are automatically sorted according to their values. Elements with the same value in a Set can only appear once. Multisets can contain multiple elements with the same value. The internal elements are implemented by a binary tree (actually based on a red-black tree (RB-tree)). , easy to find;

   Maps/Multimaps：Map的元素是成对的键值/实值，内部的元素依据其值自动排序，Map内的相同数值的元素只能出现一次，Multimaps内可包含多个数值相同的元素，内部由二叉树实现（实际上基于红黑树(RB-tree）实现），便于查找；

另外有其他容器hash_map,hash_set,hash_multiset,hash_multimap。

  容器的比较：

2.STL迭代器 

Iterator（迭代器）模式又称Cursor（游标）模式，用于提供一种方法顺序访问一个聚合对象中各个元素, 
而又不需暴露该对象的内部表示。或者这样说可能更容易理解：Iterator模式是运用于聚合对象的一种模式，通过运用该模式，使得我们可以在不知道对象内部表示的情况下，按照一定顺序（由iterator提供的方法）访问聚合对象中的各个元素。

迭代器的作用：能够让迭代器与算法不干扰的相互发展，最后又能无间隙的粘合起来，重载了*，＋＋，＝＝，！＝，＝运算符。用以操作复杂的数据结构，容器提供迭代器，算法使用迭代器；

常见的一些迭代器类型：iterator、const_iterator、reverse_iterator和const_reverse_iterator

迭代器一般声明使用示例

vector<T>::iterator it;
list<T>::iterator it;
deque<T>::iterator it；

           input         output

              \            /  

                forward

                     |

                bidirectional

                     |

               random access                            

要注意，上面这图表并不是表明它们之间的继承关系：而只是描述了迭代器的种类和接口。处于图表下层的迭代器都是相对于处于图表上层迭代器的扩张集。例如：forward迭代器不但拥有input和output迭代器的所有功能，还拥有更多的功能。

各个迭代器的功能如下：

迭代器的操作：

每种迭代器均可进行包括表中前一种迭代器可进行的操作。

只有顺序容器和关联容器支持迭代器遍历，各容器支持的迭代器的类别如下：

 3.STL算法

STL算法部分主要由头文件,,组成。要使用 STL中的算法函数必须包含头文件，对于数值算法须包含，中则定义了一些模板类，用来声明函数对象。
STL中算法大致分为四类：
1）、非可变序列算法：指不直接修改其所操作的容器内容的算法。
2）、可变序列算法：指可以修改它们所操作的容器内容的算法。
3）、排序算法：包括对序列进行排序和合并的算法、搜索算法以及有序序列上的集合操作。
4）、数值算法：对容器内容进行数值计算。

 

All algorithms are carefully classified and their functions are marked below:
Search algorithms (13): Determine whether the container contains a certain value
adjacent_find: Within the scope of the iterator pair of identified elements, search for a pair of adjacent repeated elements, if found Returns a ForwardIterator pointing to the first element of the pair. Otherwise return last. The overloaded version uses the input binary operator instead of checking for equality.
Binary_search: Search for value in an ordered sequence and return true if found. The overloaded version uses the specified comparison function object or function pointer to determine equality.
Count: Use the equal operator to compare the elements in the flag range with the input value and return the number of equal elements.
Count_if: Use the input operator to operate on the elements within the flag range and return the number of true results.
equal_range: The function is similar to equal, returning a pair of iterators, the first one represents lower_bound, and the second one represents upper_bound.
Find: Use the equal operator of the underlying element to compare the elements in the specified range with the input value. When a match occurs, the search ends and an InputIterator for the element is returned.
find_end: Find the last occurrence of "the second sequence marked by another pair of input iterators" in the specified range. If found, the first ForwardIterator of the last pair is returned, otherwise the first ForwardIterator of the input "other pair" is returned. The overloaded version uses the user-entered operator instead of the equals operation.
Find_first_of: Find the first occurrence of any element in the "second sequence marked by another pair of input iterators" within the specified range. The overloaded version uses user-defined operators.
find_if: Use the input function instead of the equal operator to execute find.
lower_bound: Returns a ForwardIterator, pointing to the first position in the ordered sequence range where the specified value can be inserted without destroying the order of the container. Overloaded functions use custom comparison operations.
upper_bound: Returns a ForwardIterator, pointing to the last position where value can be inserted into the ordered sequence range without destroying the container order. This position marks a value greater than value. Overloaded functions use custom comparison operations.
Search: Given two ranges, a ForwardIterator is returned. If the search succeeds, it points to the position where the subsequence (second range) appears for the first time in the first range. If the search fails, it points to last1. The overloaded version uses a custom comparison operation.
Search_n: Search for subsequences in which val appears n times within the specified range. The overloaded version uses a custom comparison operation.

Sorting and general algorithms (14): Provide element sorting strategies
inplace_merge: Merge two ordered sequences, and the resulting sequence covers both ends of the range. The overloaded version sorts using the input operation.
merge: Merge two ordered sequences and store them in another sequence. Overloaded version uses custom comparison.
nth_element: Reorder the sequence in the range so that all elements smaller than the nth element appear in front of it, and all elements larger than it appear in the back. The overloaded version uses a custom comparison operation.
partial_sort: Partially sort the sequence so that the number of sorted elements can be placed within the range. The overloaded version uses a custom comparison operation.
Partial_sort_copy: Similar to partial_sort, but copies the sorted sequence to another container.
partition: Reorder the elements in the specified range, use the input function, and put the elements with a true result before the elements with a false result.
Random_shuffle: Randomly adjust the order of elements in the specified range. The overloaded version inputs a random number generation operation.
reverse: Reorder the elements in the specified range in reverse order.
reverse_copy: Similar to reverse, but writes the results to another container.
rotate: Move the elements in the specified range to the end of the container, and the element pointed to by middle becomes the first element of the container.
rotate_copy: Similar to rotate, but writes the result to another container.
sort: Rearrange the elements in the specified range in ascending order. The overloaded version uses a custom comparison operation.
stable_sort: Similar to sort, but retains the order relationship between equal elements.
stable_partition: Similar to partition, but the relative order in the container is not guaranteed to be preserved.

Deletion and replacement algorithms (15)
copy: Copy sequence
copy_backward: Same as copy, but the elements are copied in the reverse order.
iter_swap: Swap the values ​​​​of two ForwardIterators.
remove: Remove all elements in the specified range that are equal to the specified element. Note that this function is not a real delete function. Built-in functions are not suitable for use with the remove and remove_if functions.
remove_copy: Copy all unmatched elements to a specified container, and return an OutputIterator pointing to the next position of the last element copied.
remove_if: Remove all elements within the specified range whose input operation result is true.
remove_copy_if: Copy all unmatched elements to a specified container.
replace: Replace all elements equal to vold in the specified range with vnew.
replace_copy: Similar to replace, but writes the result to another container.
replace_if: Replace all elements with true operation results in the specified range with new values.
replace_copy_if: Same as replace_if, but writes the result to another container.
swap: Swap the values ​​stored in two objects.
swap_range: Swap the elements in the specified range with another sequence element value.
unique: Remove duplicate elements from the sequence. Similar to remove, it cannot actually delete elements. Overloaded version uses custom comparison operation.
unique_copy: Similar to unique, but outputs the results to another container.

​ Permutation and combination algorithm (2): Provides calculation of all possible permutations and combinations of a given set in a certain order
​ next_permutation: ​ ​ ​ ​ Take out the permutation in the current range and reorder it into the next permutation. The overloaded version uses a custom comparison operation.
prev_permutation: Take out the sequence in the specified range and reorder it to the previous sequence. Returns false if there is no previous sequence. The overloaded version uses a custom comparison operation.

Arithmetic algorithm (4)
accumulate: The sum of the sequence segment elements identified by the iterator is added to an initial value specified by val. The overloaded version no longer performs addition, but the passed binary operator is applied to the element.
partial_sum: Create a new sequence in which each element value represents the sum of all elements before that position in the specified range. The overloaded version uses a custom operation instead of addition.
inner_product: Do the inner product of two sequences (multiply the corresponding elements and then sum) and add the inner product to an input initial value. Overloaded version uses user-defined actions.
adjacent_difference: Create a new sequence, each new value in the new sequence represents the difference between the current element and the previous element. An overloaded version computes the difference between adjacent elements using the specified binary operation.

Generation and mutation algorithms (6)
fill: Assign the input value to all elements within the flag range.
fill_n: Assign the input value to all elements in the range from first to first+n.
for_each: Use the specified function to iteratively access all elements in the specified range in sequence, and return the specified function type. This function must not modify elements in the sequence.
Generate: Continuously call the input function to fill the specified range.
Generate_n: Similar to the generate function, fill in n elements starting from the specified iterator.
Transform: Apply the input operation to each element in the specified range and generate a new sequence. The overloaded version operates on a pair of elements, with the other element coming from another sequence of inputs. The results are output to the specified container.

    關係演算法(8個)
    equal:                   重載版本使用輸入的運算元來取代預設的等於運算子。
    includes:               由重載版本使用使用者輸入的函數。     lexicographical_compare:  比較兩個序列。重載版本使用使用者自訂比較操作。
    max:                      以較大為其中一個元素所傳回兩個元素。重載版本使用自訂比較操作。
    max_element:              以ForwardIterator，並指出序列中最大的元素。重載版本使用自訂比較操作。
    min:                      以兩個為中較少且較小一個元素。重載版本使用自訂比較操作。
    min_element:              以ForwardIterator，指出數列中最小的元素。重載版本使用自訂比較操作。
    mismatch:             ‧如果都匹配，則傳回每個容器的last。重載版本使用自訂的比較操作。
 

    集合演算法(4個)
    set_union:             重載版本使用自訂的比較操作。
    set_intersection:         建構一個有序序列，其中元素在兩個序列中都存在。重載版本使用自訂的比較操作。
    set_difference:           建構一個有序序列，且該序列僅保留在第一個序列中存在的而第二個中所沒有的元素。重載版本使用自訂的比較操作。
    set_symmetric_difference: 建構一個有序序列，該序列取兩個序列的對稱差集(並集-交集)。
 

   堆演算法(4個)
    make_heap:              重載版本使用自訂比較操作。
    pop_heap:                 並與最大元素實際從堆中彈出，而是重新排序。它把first和last-1交換，然後重新生成一個堆。可使用容器的back來存取被"彈出"的元素或使用pop_back進行真正的刪除。重載版本使用自訂的比較操作。
    push_heap:                假設first到last-1是一個有效堆，而被加入到堆的元素存放在位置last-1，重新生成堆。在指向函數前，必須先把元素插入容器後。重載版本使用指定的比較操作。
    sort_heap:                以指定範圍內的序列重新排序，而它假設此序列為有序堆疊。重載版本使用自訂比較操作。

 

4.適配器

STL提供了三個容器適配器：queue、priority_queue、stack。這些適配器都是包裝了vector、list、deque中某個順序容器的包裝器。注意：適配器沒有提供迭代器，也不能同時插入或刪除多個元素。以下對各個適配器進行概括總結。

（1）stack用法

#include
template class stack;

可以使用三個標準順序容器cotr、deque(預設)、list中的任何一個作為預設的底層模型。

bool stack::empty()                               //判断堆栈是否为空
void stack::pop()                                 //弹出栈顶数据
stack::push(T x)                                  //压入一个数据
stack::size_type stack::size()                 //返回堆栈长度
T stack::top()                                    //得到栈顶数据

代码示例：

stack<int> intDequeStack;  
stack<int,vector<int>> intVectorStack;  
stack<int,list<int>> intListStack;

2）queue用法

#include
template > class  queue;

第一个参数指定要在queue中存储的类型，第二个参数规定queue适配的底层容器，可供选择的容器只有dequeue和list。对大多数用途使用默认的dequeue。

queue<T>::push(T x)
void queue<T>::pop()
T queue<T>::back()
T queue<T>::front()
queue<T>::size_type 
queue<T>::size()
bool queue<T>::empty()

代码示例：

queue intDequeQueue;    
queue> intListQueue;

 

（3）priority_queue用法

#include
template , typename Compare = less > class priority_queue;

priority_queue也是一个队列，其元素按有序顺序排列。其不采用严格的FIFO顺序，给定时刻位于队头的元素正是有最高优先级的元素。如果两个元素有相同的优先级，那么它们在队列中的顺序就遵循FIFO语义。默认适配的底层容器是vector，也可以使用deque，list不能用，因为priority_queue要求能对元素随机访问以便进行排序。

priority_queue<T>::push(T x)
void priority_queue<T>::pop()
T priority_queue<T>::top()
priority_queue<T>::size_type 
priority_queue<T>::size()
bool priority_queue<T>::empty()

代码示例：

priority_queue, greater >
priority_queue, greater >

 

标准库默认使用元素类型的

优先队列第一种用法，通过默认使用的

priority_queue qi;

示例中输出结果为：9 6 5 3 2

优先队列第二种用法，建立priority_queue时传入一个比较函数，使用functional.h函数对象作为比较函数。

priority_queue, greater >qi2;

示例2中输出结果为：2 3 5 6 9

优先队列第三种用法，是自定义优先级。

struct node 
{
     friend bool operator< (node n1, node n2)
     {
         return n1.priority < n2.priority;
     } 
     int priority;
     int value; 
}; 
priority_queue<node> qn;

在示例3中输出结果为：

优先级  值

9          5

8          2

6          1

2          3

1          4

在该结构中，value为值，priority为优先级。通过自定义operator编译不通过。