7

I have two questions about operator overloading.

  1. For an iterator type, how is operator-> overloaded? What value should it return assuming that it is an iterator for a collection of class T objects?

  2. Why does operator++() return by class T& while operator++(int) return by class T? I understand these two represent prefix increment and postfix increment. But why the difference in return value?

EDIT: For Alf. Code is not complete though functioning. Any suggestions for improvement are welcome.

#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
Improve this question
6
  • this looks like homework. please amend your question title to include the word "homework". Commented Jan 19, 2011 at 3:20
  • 3
    Doesn't look like homework to me. It looks like he's curious about how to implement iterators. Commented Jan 19, 2011 at 3:23
  • 1
    @ Alf P. Steinbach : Not homework. I am implementing iterators for a hash table. Commented Jan 19, 2011 at 3:24
  • Looks like homework to me. It starts at the wrong end. For example, to ask about how operator-> is overloaded one needs to know that operator-> is overloaded. Can't know that without knowing the answer to that question. So, homework. Sorry, @nakiya. Commented Jan 19, 2011 at 3:46
  • @Alf P. Steinbach: What? That sounds contrived. Perhaps you want the code? :p. Wait I'll post. Commented Jan 19, 2011 at 3:54

3 Answers 3

Reset to default
3

.1. operator-> should almost always return a pointer type. When acting as an iterator with value_type T, it should return T*.

In some rarer cases, operator-> may return a different class type, which also has an operator-> member function.

.2. There are no technical requirements on what either form of operator++ must return, but the usual conventions make them act most like the built-in meanings.

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

The built-in meaning of the pre-increment expression ++x first increments the number and then returns an lvalue to the incremented number. A return type of T& acts similarly.

The built-in meaning of the post-increment expression 'x++' increments the variable but returns an rvalue copy of the variable's previous value. So most user-defined overloads return a copy of the original value (which can practically never be a reference).

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Same question posed @Zooba : I am confused about operator->. If it returns class T*, doesn't that mean that usage should be like this: collection<T>::iterator it; it.operator->()->member = x;? Or have I got it wrong?
@nakiya: Every overloaded-operator (except new, delete and their array relatives) may be called in short form using the operator itself or in long form using the operator key word. E.g. operator+(x,y) is long for x+y. it.operator->()->member is a correct way of using the long form of your operator-> and it->member is a correct way of using the short form of your operator->.
1

For an iterator type, how is operator-> overloaded?

It's not. The operator-> can only be overloaded on class types.

If you mean "How do I overload it to return an integer type".
Then the answer is you can't. The result of operator-> is itself de-referenced and as such must be a pointer type (or an object(reference) that is a class type with overload operator->()).

What value should it return assuming that it is an iterator for a collection of class T objects?

It will return a pointer to 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.

Why does operator++() return by class T& while operator++(int) return by class T?

Technically they can return anything. But usually they are implemented as you suggested.
This is because of the standard implementation of these methods:

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; } };

I understand these two represent prefix increment and postfix increment. But why the difference in return value?

See comments in above code.

Improve this answer

Comments

0

  1. operator-> should return a pointer to type T (ie. T*).

  2. Postfix increment has to return a copy of the value, since it performs the increment but before the value has been used. Prefix increment can simply return *this after incrementing.

Simple implementations may look like this:

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

4 Comments

I am confused about operator->. If it returns class T*, doesn't that mean that usage should be like this: collection<T>::iterator it; it.operator->()->member = x;? Or have I got it wrong?
Don't call operators explicitly. Just write it->member = x. The compiler automatically generates a call to operator-> on it to get a T*, and then applies the built-in -> logic to that.
@ Karl Knechtel: This is the answer I guess. I wondered where that additional -> disappeared to.
@nakiya The only alternative to returning T* is T&, and references were added after the ability to overload the -> operator (this is also why this is not a reference). The compiler rewrites a->b as (*T::operator->(a)).b, which requires that the return value to be a pointer. If C++ were 're-started' it would probably return a reference.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.