一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1254|回复: 12
收起左侧

哪门公开课讲了Iterator的概念啊?

[复制链接] |试试Instant~ |关注本帖
AveMaleficum 发表于 2015-3-5 08:46:37 | 显示全部楼层 |阅读模式

[其他]Data structure #1 - 2015-03-05@MIT/UCB

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本帖最后由 AveMaleficum 于 2015-3-5 09:08 编辑

请问一下,哪一门公开课讲了data structure里面的iterator概念?就是那个java.util.Iterator,ListIterator.
我看了一下61 B的视频列表,似乎没有涉及到这个概念..。
之所以这么问是因为我们老师把这个加到了data structure里面,但是就讲了20分钟PPT,然后让我做lab
我死活做不出来...没办法了...

谢谢。

tailofjune 发表于 2015-3-5 08:55:26 | 显示全部楼层
那个不属于data structure吧,硬要说的话应该属于design pattern。
回复 支持 反对

使用道具 举报

 楼主| AveMaleficum 发表于 2015-3-5 09:09:42 | 显示全部楼层
tailofjune 发表于 2015-3-5 08:55
那个不属于data structure吧,硬要说的话应该属于design pattern。

这个不是吗?我们老师PPT讲了给Lab没办法啊。
小白请问一下design pattern和data structure啥关系啊。。

回复 支持 反对

使用道具 举报

sliu 发表于 2015-3-5 09:12:24 | 显示全部楼层
Java的花,LZ先学习一下interface,然后再学习iterator就顺理成章了。
顺带给个链接,我当时学的时候看的:
http://docs.oracle.com/javase/tu ... reateinterface.html
回复 支持 反对

使用道具 举报

 楼主| AveMaleficum 发表于 2015-3-5 09:13:55 | 显示全部楼层
sliu 发表于 2015-3-5 09:12
Java的花,LZ先学习一下interface,然后再学习iterator就顺理成章了。
顺带给个链接,我当时学的时候看的 ...

Interface学过了啊,突然觉得自己好弱智的感觉。。唉。。。
回复 支持 反对

使用道具 举报

tailofjune 发表于 2015-3-5 09:21:58 | 显示全部楼层
AveMaleficum 发表于 2015-3-5 09:09
这个不是吗?我们老师PPT讲了给Lab没办法啊。
小白请问一下design pattern和data structure啥关系啊。。 ...

怎么说呢,简单点说,data structure和design pattern都属于structure.
但是data structure多与算法结合,用于解决问题,关注data如何存放的问题.
design pattern则更偏向于软件工程中的概念,用于加强代码复用程度和灵活性.
我不知道lab具体什么样,但我猜测你们老师可能只是希望学生码代码实现一个iterator.你看看iterator都要什么函数,然后假定一个iterator的underlying data structure,实现一下好了.

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

sliu 发表于 2015-3-5 09:38:05 | 显示全部楼层
AveMaleficum 发表于 2015-3-5 09:13
Interface学过了啊,突然觉得自己好弱智的感觉。。唉。。。

那就很好理解iterator了。

比如从概念的角度,iterator包含hasNext, next, remove三个方法。这三个方法作为一套接口,实现数据结构的迭代,查询和修改。

从实现角度来说,
一个class首先要实现Iterable(implements Iterable,其中包含一个返回Iterator的方法),
而如果你想返回一个Iterator,该怎么办呢,当然是实现一个Iterator,所以你又需要构建一个SampleIterator implements Iterator(包含上面的hasNext, next, remove三个方法)。

细节你可以看看别人的例子,基本是我上面说的结构。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

Howie 发表于 2015-3-5 10:44:46 | 显示全部楼层
普林斯顿算法那个公开课,Week 2: Stacks and Queues 里面有。作业也要写这个

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

rsun 发表于 2015-3-5 23:33:18 | 显示全部楼层
写作业不会不是应该问同学或者ta么。。。
回复 支持 反对

使用道具 举报

