首页 > 其他分享 >STL-RBT_map,set模拟实现

STL-RBT_map,set模拟实现

时间:2024-02-27 22:56:18浏览次数:21  
标签:map set const iterator insert STL key pair return

set

#include"26RBT_container.h"
namespace test
{
    //set通过普通迭代器使用const迭代器实现限制key不能被修改

    template<class K>
    class set
    {

    private:
        struct setKeyOfT//命名? 返回RBT的类型T接收的 set的key
        {
            const K& operator()(const K& key) //类似函数重载
            {
                return key; //返回key --重载原函数
            }
        };
    private:
        RBTree< K, K, setKeyOfT>_t;
    public:
        //使用类域的要加typename,以防和静态变量冲突
        typedef typename RBTree<K, K, setKeyOfT>::const_iterator iterator; //普通迭代器
        typedef typename RBTree<K, K, setKeyOfT>::const_iterator const_iterator; //const迭代器
    /**
     * set中因为key不能修改,所以RBT的模板参数T位置需要是const K,但是,const迭代器中的是const T,使用const K的话会const迭代器变成const const K
     * 解决:set的普通迭代器也使用const迭代器
     *
     */

        iterator begin()
        {
            return _t.begin(); //begin是普通迭代器,返回值是const,发生隐式类型转换(单参数)
            //如果有相应的构造函数,则支持隐式类型转换 ,但此时迭代器没有参数为迭代器的构造函数,需要添加
            //
        }
        iterator end()
        {
            return _t.end();
        }

        const_iterator begin()const
        {
            return _t.begin();
        }
        const_iterator end()const
        {
            return _t.end();
        }

        

    public:
        pair<iterator, bool> insert(const K& key)
        {
            return _t.insert(key);
        }


    };

    void test_mySet1()
    {
        test::set<int> s;
        s.insert(2);
        s.insert(1);
        s.insert(3);

        set<int>::iterator it = s.begin();
        //while (it!=s.end())
        //{
        //    cout << *it << " ";
        //    ++it;
        //}
        for (auto& e : s)
        {
            cout << e << " ";
        }
        cout << *++it << " ";
        cout << *--it << " ";
        cout << endl;
        //*it = 1;////不允许赋值,表达式必须是可以修改的左值 .不能给常量赋值
        

    }
}

map:

#pragma once

#include"26RBT_container.h"
namespace test
{
    template<class K,class V>
    class map
    {

        //map通过pair中的const K 限制了Key不能被修改

    private:
        struct mapKeyOfT//命名? 返回RBT的类型T接收的 map的key
        { 
            const K& operator()(const pair<const K,V>& kv) //类似函数重载
            {
                return kv.first; //返回pair的key
            }
        };
    private:
        RBTree<K, pair<const K, V>, mapKeyOfT> _t;
    public:
        typedef typename RBTree<K, pair<const K,V>, mapKeyOfT>::iterator iterator; //使用类域的要加typename,以防和静态变量冲突

        iterator begin()
        {
            return _t.begin();
        }
        iterator end()
        {
            return _t.end();
        }

    public:
        pair<iterator,bool> insert(const pair<const K, V>& kv)
        {
            return _t.insert(kv);
        }

        V& operator[](const K& key)
        {
            pair<iterator,bool> ret = insert(make_pair(key, V()));
            return ret.first->second;
        }

    };

    void test_myMap1()
    {
        test::map<int, int> m;
        m.insert(std::make_pair(1, 1));
        m.insert(std::make_pair(3, 3));
        m.insert(std::make_pair(2, 2));
        test::map<int,int>::iterator it = m.begin();
        //while (it != m.end())
        //{
        //    cout << it->first << " ";
        //    ++it;
        //}
        for (auto e : m)
        {
            cout << e.first << " ";
        }

        cout << (++it)->first << " ";
        cout << (--it)->first << " ";
        cout << endl;

        //it->second = 1; //可以赋值
        //it->first = 1;//不允许赋值,表达式必须是可以修改的左值 .不能给常量赋值
    }

