7
\$\begingroup\$

Recently came upon this question asked in interview with major tech company.

Implement Java's next and hasNext function in your favorite programming language.

Here is the solution I came up with. I am not sure whether next() is implemented correctly. Here is the iterator documentation.

#include <iostream>
#include <vector>
#include <string>

template <class T>
class iterator {
public:
    iterator() {}
    iterator(std::vector<T> vec) {
        container = vec;
    }
    bool hasNext() {
        if (curr_pos == container.size()) {
            return false;
        } else {
            if (curr_pos < container.size()) {
                return true;
            }
        }
        return false;
    }
    T next(){
        if (hasNext()) {
            curr_pos += 1;
            return container.at(curr_pos-1);    
        }
    }
private:
    std::vector<T> container;
    int curr_pos = 0;
};

int main() {
    std::vector<int> int_vec {1,2,3,4};
    iterator<int> int_it(int_vec);
    while (int_it.hasNext()) {
        std::cout << int_it.next() << " ";
    }

    std::cout << std::endl;

    std::vector<std::string> str_vec {"a", "b", "c","d"};
    iterator<std::string> str_it(str_vec);
    while(str_it.hasNext()) {
        std::cout << str_it.next() << " ";
    }
    std::cout << std::endl;
    std::vector<int> empty_vec;
    iterator<int> empty_it(empty_vec);
    while(empty_it.hasNext()) {
        std::cout << empty_it.next() << " ";
    }
    return 0;
}

Here is the working version of the above code.

\$\endgroup\$

2 Answers 2

Reset to default
8
\$\begingroup\$

I see some things that may help you improve your code.

Make sure all control paths return

Within your implementation of next(), what happens if hasNext() is not true? The calling function will be expecting a type T but it won't get anything. This should be addressed.

Consider throwing an error

The Java version of next() throws a NoSuchElementException if there are no more elements. You could reproduce this behavior by actually deleting code (which would also address the above issue):

T next(){
    return container.at(curr_pos++);    
}

This works because at throws a std::out_of_range error if there are no further items.

Think carefully about signed vs. unsigned

The curr_pos member does not have a reasonable interpretation for negative values, so it would make more sense to declare it unsigned rather than int.

Prefer modern initializers for constructors

The constructor could be written using the more modern parameter intialization style. That version would look like this:

iterator(std::vector<T> vec) 
    : container{vec}, curr_pos{0} 
{}

Use const where practical

The current hasNext() routine does not (and should not) modify the underlying object, and so it should be declared const:

bool hasNext() const { /* code */ }

Simplify expressions

The hasNext() routine is overly complex. It could instead be this single line:

bool hasNext() const {
    return curr_pos < container.size();
}

Use const references where practical

The constructor could and should take a const reference to avoid a copy and to preserve flexibility. You could also use default parameters to eliminate the no-argument constructor:

iterator(const std::vector<T> &vec = {}) 
    : container{vec}, curr_pos{0} 
{}

Consider providing an initializer list constructor

The code has a few versions of something like this:

std::vector<int> int_vec {1,2,3,4};
iterator<int> int_it(int_vec);

It would be convenient to instead be able to write this:

iterator<int> int_it{1,2,3,4};

Here is a constructor that will allow that usage:

iterator(const std::initializer_list<T>& v) 
    : container{v}, curr_pos{0} 
{}
\$\endgroup\$
6
\$\begingroup\$

