public static Iterable mergeKSortedIterators(List
> Iters){
Queue minHeap = new PriorityQueue();
List result = new ArrayList();
for(Iterator iter : Iters){
if(iter.hasNext()){
minHeap.add(new newIter(iter.next(), iter));
}
}
What is iterator invalidation?
Answer:
Insertion
Sequence containers
vector: all iterators and references before the point of insertion are
unaffected, unless the new container size is greater than the previous
capacity (in which case all iterators and references are invalidated) [23.2.
4.3/1]
deque: all iterators and references are invalidated, unless the inserted
member is at an end (front or back) of the deque (in which case all
iterators are invalidated, but references to elements are unaffe... 阅读全帖
常年用C++，看到两道题要实现iterator
1. class flatten implements iterator{
public flatten(vector> a);
boolean hasNext();
iterator next();
}
2. "Program an iterator for a List which may include nodes or List i.e. *
{0,
{1,2}, 3 ,{4,{5, 6}}} Iterator returns 0 - 1 - 2 - 3 - 4 - 5 - 6"
第一题C++可以实现，第二题除非自己定义node structure，否则感觉无解。主要是C++
里的iterator不能赋NULL，看结束也不能用"iterator==NULL"来判断，得专门维持
collection结束的标识。感觉这种题是专
门给Java的人出的，C++没法搞，起码不能用已有的STL搞，非常坑人。不知道大家有什
么建议。
第一题的C++实现。
class Iterator
{
private:... 阅读全帖
interface是这个 Iterable mergeKSortedIterators(Iterators[] iters)
也就是给每个array的iterator,然后merge.
我开始想的是用merge k sorted list的办法，用一个heap保存所有的iterator,看哪个
iterator的头个element最小,push to result，然后Move to next element。
需要一个iterator的comparator来sort iterators, 是我的comparator写的不对？还
是heap的operation错了？
不知有人做过这题吗，希望给点建议。。。。
public static class iteratorComp implements Comparator>{
public int compare(Iterator a, Iterator b){
int a1 = 0;
in... 阅读全帖
L家最爱考的面试题之一就是nested integer了，
还爱考各种iterator的implementation
这题是把两个最爱合在一起了。。。。感觉很有可能出，但网上没找到满意的答案.
题目是这样的
eg: {{1,2},3,{4,{5,6}}}
不断调用iterator的next()返回的序列是 1 2 3 4 5 6
这个data structure的interface是这样的
public interface Data {
// Does this Data hold a collection?
public boolean isCollection();
// Returns the collection contained by this Data, or null if it is a
single element
public Collection> getCollection();
// Returns the single element contained by this Data, or nul... 阅读全帖
Should java.lang not depend on anything else? Why Iterator not in java.lang
package?
package java.lang;
import java.util.Iterator;
/**
* Implementing this interface allows an object to be the target of
* the "foreach" statement.
*
* @param the type of elements returned by the iterator
*
* @since 1.5
*/
public interface Iterable {
/**
* Returns an iterator over a set of elements of type T.
*
* @return an Iterator.
*/
Iterator iterator();
}
short answer: iterators are generalized pointers. so pointers, by definition
, are iterators.
long answer: there is no iterator "type" or pointer "type". iterator and
pointer are CONCEPTs, which are classes of types (that satisfy some
condition). pointer satisfy all the requirement of iterator so pointer is
iterator.
for implementation, anything suuport "iterator" (or some subclasses of
iterators) must be implemented with template (template is a set of
overloaded functions, so you are right, it ... 阅读全帖
攒了个段子请大牛点评一下:
// Not thread-safe
// Talk about validation requirement: none vs in next() vs in constructor
private static class DeepIterator implements Iterator {
private final Iterator
攒了个段子请大牛点评一下:
// Not thread-safe
// Talk about validation requirement: none vs in next() vs in constructor
private static class DeepIterator implements Iterator {
private final Iterator
//use hasNext() and next() methods of Iterator to iterate through the
elements
System.out.println("Iterating through Vector elements...");
while(itr.hasNext())
System.out.println(itr.next());
谁考你了？
template
class Node{ //used by List
Node(T data, Node* next):_data(data), _next(next){}
T _data;
Node* _next;
friend class List; //only friend can call private
friend class ListIterator;
};
template
class List{
List(Node* head=NULL, Node* tail=NULL);
List(const List& orig);
List& operator=(const List& orig);
push_front();push_end();pop_front();pop_end();
//the following are used for iterator:
typedef ListIterator... 阅读全帖
public class PeekIterator
{
private T data;
Iterator it;
public PeekIterator(Iterator iter) {
it = iter;
data = iter.hasNext()? iter.next():null;
}
public boolean hasNext() {
return data != null;
}
public T next() {
T current = data;
data = it.hasNext()?it.next():null;
return current;
}
public T peek() {
return data;
}
}
That is not the right answer.
In C++, Iterator is a concept. A concept is a set of requirement for
a type. For example, a random access iterator must allow operators
++, +, +=, --, -, -=, [], etc. with the right semantics, while a
forward iterator only needs to have ++. Naked pointers can be
iterators, because they already have these operators built-in.
User-defined types can also be iterators, as long as they overload
required operators correctly.
So the difference between iterator and pointer
I think you can use a pointer to an iterator as below:
typdef vector vi;
void main()
{
int input[] = {1, 4, 5};
vi weight = vi(input, input+sizeof(input)/sizeof(input[0]));
vi::iterator it1 = weight.begin();
vi::iterator it2 = weight.end()-1;
vi::iterator *pit = new vi::iterator;
if(1+1 == 3)
*pit = it1;
else
*pit = it2;
int result = **pit;
delete pit;
cout<
}
是的，这道题考察的就是如何设计iterator, 悲催的是iterator on binary tree, 而
且要求iterate的顺序必须是inorder. 设计iterator on array, linkedlist之类的要
比这个简单一些。即使iterate on binary tree in level order也要简单一些，对我
来说。应该算是一道集design和算法为一体的一道题吧。我面试之前是没有见到过这道
题，不知道是不是常见题。
iterator直接比的话，比较一次之后next的值就丢失了。 可以创建一个新的数据结构
， 包含iterator和当前的值。
public class IterWrapper{
int currentVal;
Iterator iter;
}
Comparator比较currentVal的大小。初始化的时候对每个iterator取next，然后放进
priorityQueue或者heap。
每次IterWrapper被poll之后，更新currentVal的值再放回去就好了。
你是说iterative solution比起recursion的好处吗？
主要是比较经济。recursion会存一个whole activation stack --> large memory
overhead, not efficient
但这个题是implement iterators, 和传统的iterative solution还不一样。iterator
的好处主要是flexible，container independent,还有就是support random access.可
以想象成每个node排成一行，可以move forward, backward for element access。
题目就是 Nested Iterator
Program an iterator for a List which may include nodes or List
{0, {1, 2}, 3, {4, {5, 6}}} Iterator returns 0 1 2 3 4 5 6
求java的做法。
感觉这道题关键是怎么设计这个既保存单个item，又保存list的结构， 这个结构设计
好了，用java iterator应该就不难了。不知道对不对， 求指点。 先谢谢啦 ：）
题目就是 Nested Iterator
Program an iterator for a List which may include nodes or List
{0, {1, 2}, 3, {4, {5, 6}}} Iterator returns 0 1 2 3 4 5 6
求java的做法。
感觉这道题关键是怎么设计这个既保存单个item，又保存list的结构， 这个结构设计
好了，用java iterator应该就不难了。不知道对不对， 求指点。 先谢谢啦 ：）
i need to keep track of the iterators to both the head element and the
tail elements given a std::list.
using name space std;
vector::iterator > x;
x.push_back(L.begin());
x.push_back(L.end());
x.back()--;
is there any alternative to replace the last two lines?
it seems the following not working. so reverse_iterator can't be casted to
iterator in force?
x.push_back(list::iterator(L.rbegin()));
In Unix, I used "kill" to kill my program, but my program has many
iterations, if I kill iteration 1, then it is dead; but iteration 2 will
start to run...etc..
Is there any way I can kill all my iterations in one shot? Thanks.
