草庐IT

c++ - 为什么没有更多的迭代器随机访问？

coder 2024-02-14 原文

我正在努力了解更多有关 C++ 中的 STL 迭代器的信息。我了解不同的数据结构如何具有不同的迭代器，但我不明白为什么有些迭代器不是 RandomAccess。例如，为什么 LinkedList 迭代器不是随机访问迭代器？我知道 LinkedList 本身不是“随机访问结构”，但我们不能实现迭代器来产生随机访问结构的错觉吗？例如，LinkedList 有一个双向迭代器，它没有定义 + 或 += 运算符，但定义了++ 运算符。难道我们不能只定义 + 和 += 运算符，使用类似的东西:

iterator operator+= (int steps) {
     for (int i = 0; i < steps; ++i) {
          this->operator++();
     }
}

在查看了 RandomAccessIterator 要求之后，我认为我们可能可以为 LinkedList 实现大部分(如果不是全部)这些功能，那么我们为什么不呢？我猜是因为某些操作本质上具有 O(N) 时间复杂度，但我不确定这是否是关键问题。如果我们要使用这种方法实现 RandomAccessIterators，这对将 LinkedList 与 STL 算法一起使用会有什么影响？我们会突然能够使用 std::sort 函数对 LinkedList 进行排序吗？

最佳答案

I'm guessing its because some operations would have essentially O(N) time complexity, but I'm not sure if that is the key concern.

是的，这正是关键问题。迭代器是在指针之后建模的。而有了指针，人们就有了一定的期待。这些期望之一是指针加法和减法是非常快的操作(具体来说，O(1))。标准库的设计者决定兑现这些期望。因此，如果标准库迭代器不能在 O(1) 中执行加法和减法，那么它就不会实现这些操作，并且不属于随机访问迭代器。

请注意，使用递增和递减运算符(++ 和 --)，性能要求稍微宽松一些，并且有一些迭代器实现了 O (log n) 而不是 O(1)。这种妥协是必要的，因为如果您不能递增或递减迭代器，它就没有多大用处。

If we were to implement RandomAccessIterators using this approach, what consequences would this have on using the LinkedList with STL algorithms? Would we suddenly be able to sort a LinkedList using the std::sort function?

是的。但它会(至少)变成一个 O(n^2) 算法，而不是标准所 promise 的 O(n log n)。

关于c++ - 为什么没有更多的迭代器随机访问？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/46627031/

amp43LinkedListsection运算符c++stliterator

