Shoping(map)

快来打我* 2023-07-16 07:59 9阅读 0赞

### ACM之map ###

*   *  关于map：
     *  hash\_map
     *   *   *  默认hash 和比较函数
             *  hash\_map 的比较函数
             *  hash\_map(size\_type n)
             *  map与hash\_map
     *  题目：
     *  我的代码：

## 关于map： ##

> map的特性是，所有元素都会根据元素的减值自动被排序。 map的所有元素都是pair，同时拥有实值(value)和键值(key)。  
> pair的第一个元素会被视为键值，第二个元素会被视为实值。 map不允许两个元素拥有相同的键值。  
> key值不可修改！

map中插入元素:  
注意后加入的在 begin一侧，即后入的排在前面；  
可利用rbegin 和 rend 反转输出，得到正确的顺序

//第一种
    map[key]=value;
    //第二种
    map<int,string> maplive;
    pair<int,string> value(1,"a")；
    maplive.insert(value);

begin() 返回指向map头部的迭代器  
end() 返回指向map末尾的迭代器  
clear() 删除所有元素  
count() 返回指定元素出现的次  
empty() 如果map为空则返回true  
erase() 删除一个元素  
find() 查找一个元素  
get\_allocator() 返回map的配置器  
insert() 插入元素  
key\_comp() 返回比较元素key的函数  
lower\_bound() 返回键值>=给定元素的第一个位置  
max\_size() 返回可以容纳的最大元素个数  
**rbegin() 返回一个指向map尾部的逆向迭代器  
rend() 返回一个指向map头部的逆向迭代器**  
size() 返回map中元素的个数  
swap() 交换两个map  
upper\_bound() 返回键值>给定元素的第一个位置  
value\_comp() 返回比较元素value的函数

## hash\_map ##

**hash\_map**是基于hash table（哈希表）。  
哈希表最大的优点，就是把**数据的存储和查找**消耗的时间大大降低，几乎可以看成是常数时间；而代价仅仅是消耗比较多的内存。然而在当前可利用内存越来越多的情况下，用空间换时间的做法是值得的。另外，编码比较容易也是它的特点之一。  
**基本原理**：使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数，也叫做散列函数），使得每个元素的关键字都与一个函数值（即数组下标，hash值）相对应，于是用这个数组单元来存储这个元素；也可以简单的理解为，按照关键字为每一个元素“分类”，然后将这个元素存储在相应“类”所对应的地方，称为桶。  
不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了“**碰撞**” —— 把不同的元素分在了相同的桶之中  
hash\_map，首先分配一大片内存，形成许多桶。**是利用hash函数，对key进行映射到不同区域（桶）进行保存**  
**插入过程**：  
得到key  
利用hash函数得到hash值  
得到桶值（一般用hash值对桶的个数求余）  
存放key和value在桶内  
**取值过程**:  
得到key值  
计算hash值  
得到桶号  
查找该桶内是否有和key值相同的，若无，则未找到（比较函数）  
若有，返回找到的值

#### 默认hash 和比较函数 ####

#include<iostream>
    using namespace std;
    #include<hash_map>
    #include<string>
    
    hash_map<int,string> myHash;
    myHash[100] = "100";
    myHash[900] = "900";
    
    hash_map::iterator iter =myHash.find(100);
    if(iter != myHash.end())
    .....
    //未声明hash函数和比较函数的，将使用默认的；
    hash_map<int, string> myMap;
    //等同于:
    hash_map<int, string, hash<int>, equal_to<int> > myMap;

struct hash<int> {
        
            size_t operator()(int __x) const {
         return __x; }
    };

key值只要是下列的类型，就可以不写hash函数

struct hash<char*>
    struct hash<const char*>
    struct hash<char> 
    struct hash<unsigned char> 
    struct hash<signed char>
    struct hash<short>
    struct hash<unsigned short> 
    struct hash<int> 
    struct hash<unsigned int>
    struct hash<long> 
    struct hash<unsigned long>

若没有则必须自定义hash函数，如string类

struct str_hash{
        
            size_t operator()(const string& str) const
            {
        
                    unsigned long __h = 0;
                    for (size_t i = 0 ; i < str.size() ; i ++)
                    __h = 5*__h + str[i];
                    return size_t(__h);
            }
    };
    //如果你希望利用系统定义的字符串hash函数，你可以这样写：
    struct str_hash{
        
            size_t operator()(const string& str) const
            {
        
                    return __stl_hash_string(str.c_str());
            }
    };

在声明自己的哈希函数时要注意以下几点：

**使用struct，然后重载operator().  
返回是size\_t  
参数是你要hash的key的类型。  
函数是const类型的。**

#### hash\_map 的比较函数 ####

在map中的比较函数，需要提供less函数。  
如果没有提供，缺省的也是less< Key>  
在hash\_map中，要比较桶内的数据和key是否相等，因此需要的是是否等于的函数:equal\_to< Key> 。  
equal\_to 源码：

//本代码可以从SGI STL
    //先看看binary_function 函数声明，其实只是定义一些类型而已。
    template <class _Arg1, class _Arg2, class _Result>
    struct binary_function {
        
            typedef _Arg1 first_argument_type;
            typedef _Arg2 second_argument_type;
            typedef _Result result_type;
    };
    //看看equal_to的定义：
    template <class _Tp>
    struct equal_to : public binary_function<_Tp,_Tp,bool>
    {
        
            bool operator()(const _Tp& __x, const _Tp& __y) const {
         return __x == __y; }
    };

若是自定义的类型，则需要自己构建compare函数：

使用equal\_to< mystruct>作为比较函数

struct mystruct{
        
