M*******a
发帖数: 1633 | 1 这样的话貌似就不是O(n)的iterate了，假设这个hashtable初始的size为100，然后只
有2个元素，这样iterate的话是O(100)而不是O(2) |
|
l*********8
发帖数: 4642 | 2 unordered_set 或者set的iterator指向的内容是const的。
否则， 如果你可以修改*it, 那么*it在hash map or bst里面的位置就要改变了，那么
这个iterator就要变成invalid了。 乱套了。 |
|
x**********a
发帖数: 1372 | 3 1. 你平时怎么选择的，面试就怎么选择
2. 要经得起follow up的问题，面试官可能问你用这个iterator的cost。我有一轮面试
就问到了，然后说让我写一个custom iterator去optimize。 |
|
y*****e
发帖数: 712 | 4 直接放int就丢失了Iterator了，没法call iter.hasNext(). |
|
A*******e
发帖数: 2419 | 5 所以iterator初始化到最小节点，next()就是iterative traversal里走一步？这题出
的很生硬啊。 |
|
c***u
发帖数: 4107 | 6 Implement an iterator over a binary search tree (BST). Your iterator will be
initialized with the root node of a BST.
Calling next() will return the next smallest number in the BST.
Note: next() and hasNext() should run in average O(1) time and uses O(h)
memory, where h is the height of the tree.
高人的程序是:
public class BSTIteratorInorder {
private Stack stack = new Stack<>();
public BSTIteratorInorder(TreeNode root) {
pushLeftChildren(root); // find the first node (le... 阅读全帖 |
|
T******7
发帖数: 1419 | 7 1. 实现一个iterator，可以按照距离原点的曼哈顿距离输出所有的点。
曼哈顿距离iterator随便写了一个 请大家帮挑毛病，謝謝 |
|
g*****y
发帖数: 94 | 8 C语言的题，对C语言不是很熟，如果下面的有语法错误的话，还请谅解。对树进行中序
遍历，initial代码如下：
void inorder(TreeNode* root) {
LABEL:
if (root == NULL) {
return;
}
// Left subtree
inorder(root->left);
// Print value
printf("%dn", root->val);
// Right subtree
root = root->right;
goto LABEL;
}
其实上面的代码对于右子树来说就是变相的recursive调用，面试官要求如何用些代码
来取代"goto LABEL;"这句，然后写些iterative的代码来实现这个中序遍历。其实要求
就是怎么做到左子树recursive，右子树iterative。怎么破这个？ |
|
S*****n
发帖数: 227 | 9
elements.begin()的类型是 void const;
iter的类型是map< , >::iterator;
你说该怎么改？我不知道。。heihei |
|
b***y
发帖数: 2799 | 10 ☆─────────────────────────────────────☆
agare (work) 于 (Thu Jul 21 19:56:29 2005) 提到:
what's the difference between iterator & const_iterator.
For example, a |
|
c**a
发帖数: 316 | 11 。。。
pos 就根本不是 pointer。
vector v(10);
char* p = &v[5];
vector::iterator it = p ; // error.
vector::iterator it = v.begin() + p - &v[0];
// now, it is ugly. |
|
a*n
发帖数: 32 | 12 how about this?
string::iterator it = string::iterator(&s[pos]); |
|
X****r
发帖数: 3557 | 13 typename std::list*>::iterator pos;
The compiler has no idea std::list*>::iterator is a type
without knowing what is T. |
|
b*******e
发帖数: 1 | 14 问一下， 开始的两行什么意思？
std::list*> pos = myList.begin();
这里的pos 不久应该是iterator么
typename std::list*>::iterator pos;
为什么又declare一次？ |
|
h****b
发帖数: 157 | 15 是不是map:iterator可以指向下一个元素，所以，用iterator自动traverse tree,因为
map是
sorted.
还有什么区别？ |
|
t****t
发帖数: 6806 | 16 这个是哪本书说的啊。要说iterator是generalized pointer就对了。反正你面试要这么
说肯定没分。
通常现在大家接受的说法是，smart pointer不需要手工delete的pointer. iterator基
本上没这功能。C++里shared_ptr算是一个。auto_ptr勉强沾边。 |
|
z****e
发帖数: 2024 | 17 Book Exploring C++
Publisher Apress
DOI 10.1007/978-1-4302-0352-0
Copyright 2009
ISBN 978-1-59059-749-1 (Print) 978-1-4302-0352-0 (Online)
Part Part 4
DOI 10.1007/978-1-4302-0352-0_60
Pages 567-580
Subject Collection Professional and Applied Computing
SpringerLink Date Saturday, February 07, 2009
我就google随便一搜，
其中一句：
An iterator can ensure that it does not advance past the end of a container.
Thus, iterators are smart pointers because they can be really, really smart |
|
d****p
发帖数: 685 | 18 iterator for certain containers (eg vector> is implemented as raw pointer -
you can think as:
template
class Iterator
{
....T* _M_current;
}
After optimization is turned on, the thin wrapper will be thown away by
compiler and you will have the
same raw metal code.
For example, you have two functions:
int foo1(std::vector::const_iterator intItr)
{ return *intItr + 1; }
and
int foo2(const int* intPtr)
{ return *intPtr + 1; }
Both functions generate the around same assembly snipet: |
|
h****b
发帖数: 157 | 19 想不到大家这么踊跃热情 : ）
如果问问什么stl不用pointer (我被问到)，可不可以回答 iterator的operator被重载
过，比
pointer更容易使用，比如list的iterator++,直接指向下一个link list element。
另外，请问一下：vector是怎么实现的？我知道是dynamic array, continuous memory
,不
过如果需要resize （e.g. increase size）, 怎么能保证还是continuous memory？
谢了 |
|
X****r
发帖数: 3557 | 20 你这么说也可以。如果是我的话会回答为了算法的普适性，STL需要区分一个类型的界面
（以及相应的功能）和其具体实现。iterator就是这样一种抽象。通过使用iterator
这个概念，而不是它的某一种具体形式（比如指针），不同容器的区别对于不关心这些
区别的算法来说就被统一了，从而简化了代码。
vector的问题，重新分配然后把内容移动过去就可以了。你可以直接看STL的源代码啊。
memory |
|
g*********s
发帖数: 1782 | 21 I have a the following data structure:
std::vector::iterator> X (x_sz);
Question: what is the initial value for X[0]..X[x_sz-1]? Do we have a "NULL"
iterator here? |
|
p*u
发帖数: 2454 | 22
and potentially dangerous?
defined doubly linked list and the initial value NULL for X elements. I
expect a stl based solution can achieve similar behaviour.
first question is why u have to use X, not the list directly? do u want
random access dummy_queue? u can add a X::iterator member to dummy queue
elements; when u delete from dummy_queue, u need to delete the element in
X first through X::iterator( note delete in vector is not very efficient
). but it's convoluted, why do u have to use X? |
|
b******n
发帖数: 592 | 23 end is not null, it points to *after* last item. you have to take care of
iterators when you modify stl container. Why do you need a list of iterators
.
and potentially dangerous?
defined doubly linked list and the initial value NULL for X elements. I
expect a stl based solution can achieve similar behaviour. |
|
b******n
发帖数: 592 | 24 My suggestion is not to do this, but I think you can use use
your own null:
vector null;
vector::iterator nullIt = null.begin();
since nullIt is pointing to this special vector, it can be used as your
special
value for null for other vectors.
I would use hash to keep my data and use list to keep iterators if I have to
. To me, hash memory layout is more stable (not if it grows).
the |
|
z****e
发帖数: 2024 | 25 .base()
but that's still not what you want.
difference between reverse iterator and iterator is no more close than
difference between class A; and class B; |
|
b*******s
发帖数: 5216 | 26 而且保存iterator没什么意义
iterator很容易失效 |
|
r****t
发帖数: 10904 | 27 在本版前面看到师傅们说过，不过当时就有疑问：
为啥 pointers are iterators?
只是因为 iterator objects support pointers arithmetic 就这么说么？（比如
sequential containers 可以用一对 pointer 来初始化，这个是不是用的 overload
ctor 来实现的？）总觉得这样逻辑有点不通，倒像是 duck typing 的逻辑了。
还是有啥别的意思在里面? |
|
c******t
发帖数: 133 | 28 菜鸟弱问：各种容器的sort函数都要两个iterator作为参数，能不能用pointer呢？我
自己理解的是如果内存连续就应该可以用pointer，比如vector，内存不连续就不行，
比如list，可是试了一下，vector也不能用pointer作为参数来排序，为什么？
iterator有哪些特殊的功能？谢谢了！ |
|
l*********8
发帖数: 4642 | 29 yes, unordered_set 或者set的iterator指向的内容是const的。
否则， 如果你可以修改*it, 那么*it在hash map or bst里面的位置就要改变了，那么
这个iterator就要变成invalid了。 乱套了。 |
|
a*********a
发帖数: 3656 | 30 sets are ordered. allowing modification of set elements via iterators would
violate the order, unless the set is re-sorted every time. the decision was
made by the committee to simply disallow nonconst reference to set elements.
there was an article in C++ user's journal about this long long ago.
set s;
s.insert(1);
s.insert(2);
s.insert(3);
set::iterator i=s.begin();
i++;
*i = 4; // s is no longer ordered!
for unordered_set, I guess allowing nonconst ref to elements would
invalidate t... 阅读全帖 |
|
Y**G
发帖数: 1089 | 31 有没有下面的现成工具？
Iterable merge(Iterable ... items);
假如a是merge(foo, bar)返回的结果,则遍历a等于遍历foo然后bar。但是把foo和bar的
元素都放入一个list又太浪费。又没有现成的轮子可以用？ |
|
K***a
发帖数: 497 | 32 function(vector a)
{
vector::iterator ater = a.begin();
vector::iterator bter = a.begin();
cout <<*ater <
cout <<*(ater+1) <
for(bter; bter != a.end; bter++)
{
cout <<*bter;
}
}
调用function两次。在两次调用中，ater都能输出vector a中每个数据。但是bter只有
在第一次调用中能输出vector a... 阅读全帖 |
|
h***z
发帖数: 233 | 33 It seems like most of the iterative linear solvers out there are either
based on or closely related to the conjugate gradient method. I know it's
commonly believed that BFGS is superior to CG as an unconstrained
optimization algorithm, so I'm wondering why all the iterative solvers are
based on CG type of algorithms? |
|
s********z
发帖数: 5411 | 34 今天看书,书上提到范德华的气体方程.
(P + a/V^2)(V - b)) = RT
只有V不知道，需要求V。 书上说有两种iteration的方法计算V，但是没具体说。
我对iteration不太清楚，谁能给解释一下。有那两种方法？具体怎么算阿？
谢谢啦！ |
|
d******e
发帖数: 7844 | 35 PCA里的SVD分解也是iterative来解的。
要么高斯消元解线性方程组，要么用Power Iteration。只不过已经是很成熟的技术，
所以已经有现成的函数了。 |
|
D**u
发帖数: 288 | 36 印象中如果需要PCA的所有的orthogonal basis 还是需要calculate eigen vectors的,不
过大多数情况都是只需要top dominant component，这样是有iterative的method的
，背后的idea类似于 Lanczos process，不过凡是iterative的method都是
approximation not 100% accurate. |
|
|
I**A
发帖数: 2345 | 38 不知道哪个更好理解，自己看吧
//POSTORDER traversal iteratively
public static void postOrderIteratively(BST mybst){
Stack nodestack = new Stack();
Node node = mybst.root;
Node prevnode = mybst.root;
//initialize the stack
while(node!=null){
nodestack.push(node);
node = node.left;
}
while( !nodestack.isEmpty()){
node = (Node)nodestack.pop();
//if this is the leaf node, then print the data o |
|
j*****g
发帖数: 223 | 39 不好意思。本来这题飘过，都没有正眼看一下。没想到近来想练练手，楞是没做出来。
pre-order and in-order are easy.
But post order, iterative traversal, without setting flags on the nodes....
how .... //老泪纵横.. |
|
m********g
发帖数: 272 | 40 有人知道怎么用iteration实现permutation吗？就是不用recursion的
谢谢！ |
|
s******d
发帖数: 61 | 41 Iterative way ofr single preorderTraversal
public void preorderTraversal(Node root){
Stack stack=new Stack();
stack.push(root);
while(true){
Node current=stack.pop();
if(current==null) break;
Node right=current.getRight();
if(right!=null)
stack.push(right);
Node left=current.getLeft();
if(left!=null)
stack.push(left);
}
}
这个是preorderTraversal, 这样怎么转成inorder呢? |
|
v***n
发帖数: 562 | 42 Anyone gives an iterative graph dfs algorithm. My implementation in Java is
as follows. It works but look a little wired to me.
public void dfsIterative(Vertex v) {
v.isVisited = true;
Stack s = new Stack();
System.out.print(v.label + " ");
for (Vertex u: v.adj()) {
s.push(u);
}
while (!s.empty()) {
Vertex u = s.pop();
for (Vertex w : u.adj()) {
if (!w.isVisited) {
w.isVisited = true;
s.push(w);
Sys... 阅读全帖 |
|
d********w
发帖数: 363 | 43 面试官说不让这么用，可以用到vector的iterator |
|
|
p*****2
发帖数: 21240 | 45
不清楚。我Java也不熟。定义两个iterator跟定义x,y差不多把。 |
|
l*****a
发帖数: 14598 | 46 估计就是看你对iterator/enumerator的理解/实现吧 |
|
l*****a
发帖数: 14598 | 47 wait, vector is from C++/STL,it should support iterator
IEnumerable/Enumerator are from C#.. |
|
p*****2
发帖数: 21240 | 48
那还不错呀。我没有test，只是写写思路。这题应该是电面的题吧？不过太java
specific了。我用C和C＃的时候都没有用过iterator。 |
|
z*********8
发帖数: 2070 | 49 我已经知道怎么写了， 不过你这个。。。
iterator应该提供hasNext和Next吧 |
|
|
