Simple C++ solution (1 line per method) without extra member variables


  • 63
    E

    Since Iterator has a copy constructor, we can just use it:

    class PeekingIterator : public Iterator
    {
    public:
        PeekingIterator(const vector<int> &nums) : Iterator(nums)
        {
        }
    
        int peek()
        {
            return Iterator(*this).next();
        }
    
        int next()
        {
            return Iterator::next();
        }
    
        bool hasNext() const
        {
            return Iterator::hasNext();
        }
    };

  • 0

    Amazingly concise solution! I know too few about classes in C++ to come up with such a nice solution.


  • 7

    Haha, this is amazing. Am I right in thinking that this won't work for iterators where the copy's next would consume data of the original (and vice versa), but that in such cases, the iterator shouldn't offer a copy constructor in the first place?

    Also, the copy constructor might take linear time, right? I mean, if it copied all the data?


  • 0

    I guess Stefan's second thought is right. Due to the copy each time we call peek, the running time of this method takes 4ms while the one without copying takes only 0ms.


  • 0
    E

    Another thing to consider: many solutions are based on the assumption that the values do not change. Can we make such an assumption? I mean, if the next value is changed between a peek call and a next call, the cached value would be invalidated, right?


  • 0

    @jianchao.li.fighter Nah, the copy constructor here only takes constant time, only copies a pointer and an index.

    @efanzh Yes, but I think that's ok. Your solution is in a unique position, being able to ask the original iterator multiple times for the same element. In Java and Python it's impossible. The problem setter's own C++ solution doesn't do it, either. So if anything, your solution is the outlier, the one with the wrong (i.e., unintended) behaviour :-P. But good point, and a nice advantage of your solution for someone who does want that behaviour.


  • 0
    P

    @StefanPochmann Can you explain this in detail? If copy constructor does not return a new object but only copies a pointer, how it works by calling next() by Iterator(*this).next()?


  • 0
    E

    @peteraristo Iterator(*this) makes a copy of current iterator, then call next on the copied iterator to get the next value without affecting current iterator.


  • 0

    I'm a little confused. "this" points to a PeekingIterator instance, and the constructor of Iterator accepts an instance of PeekingIterator. So we can copy-construct a superclass with a subclass instance? Only the members belong to the superclass in the subclass instance are used to construct a superclass instance? Is my reasoning correct? Anyway, upvoted for this mastery of C++.


  • 1

    @peteraristo It creates a new iterator object, but the internal pointer+index get copied (and then the index of the copy gets increased while the index of the original stays the same).


  • 0
    Y

    @luming89 yes, as you can see, the copy constructor in the base class Iterator accept a base class type pointer. As in C++, we can use base class pointer or reference to refer derived object. A derived class contains all the information contained in the base class, so it certainly can be used to construct a base object.


  • 0
    X

    this solution is based on the following assumption:
    Iterator::next() modify "data" itself, not the object which pointed by "data".


  • 0
    C

    Hi StefanPochmann, the base class Iterator has not implemented any constructor "Iterator(const vector<int>& nums)", so why "PeekingIterator(const vector<int>& nums) : Iterator(nums)" can be compiled? I am a little confused.


  • 0
    D
    This post is deleted!

  • 0
    L

    Can anybody check my code? I think I write the correct code but why the OJ always indicates this error: Line 22: no matching function for call to ‘Iterator::Iterator()
    Thanks.

    class Iterator {
        struct Data;
    	Data* data;
    public:
    	Iterator(const vector<int>& nums);
    	Iterator(const Iterator& iter);
    	virtual ~Iterator();
    	// Returns the next element in the iteration.
    	int next();
    	// Returns true if the iteration has more elements.
    	bool hasNext() const;
    };
    
    
    class PeekingIterator : public Iterator {
    private:
        Iterator dummy;
        int nextValue = 0;
    public:
    	PeekingIterator(const vector<int>& nums) : Iterator(nums) {
    	    // Initialize any member here.
    	    // **DO NOT** save a copy of nums and manipulate it directly.
    	    // You should only use the Iterator interface methods.
    	    dummy = Iterator(nums);
    	    if (hasNext()) {
    	        nextValue = dummy.next();
    	    }
    	}
    
        // Returns the next element in the iteration without advancing the iterator.
    	int peek() {
            return nextValue;
    	}
    
    	// hasNext() and next() should behave the same as in the Iterator interface.
    	// Override them if needed.
    	int next() {
    	    int temp = nextValue;
    	    if (dummy.hasNext()) {
    	        nextValue = dummy.next();
    	    }
    	    Iterator::next();
    	    return temp;
    	}
    
    	bool hasNext() const {
    	    return Iterator::hasNext();
    	}
    };

  • 0
    C

    Since it create a new iterator object, will that be a waste of memory?


  • 0
    E

    @CeciliaChen The newly created iterator will be destroyed immediately, so I don't think that's a problem.


  • 0
    C

    you cannot declare Iterator dummy, because no default constructor of class Iterator.


  • -1
    C

    利用了复制构造函数,非常机智!


  • 0
    H

    Very concise solution! Although it creates a nother Iterator object with the copy constructor when peek() is called, the extra cost is quite small, because the iterator object only has a pointer and several functions.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.