My code review issues

  • You implemented your iterator only for std::vector. From Java documentation (http://docs.oracle.com/javase/7/docs/api/java/util/Collection.html see All Known Implementing Classes) I assume it must be also available for other containters. So the main problem is that your iterator only works with std::vector but I think it must work with other C++ containers too. As a result the type of the container must be the template parameter and your iterator must wotk with std::deque, std::list, std::map, std::unordered_map, std::set and so on.

  • Your code actually does not impement fully Interface Iterator<E>. See methods for Interface Iterator<E>:

    boolean     hasNext();
E           next()
void        remove()

    You implemented only hasNext() and next(). Why not implement remove() even though it is optional?

  • Then, you make a deep copy of std::vector. However from the quoted below phrase I assume that your iterator should instead store lvalue reference to the container and not copy it:

    Removes from the underlying collection the last element returned by this iterator

  • T next() is likely has to be T& next() since there is no point in copying value and Java itself (in my opinion) does not copy element in next()

  • You broke the specification here:

    T next()
{
    if (hasNext()) {
        curr_pos += 1;
        return container.at(curr_pos-1);    
    }
}

    What Java iterator promises: 

    Throws:
NoSuchElementException - if the iteration has no more elements

    Your code in that case does not throw - this is a difference with the spec. You should have thrown an exception. 

    T next()
{
    if (hasNext()) {
        curr_pos += 1;
        return container.at(curr_pos-1);    
    }
    throw std::runtime_error("the iteration has no more elements");
}

  • You could have added make_iterator function to create iterators in this way:

    auto int_it = make_iterator(int_vec);

google codestyle code review issues

google codestyle analyzer (https://github.com/google/styleguide) found this issues in your code: 

>python "styleguide\cpplint\cpplint.py" main.cpp
main.cpp:7:  public: should be indented +1 space inside class iterator  [whitespace/indent] [3]
main.cpp:9:  Single-parameter constructors should be marked explicit.  [runtime/explicit] [5]
main.cpp:22:  Missing space before {  [whitespace/braces] [5]
main.cpp:25:  Line ends in whitespace.  Consider deleting these extra spaces.  [whitespace/end_of_line] [4]
main.cpp:28:  private: should be indented +1 space inside class iterator  [whitespace/indent] [3]
main.cpp:28:  "private:" should be preceded by a blank line  [whitespace/blank_line] [3]
main.cpp:34:  Missing space after ,  [whitespace/comma] [3]
main.cpp:42:  Missing space after ,  [whitespace/comma] [3]
main.cpp:44:  Missing space before ( in while(  [whitespace/parens] [5]
main.cpp:50:  Missing space before ( in while(  [whitespace/parens] [5]

My attempt

#include <iostream>
#include <vector>
#include <deque>
#include <list>
#include <stdexcept>

template <class T>
class java_iterator {
 public:
    explicit java_iterator(T* container)
      : container(container), current(container->begin()) {
      }

    bool hasNext() {
        return current != container->end();
    }

    typename T::value_type& next()  {
        if (current != container->end())
            return *current++;
        else
            throw std::runtime_error("the iteration has no more elements");
    }

 private:
    T* container;
    typename T::iterator current;
};

template <class T>
java_iterator<T> make_java_iterator(T* container) {
    return java_iterator<T>(container);
}

int main() {
    {
        std::vector<int> int_vec {1, 2, 3, 4};
        java_iterator<decltype(int_vec)> int_it(&int_vec);
        while (int_it.hasNext()) {
            std::cout << int_it.next() << " ";
        }
        std::cout << std::endl;
    }

    try {
        std::vector<int> int_vec {1, 2, 3, 4};
        java_iterator<decltype(int_vec)> int_it(&int_vec);
        while (true) {
            std::cout << int_it.next() << " ";
        }
        std::cout << std::endl;
    }
    catch (std::exception& e) {
        std::cout << e.what() << std::endl;
    }

    {
        std::vector<int> int_vec {1, 2, 3, 4};
        auto int_it = make_java_iterator(&int_vec);
        while (int_it.hasNext()) {
            std::cout << int_it.next()  << " ";
        }
        std::cout << std::endl;
    }

    {
        std::deque<int> int_vec {1, 2, 3, 4};
        java_iterator<decltype(int_vec)> int_it(&int_vec);
        while (int_it.hasNext()) {
            std::cout << int_it.next() << " ";
        }
        std::cout << std::endl;
    }

    {
        std::list<int> int_vec {1, 2, 3, 4};
        java_iterator<decltype(int_vec)> int_it(&int_vec);
        while (int_it.hasNext()) {
            std::cout << int_it.next() << " ";
        }
        std::cout << std::endl;
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.