面向对象程序设计——mapの简析

🕗 发布于 2024-09-24 02:44 c++ 算法 开发语言 stl 数据结构

1.map的定义

Key就是map底层关键字的类型，T是map底层value的类型，set默认要求Key⽀持⼩于⽐较，如果不⽀持或者需要的话可以⾃⾏实现仿函数传给第⼆个模版参数，map底层存储数据的内存是从空间配置器申请的。⼀般情况下，我们都不需要传后两个模版参数。map底层是⽤红⿊树实现，增删查改效率是O(logN) ，迭代器遍历是⾛的中序，所以是按key有序顺序遍历的

1.1map的构造

显式实例化直接构造

//map
int main()
{
//显式定义
map<string, string> dict;
pair<string, string> key("first", "第一个");
dict.insert(key);

return 0;
}

匿名对象构造

//map
int main()
{
//显式定义
map<string, string> dict;
pair<string, string> key("first", "第一个");
dict.insert(key);

//匿名对象
dict.insert(pair<string, string>("second", "第二个"));

return 0;
}

函数模版构造

//map
int main()
{
//显式定义
map<string, string> dict;
pair<string, string> key("first", "第一个");
dict.insert(key);

//匿名对象
dict.insert(pair<string, string>("second", "第二个"));

//make_pair函数模版直接插入
dict.insert(make_pair("sort", "排序"));

return 0;
}

多参数类型转换

//map
int main()
{
//显式定义
map<string, string> dict;
pair<string, string> key("first", "第一个");
dict.insert(key);

//匿名对象
dict.insert(pair<string, string>("second", "第二个"));

//make_pair函数模版直接插入
dict.insert(make_pair("sort", "排序"));

//C++11支持多参数类型转换
dict.insert({ "hello","泥嚎" });
//key相同的情况下,value不相等不会更新,而且key不可以被修改而value可以
dict.insert({ "hello","泥嚎xixixixixi" });

//遍历,这里需要显式打印key与value,因为他们是公有的
//map<string, string>::iterator it = dict.begin();
auto it = dict.begin();
while (it != dict.end())
{
//使用.访问
//cout << (*it).first << ":" << (*it).second << endl;

//使用->访问结构体,这里实际上就是重载了一个->
//cout << it.operator->()->first << ":" << it.operator->()->second << endl;
cout << it->first << ":" << it->second << endl;
++it;
}

return 0;
}

小tips:

1.在map中有一个pair存储key与value，后面我们使用的first就是key，second就是value

2.当新插入一个数据与原来某个数据相同时，如果key相同value不同的情况下，该数据不会更新，且key不可以被修改而value可以被修改

3.通常使用迭代器遍历map时需要显式的使用.或者->访问pair中的first与second，不能直接解引用

2.pair

map底层的红⿊树节点中的数据，使⽤pair存储键值对数据

pair的代码解释

typedef pair<const Key, T> value_type;
template <class T1, class T2>
struct pair 
{
    typedef T1 first_type;
    typedef T2 second_type;
    T1 first;
    T2 second;
 
    pair(): first(T1()), second(T2())
    {}
 
   pair(const T1& a, const T2& b): first(a), second(b)
   {}
 
   template<class U, class V> 
   pair (const pair<U,V>& pr): first(pr.first), second(pr.second)
   {}
};
template <class T1,class T2>
inline pair<T1,T2> make_pair (T1 x, T2 y)
{
 return ( pair<T1,T2>(x,y) );
}

3.map的增删查

3.1插入

insert插⼊⼀个pair<key, T>对象 
1、如果key已经在map中，插⼊失败，则返回⼀个pair<iterator,bool>对象，返回pair对象
first是key所在结点的迭代器，second是false 
2、如果key不在在map中，插⼊成功，则返回⼀个pair<iterator,bool>对象，返回pair对象
first是新插⼊key所在结点的迭代器，second是true 
也就是说⽆论插⼊成功还是失败，返回pair<iterator,bool>对象的first都会指向key所在的迭
代器 
那么也就意味着insert插⼊失败时充当了查找的功能，正是因为这⼀点，insert可以⽤来实现
operator[]
需要注意的是这⾥有两个pair，不要混淆了，⼀个是map底层红⿊树节点中存的pair<key, T>，另
⼀个是insert返回值pair<iterator,bool>

这里我们只介绍最常用并且较为重要的一种插入，即在插入后会返回一个pair，注意这里的pair与map底层的pair不同，若插入成功就会返回pair<插入后的key的迭代器，true>，插入失败就返回pair<原来就存在相同key的迭代器，false>，这对后面的operator[]有很大作用

