Shulou(Shulou.com)06/01 Report--

This article introduces the relevant knowledge of "how to understand multimap and priority_queue". In the operation of actual cases, many people will encounter such a dilemma. Next, let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

Topic description: there is a man walking back and forth on a section of road every day, feeling bored, so he invented a stone-throwing game for himself: in an one-way walk, suppose there are n stones in the whole journey. Each stone has two important information, one is the location, the other is the distance the stone can be thrown. It is also worth noting that the bigger the stone, the closer it is to throw it. Starting from the first stone, the odd number of stones encountered was lifted and thrown forward, and the even number of stones encountered was not dealt with. If there are two stones in a certain position, the person will first see the larger stone (that is, the stone thrown at a closer distance). Now it is required to figure out how far the man has gone and there will be no stone to throw.

Input data: the first line gives the number of groups of test data t (1)

< = t , less >

This definition is used for other priorities for users to use non-less () functions.

It should be noted that no matter whether the container is the default container or not, vector needs to pass parameters, which is determined by the internal implementation of the priority queue correlation function.

For example:

Now that the element type is a structure type, the comparison function needs to be changed, and the processing is as follows:

Struct node

{

Element_type x

Element_type y

}

Bool compare (node a, node b)

{

Return a. X > a. Y; (the priority relationship here can be changed at will)

}

Priority_queue

Another example is as follows:

Struct node

{

Friend bool operator

< ( node a , node b ) { return a . y >

B. Y; (again, the priority order here can be changed as needed)

}

Element_type x

Element_type y

}

Priority_queue

< node>

Or something like this:

Priority_queue

< node , vector , less >

; / / the priority has actually changed at this time.

Supplementary note:

In the priority queue, there are two built-in priority comparison functions:

Less (), the priority decreases gradually from the head of the team.

Greater (), the priority increases gradually from the head of the team.

However, if there is no declaration, less () is used by default, and the third declaration method described above is used when you need to use greater ().

two。 Most of the other functions of the priority queue are similar to those of the normal queue queue.

The above is the use of priority queue method, the following I will use the multimap method to explain this problem, in this problem, the multimap method seems to be some trouble, but it is also a way to solve the problem, focusing on the use of related functions of multimap.

Priority_queue has the automatic sorting function in the sequential container, and the relational container also has this feature, and the red-black tree is very efficient.

Relational containers have two pairs of set / multiset and map / multimap:

The structure of set is equivalent to a set, which not only satisfies the uniqueness and certainty of the set, but also satisfies the order (the default arrangement from small to large). The related uses of multiset and set are mostly the same, except that multiset allows the occurrence of the same elements in the collection, which leads to differences in some functions.

The structure of map/multimap is equivalent to a set of mapping pairs, again, the two are more or less the same, except that elements with the same key values are allowed in multimap.

Because at a certain time, the position and throwing distance of each stone are determined and correspond one by one. So I thought I could use the map container, and because there may be more than one stone in the same place during the stone throwing process, I can be sure to use the multimap container.

The idea is more or less the same as the above way of thinking, first save the initial data into map, and then set the counting variables and store the current location of variables, map is not empty continue to count variables parity judgment and map delete, insert elements processing. The situation where the throwing distance is zero should also be considered.

There are some points to pay attention to in this process:

I. header file

Multimap is included in the map header file, and the # include statement should be added when the program is written at the beginning of the file.

II. Declaration

There are two types:

The first kind:

Multimap mp

Contains the following information

A multimap variable mp with key value of type key_type and associated value of type value_type is declared.

The keys in multimap are sorted from small to large according to the default sort order.

The second kind:

Multimap >

Contains the following information

A multimap variable mp with key value of type key_type and associated value of type value_type is declared.

The sorting rules of multimap internal key values are given by the comparison function compare. Please note that the parameters in the compare () function have only the type of key value, but not the type of associated value, because the sorting within multimap is only sorted according to the size of the key value, and the order of the associated value is not handled accordingly, thus it can be seen that the relative position of the same key value element in multimap is not determined by the size of the associated value, but by the order in which it is added.

Third, ordinary map can use map [key] to operate on the associated values of elements whose key value is key, but multimap does not contain this property, so adding elements to multimap can only use the insert () function, nor can you use mp [key] to access an element. The usage is as follows:

Mp. Insert (pair

< key_type ,value_type>

(key, value))

Mp. Insert (make_pair (key, value))

Where pair is a template type with two members, first and second. The type of the two members can be determined as needed, either a basic data type or a user-defined type. Pair can be passed and used as a new type of function. The statement is as follows:

Pair

< element_type , element_type >

P = (element_1, element_2)

Pair

< element_type , element_type >

P = make_pair (element_1, element_2)

When you need to use two members of pair, it is as follows:

P. First

P. Second

Clever use of pair, when a function needs to return two different types of values, you can define pair to return.

Fourth, how to determine the number of elements with the same key value but different associated values, and how to access them:

Determine the number of functions to use

Mp. Count (key)

Access one by one

Mp. Equal_range (key)

Note that the return value of this function is two iterators, where the first iterator returns the iterator of the first element of the key value, and the second iterator returns the iterator of the last element of the key to access the next element that is about to jump. Therefore, you need to use the template pair, as follows:

Typedef multimap

< key_type , value_type >

:: iterator iter

Pair

< iter , iter >

P

P = mp. Equal_range (key)

While (p. First! = p. Second)

{

Cout

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.