📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 4068| 回复: 12
跳转到指定楼层
上一主题 下一主题
收起左侧

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

全局:
公开课
学校名称: MIT/UCB
Unit号: 1
开课时间: 2015-03-05
课程全名: Data structure
平台: 其他

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

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

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

谢谢。


上一篇:[Homework] Algorithms: Design and Analysis, Part I (Week 5)
下一篇:Principles of Computing Week3
推荐
cs900601 2015-3-5 23:57:11 | 只看该作者
全局:
要说迭代器的话,C++ Grandmaster这门课里有讲过什么是迭代器;
和Java很类似,迭代器是C++标准模板库中的一部分。
从比较宽泛的方面来说,所以需要迭代器的原因,是因为能让其下的容器都可以兼容“向前移动”、“向后移动”、和“随机访问”这几个操作,而又不管它具体是如何实现的。
也就像是有一个万能的机器人遥控器,上面有“向前1步”、“向后1步”、“到第N步”、“输入/输出”等功能,而不管你控制的机器人是用机械腿走路还是用轮子走路还是用反重力装置走路…
随机迭代器是最高级的,因为它依赖向前移动N步和向后移动N步的功能。(譬如在树上的迭代器,每次只能往前或往后一个单位,但是若是在数组上的迭代器,因为知道了下标就知道了存储位置,所以可以一次往前或往后N个单位)
如果一个迭代器能向前和向后移动,它就是双向迭代器(譬如在文件中定位的迭代器,可以快进到文件末端,也能返回到前面),如果只能向一个方向移动,那就是单向迭代器(譬如下载流媒体的迭代器,只能越下载越多,不能回退)。
而所有的迭代器都可以输入或输出(譬如印到屏幕上,或是从键盘读取数据),或二者兼备:
(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大米 +10 收起 理由
AveMaleficum + 10 谢谢!

查看全部评分

回复

使用道具 举报

推荐
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


回复

使用道具 举报

推荐
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大米 +10 收起 理由
AveMaleficum + 10 谢谢。

查看全部评分

回复

使用道具 举报

🔗
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大米 +10 收起 理由
AveMaleficum + 10 谢谢。

查看全部评分

回复

使用道具 举报

🔗
Howie 2015-3-5 10:44:46 | 只看该作者
全局:
普林斯顿算法那个公开课,Week 2: Stacks and Queues 里面有。作业也要写这个

评分

参与人数 1大米 +10 收起 理由
AveMaleficum + 10 Thanks!!

查看全部评分

回复

使用道具 举报

🔗
jby1797 2015-3-5 23:33:18 | 只看该作者
全局:
写作业不会不是应该问同学或者ta么。。。

点评

。。目前只有我一个人上这门课啊。不说了,说多都是泪。我约好明天和教授见面了。  发表于 2015-3-6 02:14
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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