    	int myID;
    	int value;
    	bool operater== (const mystruct &my) const{
        
    			return (myId == my.myID) && (value == my.value);
    			}
    	};

实现：

hash_map(mystruct,int,hash_str,equal_to<mystruct>) myHash;

构建函数对象

struct compare_str{
        
    	bool operature()(const char* p1, const char* p2) const{
        
    		 return strcmp(p1,p2)==0;
    		 }
    	};

实现：

hash_map(const char*,string,hash<char*>, compare_str);

#### hash\_map(size\_type n) ####

如果讲究效率，这个参数是必须要设置的。  
n 主要用来设置hash\_map容器中hash桶的个数。桶个数越多，hash函数发生冲突的概率就越小，重新申请内存的概率就越小。  
n越大，效率越高，但是内存消耗也越大。  
const\_iterator find(const key\_type& k) const. 用查找，输入为键值，返回为迭代器。

data\_type& operator\[\](const key\_type& k)

像使用数组一样使用。  
不过需要注意的是，当你使用\[key\]操作符时，如果容器中没有key元素，这就相当于自动增加了一个key元素。因此当你只是想知道容器中是否有key元素时，你可以使用find。如果你希望插入该元素时，你可以直接使用\[ \]操作符。  
insert

在容器中不包含key值时，insert函数和\[\]操作符的功能差不多。但是当容器中元素越来越多，每个桶中的元素会增加，为了保证效率，hash\_map会自动申请更大的内存，以生成更多的桶。  
因此在insert以后，以前的iterator有可能是不可用的  
erase 函数。

在insert的过程中，当每个桶的元素太多时，hash\_map可能会自动扩充容器的内存。  
erase并不自动回收内存。因此你调用erase后，其他元素的iterator还是可用的。

#### map与hash\_map ####

> 构造函数。hash\_map需要hash函数，等于函数；map只需要比较函数(小于函数).  
> 存储结构。hash\_map采用hash表存储，map一般采用红黑树(RB Tree)实现。因此其memory数据结构是不一样的。
> 
> 总体来说，hash\_map 查找速度会比map快，而且查找速度基本和数据数据量大小，属于常数级别;而map的查找速度是log(n)级别。并不一定常数就比log(n)小，hash还有hash函数的耗时，明白了吧，如果你考虑效率，特别是在元素达到一定数量级时，考虑考虑hash\_map。但若你对内存使用特别严格，希望程序尽可能少消耗内存，那么一定要小心，hash\_map可能会让你陷入尴尬，特别是当你的hash\_map对象特别多时，你就更无法控制了，而且hash\_map的构造速度较慢。

#include <hash_map>
    #include <string>
    #include <iostream>
    
    using namespace std;
    //define the class
    class ClassA{
        
            public:
            ClassA(int a):c_a(a){
        }
            int getvalue()const {
         return c_a;}
            void setvalue(int a){
        c_a;}
            private:
            int c_a;
    };
    
    //1 define the hash function
    struct hash_A{
        
            size_t operator()(const class ClassA & A)const{
        
                    //  return  hash<int>(classA.getvalue());
                    return A.getvalue();
            }
    };
    
    //2 define the equal function
    struct equal_A{
        
            bool operator()(const class ClassA & a1, const class ClassA & a2)const{
        
                    return  a1.getvalue() == a2.getvalue();
            }
    };
    
    int main()
    {
        
            hash_map<ClassA, string, hash_A, equal_A> hmap;
            ClassA a1(12);
            hmap[a1]="I am 12";
            ClassA a2(198877);
            hmap[a2]="I am 198877";
            
            cout<<hmap[a1]<<endl;
            cout<<hmap[a2]<<endl;
            return 0;
    }
    -bash-2.05b$ make my
    c++  -O -pipe -march=pentiumpro  my.cpp  -o my
    -bash-2.05b$ ./my
    I am 12
    I am 198877

## 题目： ##

Shopping  
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 6924 Accepted Submission(s): 2438

Problem Description  
Every girl likes shopping,so does dandelion.Now she finds the shop is increasing the price every day because the Spring Festival is coming .She is fond of a shop which is called “memory”. Now she wants to know the rank of this shop’s price after the change of everyday.

Input  
One line contians a number n ( n<=10000),stands for the number of shops.  
Then n lines ,each line contains a string (the length is short than 31 and only contains lowercase letters and capital letters.)stands for the name of the shop.  
Then a line contians a number m (1<=m<=50),stands for the days .  
Then m parts , every parts contians n lines , each line contians a number s and a string p ,stands for this day ,the shop p 's price has increased s.

Output  
Contains m lines ,In the ith line print a number of the shop “memory” ‘s rank after the ith day. We define the rank as :If there are t shops’ price is higher than the “memory” , than its rank is t+1.

Sample Input  
3  
memory  
kfc  
wind  
2  
49 memory  
49 kfc  
48 wind  
80 kfc  
85 wind  
83 memory

Sample Output  
1  
2

## 我的代码： ##

#include <bits/stdc++.h>
    
    using namespace std;
    
    int main()
    {
        
        int n, m, p;
        map< string, int> shop;
        while(cin>>n){
        
            string s;  //仅用于输入商店名字
            for(int i=1; i<=n; i++)
                cin>>s;
            cin>>m;
            while(m--){
        
                for(int i=1; i<=n; i++){
        
                    cin>>p>>s;
                    shop[s] += p;
                }
                int rank = 1;  //排名
                map<string,int>::iterator it;
                for(it = shop.begin(); it != shop.end(); it++)
                    if(it->second > shop["memory"])
                        rank++;
                cout<<rank<<endl;
            }
            shop.clear();
        }
        return 0;
    }

Shoping(map)

发表评论取消回复

还没有评论，来说两句吧...

相关阅读