//单个数据插⼊，如果已经key存在则插⼊失败,key存在相等value不相等也会插⼊失败 
pair<iterator, bool> insert(const value_type& val);
//列表插⼊，已经在容器中存在的值不会插⼊ 
void insert(initializer_list<value_type> il);
//迭代器区间插⼊，已经在容器中存在的值不会插⼊ 
template <class InputIterator>
void insert(InputIterator first, InputIterator last);

//插入
int main()
{
map<int, string> mymap;
//1.单个数据插⼊，如果已经key存在则插⼊失败,key存在相等value不相等也会插⼊失败 
    //pair<iterator, bool> insert(const value_type& val);
mymap.insert({ 1, "first" });
mymap.insert({ 1,"first_change" });
auto it = mymap.begin();
while (it != mymap.end())
{
cout << it->first << ":" << it->second << endl;
it++;
}

return 0;
}

3.2删除

// 删除⼀个迭代器位置的值 
iterator erase (const_iterator position);
// 删除k，k存在返回0，存在返回1 
size_type erase (const key_type& k);
// 删除⼀段迭代器区间的值 
iterator erase (const_iterator first, const_iterator last);

//删除
int main()
{
map<int, string> mymap;
mymap.insert({ 1, "first" });
mymap.insert({ 2,"second" });
mymap.insert({ 3,"three" });
mymap.insert({ 4,"four" });
mymap.insert({ 5,"five" });
auto it1 = mymap.begin();
while (it1 != mymap.end())
{
cout << it1->first << ":" << it1->second << " ";
it1++;
}
cout << endl;
    //迭代器删除
mymap.erase(mymap.begin());
auto it2 = mymap.begin();
while (it2 != mymap.end())
{
cout << it2->first << ":" << it2->second << " ";
it2++;
}
cout << endl;
    //删除指定的key所对应的pair
mymap.erase(4);
auto it3 = mymap.begin();
while (it3 != mymap.end())
{
cout << it3->first << ":" << it3->second << " ";
it3++;
}
cout << endl;

return 0;
}

3.3查找

//查找k，返回k所在的迭代器，没有找到返回end() 
iterator find(const key_type& k);
//查找k，返回k的个数 
size_type count(const key_type& k) const;

int main()
{
//这里使用int()默认初始化为0
map<string, int> mymap;
mymap.insert({ "苹果",int() });
mymap.insert({ "香蕉",int() });
mymap.insert({ "西瓜",int() });
mymap.insert({ "菠萝",int() });
mymap.insert({ "苹果",int() });
mymap.insert({ "柑橘",int() });
mymap.insert({ "苹果",int() });
auto it1 = mymap.begin();
while (it1 != mymap.end())
{
cout << it1->first << ":" << it1->second << " ";
it1++;
}
cout << endl;

auto it = mymap.find("苹果");
cout << it->first << ":" << it->second << endl;

int count = mymap.count("苹果");
if (count)
{
cout << "苹果存在" << endl;
}
else
{
cout << "苹果不存在" << endl;
}

return 0;
}

4.operatpr[]间接实现增删查改

1、如果k不在map中，insert会插⼊k和mapped_type默认值，同时[]返回结点中存储 mapped_type值的引⽤，那么我们可以通过引⽤修改返映射值。所以[]具备了插⼊+修改功能

//operator[]
int main()
{
map<int, string> mymap;
mymap.insert({ 1,"first" });

//1.原来的key不存在->插入+修改
//key不存在->插入{2,""};
mymap[2];

//key不存在->插入+修改{3,"third"};
mymap[3] = "third";

return 0;
}

2、如果k在map中，insert会插⼊失败，但是insert返回pair对象的first是指向key结点的迭代器，返回值同时[]返回结点中存储mapped_type值的引⽤，所以[]具备了查找+修改的功能

//operator[]
int main()
{
map<int, string> mymap;
mymap.insert({ 1,"first" });

//2.原来的key存在->查找+修改
//key存在->查找,但是必须确定要查找的元素一定存在
cout << mymap[2] << endl;

//key存在->修改
mymap[3] = "third_change";
cout << mymap[3] << endl;

return 0;
}

5.multimap和map的差异

multimap和map的使⽤基本完全类似，主要区别点在于multimap⽀持关键值key冗余，那么 insert/find/count/erase都围绕着⽀持关键值key冗余有所差异，这⾥跟set和multiset完全⼀样，⽐如 find时，有多个key，返回中序第⼀个。其次就是multimap不⽀持[]，因为⽀持key冗余，[]就只能⽀持插⼊了，不能⽀持修改

6.实战代码练习

138.随机链表的复制

思路解析：

