大学IT网 - 最懂大学生的IT学习网站! QQ资料交流群:367606806
当前位置:大学IT网 > C++技巧 > STL之map原理及实现

STL之map原理及实现(2)

关键词:STLmapmap原理map实现  阅读(4371) 赞(16)

[摘要]本文是对STL之map原理及实现的讲解,对学习C++编程技术有所帮助,与大家分享。

CSortVector和CVector有点类似,只不过CSortVector中的数据在插入的时候需要排序,其他的接口比较相识。CSortVector的关键实现就是二分查找。新增和删除的时候都是通过二分查找,定位到指定的位置,在进行相关操作。这里有必要特意列出二分查找的实现,如下:

        int indexOf(const T& t)
        {
            int begin=0;
            int end=size_-1;
            int index=-1;
            while (begin<=end)
            {
                index=begin+(end-begin)/2;
                if (buf[index]==t)
                {
                    return index;
                }else if (buf[index]<t)
                {
                    begin=index+1;
                }else{
                    end=index-1;
                }
            }
            return -1;
        }


CSortVector测试代码如下:

    void csortvectorTest()
    {
        csortvector<int> l;
        l.add(2);
        l.add(4);
        l.add(9);
        l.add(3);
        l.add(7);
        l.add(1);
        l.add(5);
        l.add(8);
        l.add(0);
        l.add(6);
        cout<<"任意插入一组数据后,自动排序:"<<endl;
        for (int i=0;i<l.size();i++)
        {
            cout<<l[i]<<" ";
        }
        cout<<endl<<endl;

        l.erase(l.begin());
        l.erase(l.end()-1);
        cout<<"删除第一个和最后一个数:"<<endl; 
        for (int i=0;i<l.size();i++)
        {
            cout<<l[i]<<" ";
        } 
        cout<<endl<<endl;

        cout<<"5的下标:"<<l.indexOf(5)<<endl;
        cout<<"下标为3的数:"<<l[3]<<endl;
        l.remove(5);
        cout<<"删除5以后,5的下标是"<<l.indexOf(5)<<endl<<endl;

        cout<<"最后还剩:"<<endl;
        for (int i=0;i<l.size();i++)
        {
            cout<<l[i]<<" ";
        } 
    }


运行结果如下:



注意:由于CSortVector中的元素要排序,所以其中的元素要实现运算符”<”。
介绍完CSortVector,接下来说说CMap。其实CSortVector已经解决CMap的大部分功能了,后者只需要在前者的基础之上简单的封装即可完事。CMap源码如下:

#ifndef _CMAP_H_
#define _CMAP_H_
#include "csortvector.h"
namespace cth
{
    template<typename Key,typename Value>
    struct pair 
    {
        typedef Key first_type;
        typedef Value second_type;
        pair(){}
        pair(const Key& key,const Value& val):first(key),second(val){}
        pair(const pair& other):first(other.first),second(other.second){}
        Key first;
        Value second;
    };

    class NoCopy
    {
    public: 
        inline NoCopy(){}
        NoCopy(const NoCopy&);
        NoCopy& operator=(const NoCopy&); 
    };

    template<typename Key,typename Value>
    class cmap:public NoCopy
    {
    public:
        typedef pair<Key,Value>* iterator;
        typedef const pair<Key,Value>* const_iterator;
        cmap(){}
        int insert(const pair<Key,Value>& item)
        {
            iterator iter=find(item.first);
            if (iter!=end())
            {
                return iter-begin();
            }
            int index=Keys.add(item.first);
            if (index>=0)
            {
                index=Values.insert(Values.begin() + index,item);
            }
            return index;
        }

        int insert(const Key& key,const Value& val)
        {
            pair<Key,Value> item;
            item.first=key;
            item.second=val;
            return insert(item);
        }

        Value& operator[](const Key& key)
        {
            int index=Keys.indexOf(key);
            if (index<0)
            {
                index=insert(key,Value());
            }
            return Values[index].second;
        }

        iterator begin()
        {
            return iterator(&*Values.begin());
        }

        iterator end()
        {
            return iterator(&*Values.end());
        }

        iterator find(const Key& key)
        {
            int index=Keys.indexOf(key);
            if (index<0)
            {
                return end(); 
            }else
            {
                return iterator(&Values[index]); 
            } 
        }

        void erase(const Key& key)
        { 
            int index=Keys.remove(key) ; 
            if (index>=0)
            {
                cvector<pair<Key,Value>>::iterator iter=Values.begin()+index;
                Values.erase(iter);
            } 
        }

        void erase(const_iterator iter)
        { 
            int index=Keys.remove(iter->first) ; 
            if (index>=0)
            {
                cvector<pair<Key,Value>>::iterator iter=Values.begin()+index;
                Values.erase(iter);
            } 
        }

        int size()
        {
            return Keys.size();
        }

        bool empty()
        {
            return Keys.size()==0;
        }

        void clear()
        {
            Keys.clear();
            Values.clear();
        }

    private:
        csortvector<Key> Keys;
        cvector<pair<Key,Value>> Values; 
    };
 
}
#endif


插入操作,CMap的插入操作分两种,一种是通过insert方法;另一种是通过操作符[]。
Insert方法是先找到Key在Keys中的位置,如果已经存在就返回,CMap不允许重复,如果不存在就通过二分查找找到对应的位置,插入Key,并在Values中对应的地方插入Value。
通过操作符[]插入:如m[1]=1;刚开始我也不知道这个是怎么实现的,后来突然明白,操作符[]返回的是一个引用,其实就是给我m[1]的返回值赋值,调用的也是返回值的operator=,CMap只用实现operator[]就行。
其他的方法都是一些简单的封装,这里就不在累赘,最后概述一下CMap的实现:
CMap是基于一个排序数组CSortVector实现的,将Key存入排序数据中,Value和Key通过Pair<Key,Value>存在CVector中,通过二分查找确定某个Key是否存在,不存在就将这个Key插入排序数据中,返回Key在数组中的索引,并将Pair<Key,Value>存在CVector中对应的位置。删除还是通过二分查找寻找,找到就将两个数组中对应的元素删除。

CMap测试代码运行如下:

«上一页12下一页»


相关评论