cs900601 发表于 2015-3-5 23:57:11 | 显示全部楼层
要说迭代器的话,C++ Grandmaster这门课里有讲过什么是迭代器;
和Java很类似,迭代器是C++标准模板库中的一部分。
从比较宽泛的方面来说,所以需要迭代器的原因,是因为能让其下的容器都可以兼容“向前移动”、“向后移动”、和“随机访问”这几个操作,而又不管它具体是如何实现的。
也就像是有一个万能的机器人遥控器,上面有“向前1步”、“向后1步”、“到第N步”、“输入/输出”等功能,而不管你控制的机器人是用机械腿走路还是用轮子走路还是用反重力装置走路…
随机迭代器是最高级的,因为它依赖向前移动N步和向后移动N步的功能。(譬如在树上的迭代器,每次只能往前或往后一个单位,但是若是在数组上的迭代器,因为知道了下标就知道了存储位置,所以可以一次往前或往后N个单位)
如果一个迭代器能向前和向后移动,它就是双向迭代器(譬如在文件中定位的迭代器,可以快进到文件末端,也能返回到前面),如果只能向一个方向移动,那就是单向迭代器(譬如下载流媒体的迭代器,只能越下载越多,不能回退)。
而所有的迭代器都可以输入或输出(譬如印到屏幕上,或是从键盘读取数据),或二者兼备:
螢幕快照_2015-03-05_09-39-21.png (n3485 Chapter 24.2.1)

这个页面上有更多的图来解释以上几种迭代器(http://www.math.univ-toulouse.fr/~grundman/stl-tutorial/tutorial_11.htm

另外,迭代器反应了一些底层实现的机制,譬如说std::map(在Java中是Map)是用红黑树实现的,其Key是有序存放的,所以可以通过以下代码按顺序把Key都印出来……
  1. <p>std::map m1;</p><p>for(std::map<int, int>::iterator itr = m1.begin(); itr!=m1.end(); itr++) { printf("%d\n", itr->first); }</p>
复制代码
印出来的数会是递增的。





而若是<unordered_map>(在Java中可能是HashMap),也许就不会是递增的…
不知有没有地方说错…


评分

1

查看全部评分

回复 支持 反对

使用道具 举报

wilbur_zzz 发表于 2015-4-6 15:09:26 | 显示全部楼层
Iterator其实没什么难理解的,我当时也不知道是啥,其实很简单,地基那楼说的挺好
回复 支持 反对

使用道具 举报

sky420 发表于 2015-6-15 04:36:29 | 显示全部楼层
本帖最后由 sky420 于 2015-6-15 05:24 编辑

Berkely的CS61A,倒数第二周的视频,可以去我的网页查,gaotx.com/cs61a。不清楚其他的语言,在上cs61a,主要用python, 最近正好讲到这个概念。因为术语不知道翻译过来准不准确,所以我用英语简单介绍一下。
Take for loop as an example to specifiy the iterable and iterator. The object that for loop iterates over is required to be iterable.
  1. for elem in iterable: do something
复制代码
What the for loop exactly does is that it uses __iter__ method to get an iterator from the iterable and gets value or element from the iterator using __next__ method. Thus, iteratble must implement iterable interface which contains __iter__ method. It seems that iterator only requires to implement __next__ method, but it is not ture. Actually iterator is also an iterable because after first iteration, in order to make next iteration, for loop needs to call the iterator that is returned from the first iteration to get another iterator using __iter__ method. Then, use the new iterator from the second iteration to get new value by __next__ method. Thus, an iterator needs to implement interator interface which includes both __iter__ and __next__ method. Note that for iterator, __next__ method usually return itself.

class Iterable:
    def __init__(self):
        do something
    def __iter__(self):
        do something


class Iterator:
    def __init__(self):
        self.start = 5
    def __next__(self):
        do something
    def __iter__(self):
        return self


评分

1

查看全部评分

回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-6 23:13

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表