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

Brief introduction

Obviously, these two header files are the unordered versions of the map and set header files, respectively. So they have an important property:

Out of order

How to out of order

This unorder implies that the underlying implementation of the class in the two header files-Hash. It is also because of this that you can pass in a custom hash function, or hash function object, to be exact, when declaring these unordered template classes.

Elements with the same hash value are placed in the same bucket.

Why is it out of order?

In the case of providing mapping and collection functions, we focus on the rapid acquisition of elements.

Map and set implemented with tree structure (red-black tree, binary search tree, etc.) usually need to traverse the tree structure from the top to the next from the root node when searching, obtaining and modifying elements, so the time complexity is linear; while through the hash table, as long as the hash function and bucket size are selected properly, the time complexity will be constant (only need to call the function once and do a small search).

Unidirectional iterator

The implementation of the hash table complicates the two-way traversal on the container, and there seems to be no suitable method to achieve high efficiency and speed. Therefore, unorder versions of map and set provide only forward iterators (non-unorder versions provide bi-directional iterators).

What function is missing?

Lower_bound

Upper_bound

The normal version of map and set, which are ordered containers, can tell which before and after each element should be; this version of the container is different because they are out of order and cannot determine the order of each element. Therefore, the container does not have enough information to calculate the two boundaries (however, the equality comparison of elements is still feasible).

What function is added?

For the sake of the concept of implementation, this version of the class template is essential with some special functions.

Bucket dependent (Bucket)

Bucket_count: number of buckets.

Max_bucket_count: maximum number of barrels.

Bucket_size: bucket size, that is, capacity.

Bucket: locates the bucket position of a given element.

Hash strategy

Load_factor: returns load factor, that is, the ratio of the current number of elements to the number of buckets in the container.

Max_load_factor: returns or sets the maximum load factor.

Rehash: set the number of buckets and rehash the elements.

Reserve: the number of buckets requested to be retained to a given value.

Note that no function can change the capacity of the bucket, and the bucket may also grow dynamically.

Observers

Hash_function: returns the hash function (passed in as an argument when declared, or the default hash in the funtional header file).

Key_eq: returns the equality predicate of key, which is similar to hash_function.

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.