本题的难点就是如何深拷贝一个随机链表，随机链表的定义就是每一个节点都有两个指针，一个指针next指向下一个节点，另一个随机指针指向任意节点，难点就是拷贝这两个指针

不过在学习了map后我们可以使用映射拷贝，即首先创建一个新的链表首先拷贝原链表以及next指针，然后将该链表存储在一个map中，使用每个节点本身当做key，random指针当做value，之后处理拷贝而来的新链表中的random指针，使用map中的key做映射，保证random在拷贝后链表中的相对位置与原链表的相同，最后返回拷贝而来的新链表的头结点

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node* copyRandomList(Node* head) 
    {
        map<Node*,Node*> mapNode;
        Node* copyhead = nullptr;
        Node* copytail = nullptr;
        Node* cur = head;

        //拷贝原链表映射到map中并且创建一个新链表拷贝原链表
        while(cur)
        {
            //初始时刻
            if(copytail == nullptr)
            {
                copyhead = copytail = new Node(cur->val);
            }
            else
            {
                //从尾节点开始接入新节点
                copytail->next = new Node(cur->val);
                copytail = copytail->next;
            }
            //映射拷贝到map中
            mapNode[cur] = copytail;
            cur = cur->next;
        }
        
        //处理random指针，copy与cur指针同时运动
        cur = head;
        Node* copy = copyhead;
        while(cur)
        {
            if(cur->random == nullptr)
            {
                copy->random = nullptr;
            }
            else
            {
                //使用映射处理random节点
                copy->random = mapNode[cur->random];
            }
            cur = cur->next;
            copy = copy->next;
        }
        return copyhead;
    }
};

原文地址：https://blog.csdn.net/2301_80689220/article/details/142444337

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：828华为云征文 | 将Vue项目部署到Flexus云服务器X实例并实现公网访问
下一篇：SaltStack的state定义主机状态及Jinja模版的使用

大模型培训讲师叶梓:Llama Factory 微调模型实战分享提纲
LLaMA-Factory ——一个高效、易用的大模型训练与微调平台。它支持多种预训练模型，并且提供了丰富的训练算法，包括增量预训练、多模态指令监督微调、奖励模型训练等。
阅读更多2024-09-24
TM-align蛋白质聚类数据格式转化
可以进一步把不符合要求的结构过滤掉，从而得到的数据集可以用于结构预测或蛋白质设计的模型研究。第一列为编号，第二列为聚类的代表序列，第三列为所有的其它同源序列，逗号隔开。其中，第一列为聚类的代表序列，第
阅读更多2024-09-24
掌上高考爬虫逆向分析
掌上高考爬虫逆向分析
阅读更多2024-09-24
笔记整理—内核！启动！—linux应用编程、网络编程部分（4）linux文件属性
整理一下学习的内容，个人观点可能存在错误。对linux的文件属性进行介绍，并说明用什么函数可用对文件的属性进行查看以及修改。
阅读更多2024-09-24
DC-DC选型
Buck、Boost、Buck-boost同步非同步隔离与非隔离电源效率模式选择选型总结
阅读更多2024-09-24
OpenAI GPT-3 API: What is the difference between davinci and text-davinci-003?
OpenAI GPT-3 API：davinci 和 text-davinci-003 有什么区别
阅读更多2024-09-24
C语言内存函数
仔细想一下，就能知道当把1、2先拷贝放到arr+2和arr+3的地址处，其实原来数组的3和4就被1和2覆盖了，所以之后再来拷贝arr1+2和arr1+3地址处的元素到arr1+4和arr1+5所指向的
阅读更多2024-09-24
实现HTML两栏布局
是一个弹性单位，代表“分数”，它会根据剩余空间的比例来分配宽度。：表示第二列会占据剩余的所有空间。浮动 + margin。
阅读更多2024-09-24
MyBatis-Plus 实体类注解
如果逻辑删除标记的值不为 0 和 1，可以通过全局配置进行自定义。db-config:logic-not-delete-value: 0 # 未删除的值logic-delete-value: 2 #
阅读更多2024-09-24
Matplotlib-数据可视化详解
可视化介绍数据可视化是指直观展现数据，它是数据处理过程的一部分。把数值绘制出来更方便比较。借助数据可视化，能更直观地理解数据，这是直接查看数据表做不到的数据可视化有助于揭示数据中隐藏的模式，数据分析时
阅读更多2024-09-24

面向对象程序设计——mapの简析

1.map的定义

1.1map的构造

2.pair

3.map的增删查

3.1插入

3.2删除

3.3查找

4.operatpr[]间接实现增删查改

5.multimap和map的差异

6.实战代码练习

相关文章