    void test_myMap2()
    {
        //map的使用
        map<std::string, std::string>  dict;
        dict.insert(std::pair<std::string, std::string>("sort", "排序")); //匿名对象插入
        dict.insert(std::make_pair("string", "字符串"));    //pair封装插入
        dict.insert(std::make_pair("count", "计数"));
        dict.insert(std::make_pair("count", "(计数)")); //插入失败的
        auto it = dict.begin();
        while (it != dict.end())
        {
            cout << it->first << ":" << it->second << endl;
            ++it;
        }
    }

    void test_myMap3()
{
    std::string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜","苹果", "香蕉", "苹果", "香蕉" };
    map<std::string, int> countMap;
    /*for (auto e : arr)
    {
        auto ret = countMap.find(x);
        if (ret==countMap.end())
        {
            countMap.insert(std::pair<string, int>(x, 1));
        }
        else
        {
            ++ret->second;
        }
    }*/

    for (auto& e : arr)
    {
        ++countMap[e];
    }

    for (auto& s : countMap)
    {
        cout <<  s.first << ":" << s.second << endl;
    }
    

}

}

 

标签:map,set,const,iterator,insert,STL,key,pair,return
From: https://www.cnblogs.com/DSCL-ing/p/18038625

相关文章

  • STL-bitset模拟实现
    #include<time.h>#include<string>#include<vector>#include<iostream>usingstd::cout;usingstd::endl;usingstd::string;namespacetest{/**位图概念*所谓位图,就是用每一位来存放某种状态,适用于海量数据,数据无重复的场景。通常是用来判断某个数据存不存在的。......
  • STL-priority_queue模拟实现
    #include<deque>//测试用#include<vector>//测试用#include"9Date.h"//测试用#include<iostream>usingstd::cout;usingstd::endl;usingstd::cin;namespacetest{template<classT>structless{booloperator()(constT&......
  • STL-string模拟实现
    1#pragmaonce23#include<iostream>4#include<string.h>5#include<assert.h>6usingstd::cout;7usingstd::endl;8usingstd::cin;9namespacetest{1011classstring{12//friendstd::ostream&......
  • C++ STL 容器 forward_list类型
    C++STL容器forward_list类型介绍std::forward_list是C++标准模板库(STL)中的一个单向链表容器。与std::list不同,std::forward_list只允许从头部到尾部的单向迭代,不支持反向迭代。因此,std::forward_list在某些操作上可能比std::list更高效,尤其是在插入和删除元素时......
  • STL-vector模拟实现
    #pragmaonce#include<assert.h>#include<iostream>usingstd::cout;usingstd::endl;usingstd::cin;namespacetest{//#include<algorithm>//模板参数省略:1.作为时2.作为类型名template<classT>//数组名:类型名:xx数组classvector......
  • STL-list模拟实现
    #pragmaonce#include"16my_Itetator.h"//测试用#include<iostream>//测试用usingstd::cout;usingstd::endl;usingstd::cin;namespacetest{//struct默认权限是public,一般也不会加权限,class才会(需要封装时使用class)//结点使用struct的好处是开放结点,......
  • STL-stack模拟实现
    #pragmaonce#include<assert.h>#include<list>#include<vector>#include<deque>#include<iostream>usingstd::cout;usingstd::endl;usingstd::cin;namespacetest{//template<classT,classContainers=std::vector&......
  • STL-queue模拟实现
    #include<list>#include<assert.h>#include<deque>#include<iostream>usingstd::cout;usingstd::endl;usingstd::cin;namespacetest{//template<classT,classContainers=std::list<T>>template<classT,c......
  • C++ STL 容器 list类型
    C++STL容器list类型list对于异常支持很好,要么成功,要么不会发生什么事情以下是std::list在异常处理方面表现良好的几个原因:动态内存管理:std::list使用动态内存分配来存储元素,这意味着它会在需要时自动分配内存,并在不再需要时释放内存。这种自动管理可以减少内存泄漏和悬......
  • C++ STL 容器-Deque
    C++STL容器-Dequestd::deque(双端队列)是C++标准模板库(STL)中的一个容器,它支持在序列的两端快速插入和删除元素。与std::vector和std::list等其他序列容器相比,std::deque在某些特定场景下具有独特的优势。元素的访问和迭代比vector慢,迭代器不是普通的指针。以下是std::deque的一......