有关c++ - 为什么没有更多的迭代器随机访问？的更多相关文章

  1. ruby - 为什么我可以在 Ruby 中使用 Object#send 访问私有(private)/ protected 方法？ - 2

    类classAprivatedeffooputs:fooendpublicdefbarputs:barendprivatedefzimputs:zimendprotecteddefdibputs:dibendendA的实例a=A.new测试a.foorescueputs:faila.barrescueputs:faila.zimrescueputs:faila.dibrescueputs:faila.gazrescueputs:fail测试输出failbarfailfailfail.发送测试[:foo,:bar,:zim,:dib,:gaz].each{|m|a.send(m)resc

  2. ruby-on-rails - Rails - 子类化模型的设计模式是什么？ - 2

    我有一个模型:classItem项目有一个属性“商店”基于存储的值，我希望Item对象对特定方法具有不同的行为。Rails中是否有针对此的通用设计模式？如果方法中没有大的if-else语句，这是如何干净利落地完成的？ 最佳答案 通常通过Single-TableInheritance. 关于ruby-on-rails-Rails-子类化模型的设计模式是什么？，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.co

  3. ruby - 什么是填充的 Base64 编码字符串以及如何在 ruby​​ 中生成它们？ - 2

    我正在使用的第三方API的文档状态:"[O]urAPIonlyacceptspaddedBase64encodedstrings."什么是“填充的Base64编码字符串”以及如何在Ruby中生成它们。下面的代码是我第一次尝试创建转换为Base64的JSON格式数据。xa=Base64.encode64(a.to_json) 最佳答案 他们说的padding其实就是Base64本身的一部分。它是末尾的“=”和“==”。Base64将3个字节的数据包编码为4个编码字符。所以如果你的输入数据有长度n和n%3=1=>"=="末尾用于填充n%

  4. ruby - 解析 RDFa、微数据等的最佳方式是什么，使用统一的模式/词汇(例如 schema.org)存储和显示信息 - 2

    我主要使用Ruby来执行此操作，但到目前为止我的攻击计划如下:使用gemsrdf、rdf-rdfa和rdf-microdata或mida来解析给定任何URI的数据。我认为最好映射到像schema.org这样的统一模式，例如使用这个yaml文件，它试图描述数据词汇表和opengraph到schema.org之间的转换:#SchemaXtoschema.orgconversion#data-vocabularyDV:name:namestreet-address:streetAddressregion:addressRegionlocality:addressLocalityphoto:i

  5. ruby - 难道Lua没有和Ruby的method_missing相媲美的东西吗？ - 2

    我好像记得Lua有类似Ruby的method_missing的东西。还是我记错了？ 最佳答案 表的metatable的__index和__newindex可以用于与Ruby的method_missing相同的效果。 关于ruby-难道Lua没有和Ruby的method_missing相媲美的东西吗？，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/7732154/

  6. ruby - 为什么 4.1%2 使用 Ruby 返回 0.0999999999999996？但是 4.2%2==0.2 - 2

    为什么4.1%2返回0.0999999999999996？但是4.2%2==0.2。 最佳答案 参见此处:WhatEveryProgrammerShouldKnowAboutFloating-PointArithmetic实数是无限的。计算机使用的位数有限(今天是32位、64位)。因此计算机进行的浮点运算不能代表所有的实数。0.1是这些数字之一。请注意，这不是与Ruby相关的问题，而是与所有编程语言相关的问题，因为它来自计算机表示实数的方式。 关于ruby-为什么4.1%2使用Ruby返

  7. ruby-on-rails - 在混合/模块中覆盖模型的属性访问器 - 2

    我有一个包含模块的模型。我想在模块中覆盖模型的访问器方法。例如:classBlah这显然行不通。有什么想法可以实现吗？ 最佳答案 您的代码看起来是正确的。我们正在毫无困难地使用这个确切的模式。如果我没记错的话，Rails使用#method_missing作为属性setter，因此您的模块将优先，阻止ActiveRecord的setter。如果您正在使用ActiveSupport::Concern(参见thisblogpost)，那么您的实例方法需要进入一个特殊的模块:classBlah

  8. ruby-on-rails - rails 目前在重启后没有安装 - 2

    我有一个奇怪的问题:我在rvm上安装了ruby​​onrails。一切正常，我可以创建项目。但是在我输入“railsnew”时重新启动后，我有“程序'rails'当前未安装。”。SystemUbuntu12.04ruby-v"1.9.3p194"gemlistactionmailer(3.2.5)actionpack(3.2.5)activemodel(3.2.5)activerecord(3.2.5)activeresource(3.2.5)activesupport(3.2.5)arel(3.0.2)builder(3.0.0)bundler(1.1.4)coffee-rails(

  9. ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2

    我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server

  10. ruby - 续集在添加关联时访问many_to_many连接表 - 2

    我正在使用Sequel构建一个愿望list系统。我有一个wishlists和itemstable和一个items_wishlists连接表(该名称是续集选择的名称)。items_wishlists表还有一个用于facebookid的额外列(因此我可以存储opengraph操作)，这是一个NOTNULL列。我还有Wishlist和Item具有续集many_to_many关联的模型已建立。Wishlist类也有:selectmany_to_many关联的选项设置为select:[:items.*,:items_wishlists__facebook_action_id].有没有一种方法可以

随机推荐