首页 > 代码库 > map容器设计

map容器设计

在红黑树基础上设计map容器,在设计map时,可以明显利用的map模板类中KEY,VALUE,KEYOFVALUE的灵活运用

不多说,代码如下:

//my_map.h

#ifndef MY_MAP_H_INCLUDED
#define MY_MAP_H_INCLUDED

#include<utility> //for pair
#include"my_rb_tree.h"
using std::pair;
namespace juine
{

    template<class T,class U>
    struct select1st
    {
        T operator()(pair<T,U> tt)
        {
            return tt.first;
        }
    };
    template<class T>
    struct comp
    {
        bool operator()(T v1,T v2)
        {
            return v1<v2;
        }

    };

    template<class Key,class Value,class Alloc=my_alloc >
    class my_map
    {
    public:
        typedef Key key_type;
        typedef pair<Key,Value> value_type;
        typedef RB_Tree<key_type,value_type,select1st<Key,Value>,comp<key_type>,Alloc > rep_type;
    protected:
        rep_type rb_tree;
    public:
        typedef typename rep_type::iterator iterator;

        my_map(){};
        iterator begin()
        {
            return rb_tree.begin();
        }
        iterator end()
        {
            return rb_tree.end();
        }
        iterator insert(pair<Key,Value> p)
        {
            return rb_tree.insert_node(p);
        }
        void erase(iterator pos)
        {
            rb_tree.delete_node(*pos);
        }
        iterator find(Key k)
        {
            return rb_tree.find(k);
        }
        iterator lower_bound(key_type value)
        {
            return rb_tree.lower_bound(value);
        }
        iterator upper_bound(key_type value)
        {
            return rb_tree.upper_bound(value);
        }

        Value& operator[](key_type k)
        {
            Value value;
            pair<Key,Value> p=make_pair(k,value);

            //这个设计的没有STL源码的好,不过也达到了要求
            //刚开始设计时候ions
            iterator iter=insert(p);
            return iter->second;
        }
    };
}

#endif // MY_MAP_H_INCLUDED


测试代码如下:

//test_map.cpp
#include"my_map.h"
#include<iostream>
#include<string>
using namespace std;
using namespace juine;

int main()
{
    my_map<int,string> ss;
    string s[10]={"a","b","c","d","e","f","g","h","i","j"};
    int i;
    for(i=1;i<10;i++)
        ss.insert(make_pair(i,s[i]));
    my_map<int,string>::iterator iter=ss.begin();
    my_map<int,string>::iterator iter1;
    //iter1=ss.upper_bound(6);
    iter=ss.lower_bound(3);
    ss[10]="abcd";
    for(;iter!=ss.end();iter++)
        cout<<iter->first<<"->"<<iter->second<<endl;
    return 0;
}
测试结果: