运算符重载的问题

Question

运算符重载的问题

7

我有两个关于运算符重载的问题。

对于迭代器类型，如何重载operator->？假设它是一个用于class T对象集合的迭代器，应该返回什么值？
为什么operator++()通过class T&返回，而operator++(int)通过class T返回？我知道这两个代表前缀递增和后缀递增。但为什么返回值不同？

编辑：针对Alf的代码尚未完整，但已具有功能。欢迎提出改进意见。

#ifndef DHASH_H
#define DHASH_H

//#include <vector>
#include <memory>
#include <exception>
#include <new>
#include <algorithm>
#include <functional>

namespace MCol
{
    template <typename KEY, typename VALUE, typename HASH_FUNCTION, typename KEY_COMP = std::equal_to<KEY> >
        class hash_container
        {
            private:
                struct entry
                {
                    KEY _k;
                    VALUE _v;

                    entry(const KEY& k, const VALUE& v)
                        :_k(k), _v(v)
                    {}

                    entry& operator=(const entry& e)
                    {
                        this->_k = e._k;
                        this->_v = e._v;
                    }
                };

            private:
                struct bucket
                {
                    entry* a_Entries;
                    size_t sz_EntryCount;   

                    bucket()
                    {
                        sz_EntryCount = 0;
                        a_Entries = NULL;
                    }

                    ~bucket()
                    {
                        for(size_t szI = 0; szI < sz_EntryCount; ++szI)
                        {
                            a_Entries[szI].~entry();
                        }
                        free(a_Entries);
                    }

                    //Grow by 1. (Perhaps later try block increment. But wikipedia suggests that there is little difference between the two)
                    inline bool insert(const KEY& k, const VALUE& v) throw (std::bad_alloc)
                    {
                        if(find(k) != NULL)
                        {
                            return false;
                        }
                        a_Entries = static_cast<entry*>(realloc(a_Entries, sizeof(entry)*(++sz_EntryCount)));
                        if(a_Entries == NULL)
                        {
                            throw std::bad_alloc();
                        }

                        new (&a_Entries[sz_EntryCount - 1]) entry(k, v);
                        return true;
                    }

                    //Find entry, swap with last valid entry, remove if necessary.
                    inline bool erase(const KEY& k) throw(std::bad_alloc)
                    {
                        //Forwards or backwards? My guess is backwards is better.
                        entry* pE = a_Entries;
                        while(pE != a_Entries + sz_EntryCount)
                        {
                            if(pE->_k == k)
                            {
                                break;
                            }
                            ++pE;
                        }

                        if(pE == a_Entries + sz_EntryCount)
                        {
                            return false;
                        }

                        //We don't need to swap if the entry is the only one in the bucket or if it is the last one.
                        entry* pLast = a_Entries + sz_EntryCount - 1;
                        if((sz_EntryCount > 1) && (pE != pLast))
                        {
                            pE = pLast;
                        }

                        a_Entries = static_cast<entry*>(realloc(a_Entries, sizeof(entry)*(--sz_EntryCount)));
                        if(a_Entries == NULL && sz_EntryCount > 0)
                        {
                            throw std::bad_alloc();
                        }

                        return true;
                    }

                    inline entry* find(const KEY& k) throw()
                    {
                        //Better implement a search policy.
                        entry* pE = a_Entries;
                        while(pE != a_Entries + sz_EntryCount)
                        {
                            if(pE->_k == k)
                            {
                                break;
                            }
                            ++pE;
                        }

                        if(pE == a_Entries + sz_EntryCount)
                        {
                            return NULL;
                        }

                        return pE;
                    }
                };

                HASH_FUNCTION& _hf;
                KEY_COMP _kc;

                size_t sz_TableSize;
                double d_MultFactor;                                            //Recalculate this as 1/sz_TableSize everytime sz_TableSize changes.
                size_t sz_NextResizeLimit;
                size_t sz_EntryCount;
                double d_ExpectedLoadFactor;
                double d_CurrentLoadFactor;

                //If the load factor is relatively high (say >0.5 assuming sizeof(entry) == 2*sizeof(size_t)), it is more space efficient to keep a straight bucket array. But if the load factor is low, memory consumption would be lower if a pointer array of Entries is used here. But, because we would not be much concerned with a little additional memory being used when there are few entries, I think array of bucket objects is better. Further, it bypasses a pointer lookup. May have to reconsider is a situation where multiple hash tables are used (Perhaps as an array).
                bucket* a_Buckets;


                hash_container(const hash_container&);
                hash_container& operator=(const hash_container&);

                inline void calculateMultFactor() throw()
                {
                    d_MultFactor = 1.0f/static_cast<double>(sz_TableSize + 1);
                    //sz_NextResizeLimit = static_cast<size_t>(d_ExpectedLoadFactor*sz_TableSize);
                    //Have a look at this.
                    //TODO
                }

                void resize(size_t szNewSize) throw(std::bad_alloc)
                {
                    if(szNewSize == 0)
                    {
                        szNewSize = 1;
                    }
                    size_t szOldSize = sz_TableSize;
                    for(size_t szI = szNewSize; szI < szOldSize; ++szI)
                    {
                        a_Buckets[szI].~bucket();
                    }

                    a_Buckets = static_cast<bucket*>(realloc(a_Buckets, sizeof(bucket)*szNewSize));
                    if(a_Buckets == NULL)
                    {
                        throw std::bad_alloc();
                    }
                    //Unnecessary at the moment. But, just in case that bucket changes.
                    for(size_t szI = szOldSize; szI < szNewSize; ++szI)
                    {
                         new (&a_Buckets[szI]) bucket();
                    }

                    sz_TableSize = szNewSize;
                    calculateMultFactor();
                }

                inline bucket* get_bucket(const KEY& k) throw()
                {
                    return a_Buckets + _hf(k, sz_TableSize);
                }

                inline bool need_resizing() const throw()
                {

                }
            public:
                //typedef iterator void*;
                //typedef const_iterator void*;

                //iterator Insert(KEY& k, VALUE& v);
                //VALUE& Find(Key& k);
                //const VALUE& Find(Key& k);
                //iterator Find(KEY k);
                //const_iterator Find(KEY k);
                //void Delete(KEY& k);
                //void Delete(iterator it);
                //void Delete(const_iterator it);
                class iterator
                {
                    private:
                        entry* p_Entry;
                        bucket* p_Bucket;

                        friend class bucket;

                    public:
                        iterator(entry* pEntry)
                            :p_Entry(pEntry)
                        {
                        }

                        iterator()
                        {
                            p_Entry = NULL;
                        }

                        iterator(const iterator& it)
                        {
                            this->p_Entry = it.p_Entry;
                        }

                        inline VALUE& operator*() const
                        {
                            return p_Entry->_v;
                        }

                        inline bool operator==(const iterator& it) const
                        {
                            return this->p_Entry == it.p_Entry;
                        }

                        inline bool operator!=(const iterator& it) const
                        {
                            return !(*this == it);
                        }

                        inline iterator& operator=(const iterator& it)
                        {
                            this->p_Entry = it.p_Entry;
                        }

                        inline VALUE* operator->() const
                        {
                            return &p_Entry->_v;
                        }

                        inline iterator operator++()
                        {
                            return *this;
                        }

                        inline iterator& operator++(int)
                        {
                            //WRONG!!!
                            //TODO : Change this.
                            return *this;
                        }
                };

            private:
                iterator _EndIt;

            public:
                hash_container(HASH_FUNCTION& hf, size_t szTableSize = 1024, double dLoadFactor = 0.7f, KEY_COMP kc = KEY_COMP())throw(std::bad_alloc)
                    :_hf(hf), sz_TableSize(szTableSize), d_ExpectedLoadFactor(dLoadFactor), _kc(kc)
                {
                    if(d_ExpectedLoadFactor < 0.1f)
                    {
                        d_ExpectedLoadFactor = 0.1f;
                    }

                    a_Buckets = NULL;
                    sz_TableSize = 0;
                    if(szTableSize == 0)
                    {
                        szTableSize = 1;
                    }
                    resize(szTableSize);
                    d_CurrentLoadFactor = 0.0f;
                    sz_EntryCount = 0;

                    _EndIt = iterator(NULL);
                }

                virtual ~hash_container()
                {
                    for(size_t szI = 0; szI < sz_TableSize; ++szI)
                    {
                        a_Buckets[szI].~bucket();
                    }
                }

                inline iterator find(const KEY& k) throw()
                {
                    bucket* pBucket = get_bucket(k);
                    return pBucket->find(k);
                }

                inline bool insert(const KEY& k, const VALUE& v) throw(std::bad_alloc)
                {
                    bucket* pBucket = get_bucket(k);
                    bool bRet = false;
                    try
                    {
                        bRet = pBucket->insert(k, v);
                    }
                    catch(std::bad_alloc& e)
                    {
                        //What now?
                        throw e;
                    }
                    if(bRet == true)
                    {
                        ++sz_EntryCount;
                    }
                    return bRet;
                }

                inline VALUE& operator[](const KEY& k) throw(std::bad_alloc)
                {
                    bucket* pBucket = get_bucket(k);

                }

                inline bool erase(const KEY& k) throw(std::bad_alloc)
                {
                    bucket* pBucket =  get_bucket(k);
                    bool bRet = false;
                    try
                    {
                        bRet = pBucket->erase(k);
                    }
                    catch(std::bad_alloc& e)
                    {
                        throw e;
                    }
                    if(bRet == true)
                    {
                        --sz_EntryCount;
                    }
                    return bRet;
                }

                inline iterator end() const
                {
                    return _EndIt;
                }

                inline size_t size() const
                {
                    return sz_EntryCount;
                }

                inline size_t table_size() const
                {
                    return sz_TableSize;
                }

                inline double current_load_factor() const
                {
                    return d_MultFactor*static_cast<double>(sz_EntryCount);
                }

                inline double expected_load_factor() const
                {
                    return d_ExpectedLoadFactor;
                }
        };
}

#endif

- nakiya

这看起来像是一道作业题。请修改你的问题标题，加上“作业”这个词。 - Cheers and hth. - Alf

3

对我来说，这似乎不是作业。看起来他对如何实现迭代器很好奇。 - Benjamin Lindley

1

@ Alf P. Steinbach ：不是作业。我正在为哈希表实现迭代器。 - nakiya

看起来像是作业。它从错误的角度开始。例如，要询问如何重载operator->，就需要知道operator->已被重载。如果不知道那个问题的答案，就无法知道。所以，这是作业。抱歉，@nakiya。 - Cheers and hth. - Alf

@Alf P. Steinbach：什么？那听起来好像是刻意为之。也许你想要代码？:p。等我发一下。 - nakiya

OP已经声明这不是作业。接受这一点，进一步讨论是毫无意义的。要么回答问题，要么继续下一个问题。 - Martin York

3个回答

1

对于迭代器类型，如何重载 operator-> 运算符？

它不可以。operator->运算符只能在类类型上进行重载。

如果您的意思是“我该如何将其重载以返回整数类型”，那么答案是不能。operator->的结果本身被取消引用，因此必须是指针类型（或重载operator->()的类类型对象（引用））。

如果这是一个T类对象集合的迭代器，它应该返回什么值？

它将返回指向 T 的指针。

struct Y { int a; };
std::vector<Y> plop(/* DATA TO INIT*/);

std::vector<Y>::iterator b = plop.begin();
b->a = 5; // here b.operator->() returns a pointer to Y object.
          // This is then used to access the element `a` of the Y object.

为什么operator++()返回class T&，而operator++(int)返回class T？

从技术上讲，它们可以返回任何东西。但通常它们是按照您建议的方式实现的。

这是因为这些方法的标准实现：

class X
{
     public:
         // Simple one first. The pre-increment just increments the objects state.
         // It returns a reference to itself to be used in the expression.
         X& operator++()
         {
              /* Increment this object */
              return *this;
         }

         // Post Increment: This has to increment the current object.
         // But the value returned must have the value of the original object.
         //
         // The easy way to do this is to make a copy (that you return). The copy
         // has the original value but now is distinct from this. You can now use
         // pre-increment to increment this object and return the copy. Because
         // the copy was created locally you can not return by reference.
         X operator++(int)
         {
             X  copy(*this);
             ++(*this);
             return copy;
         }
};

我理解这两个代表前缀递增和后缀递增。但为什么返回值不同呢？

请参见上面代码中的注释。

- Martin York

0

operator-> 应该返回类型为 T 的指针（即 T*）。
后缀递增必须返回值的副本，因为它执行递增操作，但在使用该值之前。前缀递增可以在递增后简单地返回 *this。

简单的实现可能如下所示：

T T::operator++(int)
{
    T temp = *this;
    ++*this;
    return temp;
}

T& T::operator++()
{
    this->value += 1;
    return *this;
}

- Zooba

我对 operator-> 感到困惑。如果它返回 class T*，那么使用方式不应该是这样的吗：collection<T>::iterator it; it.operator->()->member = x;？还是我理解错了？ - nakiya

1

不要显式地调用操作符。只需编写 it->member = x。编译器会自动生成对 it 上的 operator-> 的调用以获取 T*，然后将内置的 -> 逻辑应用于其上。 - Karl Knechtel

@ Karl Knechtel：我猜这就是答案。我想知道那个额外的 -> 去哪了。 - nakiya

@nakiya 返回 T* 的唯一替代方案是 T&，而在重载 -> 运算符的能力之后才添加了引用（这也是为什么 this 不是引用的原因）。编译器将 a->b 重写为 (*T::operator->(a)).b，这要求返回值是一个指针。如果 C++ 被“重新启动”，它可能会返回一个引用。 - Zooba

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- aschepler · Accepted Answer

.1. operator-> 应该几乎总是返回一个指针类型。当作为具有 value_type T 的迭代器时，它应该返回 T*。

在一些更罕见的情况下，operator-> 可能会返回一个不同的类类型，该类类型还具有一个 operator-> 成员函数。

.2. 对于 operator++ 的任何形式，都没有技术要求，但通常的惯例使它们最像内置意义。

class T {
public:
    // pre-increment
    T& operator++() { increment_me(); return *this; }
    // post-increment
    T operator++(int) { T copy(*this); increment_me(); return copy; }
    //...
};

内置的前缀自增表达式++x的含义是先将数字加1，然后返回一个对增加后数字的左值引用。返回类型T&的作用类似。

内置的后缀自增表达式'x++'会增加变量的值，但返回变量先前值的rvalue副本。因此，大多数用户定义的重载函数会返回原始值的副本（几乎永远不可能是引用）。