草庐IT

C++ deque 的迭代器在 push_front() 之后失效

coder 2023-11-15 原文

刚才，我正在阅读 Josuttis 的 STL 书。

据我所知——c++ vector 是一个可以重新分配的 c 数组。所以，我明白了，为什么在 push_back() 之后所有的迭代器和引用都会变得无效。

但我的问题是关于 std::deque。据我所知，它是大块数组(c 数组的 c 数组)。所以 push_front() 在开头插入元素，如果没有空间，deque 分配新 block ，并将元素放在已分配 block 的末尾。

在中间的 insert() 之后，所有引用和迭代器都变得无效，我明白为什么——所有元素都被移动了。 但我真的误解了短语“...在 push_back() 和 push_front() 之后所有引用都保持有效，但迭代器不有效”(相同的短语可以在 @ standard:23.2.2.3 中找到)

这是什么意思？!如果引用有效，则双端队列无法重新分配(== 移动)其元素。那么为什么迭代器会失效呢？为什么我不能在插入非移动元素后使用它们？或者这句话的意思是，我不能确定迭代器是否等于 begin() 或 end() 和溢出？

另外，我想提一下，在 erase() 之后，所有迭代器和引用都保持有效(删除的除外 :-))。

PS:请不要以“标准”形式回答:“它不能使用，因为 THE STANDARD 是这么说的”。 我想了解原因，会发生什么。

最佳答案

我认为迭代器失效但引用未失效的原因可能是因为双端队列实现了指向存储元素的双端队列页面的指针数组。对双端队列中元素的引用将直接引用“页面”中的元素。但是，双端队列中的迭代器可能依赖于指向各个页面的指针 vector 。

在双端队列的一端或另一端插入一个新元素永远不需要重新分配和移动现有数据页，但它可能需要添加到(并因此重新分配和复制)页面指针数组，使任何依赖于的迭代器无效前一个页面指针数组。

Array of pointers           
(if this grows                 Data Pages
 and gets copied,           (these never move
 iterators are invalid)      due to insert at ends)
-----------------          --------------------

 +----------+               +----------+
 |         -+-------------->|          |
 +----------+               +----------+
 |         -+---------+     |          |
 +----------+         |     +----------+
 |         -+---+     |     |          |
 +----------+   |     |     +----------+ 
                |     |
                |     |
                |     |
                |     |     +----------+
                |     +---->|          |
                |           +----------+
                |           |          |
                |           +----------+
                |           |          |
                |           +----------+ 
                |           
                |           +----------+
                +---------->|          |
                            +----------+
                            |          |
                            +----------+
                            |          |
                            +----------+

关于C++ deque 的迭代器在 push_front() 之后失效，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/1658956/

push_frontampsectionpushc++stliteratordeque

有关C++ deque 的迭代器在 push_front() 之后失效的更多相关文章

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

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

  2. ruby - 为什么 Ruby 的 each 迭代器先执行？ - 2

    我在用Ruby执行简单任务时遇到了一件奇怪的事情。我只想用每个方法迭代字母表，但迭代在执行中先进行:alfawit=("a".."z")puts"That'sanalphabet:\n\n#{alfawit.each{|litera|putslitera}}"这段代码的结果是:(缩写)abc⋮xyzThat'sanalphabet:a..z知道为什么它会这样工作或者我做错了什么吗？提前致谢。 最佳答案 因为您的each调用被插入到在固定字符串之前执行的字符串文字中。此外，each返回一个Enumerable，实际上您甚至打印它。试试

  3. ruby - 使用 `+=` 和 `send` 方法 - 2

    如何将send与+=一起使用？a=20;a.send"+=",10undefinedmethod`+='for20:Fixnuma=20;a+=10=>30 最佳答案 恐怕你不能。+=不是方法，而是语法糖。参见http://www.ruby-doc.org/docs/ProgrammingRuby/html/tut_expressions.html它说Incommonwithmanyotherlanguages,Rubyhasasyntacticshortcut:a=a+2maybewrittenasa+=2.你能做的最好的事情是:

  4. ruby - 如何计算 Liquid 中的变量 +1 - 2

    我对如何计算通过{%assignvar=0%}赋值的变量加一完全感到困惑。这应该是最简单的任务。到目前为止，这是我尝试过的:{%assignamount=0%}{%forvariantinproduct.variants%}{%assignamount=amount+1%}{%endfor%}Amount:{{amount}}结果总是0。也许我忽略了一些明显的东西。也许有更好的方法。我想要存档的只是获取运行的迭代次数。 最佳答案 因为{{incrementamount}}将输出您的变量值并且不会影响{%assign%}定义的变量，我

  5. ruby 代码 : why put colon in front of variable name (inside initialize method) - 2

    我遇到了一些Ruby代码，我试图理解为什么变量在initialize方法声明中的名称末尾有冒号。冒号有什么原因吗？attr_reader:var1,:var2definitialize(var1:,var2:)@var1=var1@var2=var2end 最佳答案 那些是关键字参数。您可以按名称而非位置使用它们。例如ThatClass.new(var1:42,var2:"foo")或ThatClass.new(var2:"foo",var1:42)Anarticleaboutkeywordargumentsbythoughtbot

  6. arrays - Ruby 数组 += vs 推送 - 2

    我有一个数组数组，想将元素附加到子数组。+=做我想做的，但我想了解为什么push不做。我期望的行为(并与+=一起工作):b=Array.new(3,[])b[0]+=["apple"]b[1]+=["orange"]b[2]+=["frog"]b=>[["苹果"],["橙子"],["Frog"]]通过推送，我将推送的元素附加到每个子数组(为什么？):a=Array.new(3,[])a[0].push("apple")a[1].push("orange")a[2].push("frog")a=>[[“苹果”、“橙子”、“Frog”]、[“苹果”、“橙子”、“Frog”]、[“苹果”、“

  7. += 的 Ruby 方法 - 2

    有没有办法让Ruby能够做这样的事情？classPlane@moved=0@x=0defx+=(v)#thisiserror@x+=v@moved+=1enddefto_s"moved#{@moved}times,currentxis#{@x}"endendplane=Plane.newplane.x+=5plane.x+=10putsplane.to_s#moved2times,currentxis15 最佳答案 您不能在Ruby中覆盖复合赋值运算符。任务在内部处理。您应该覆盖+，而不是+=。plane.a+=b与plane.a=

  8. ruby - Sinatra + Heroku + Datamapper 使用 dm-sqlite-adapter 部署问题 - 2

    出于某种原因，heroku尝试要求dm-sqlite-adapter，即使它应该在这里使用Postgres。请注意，这发生在我打开任何URL时-而不是在gitpush本身期间。我构建了一个默认的Facebook应用程序。gem文件:source:gemcuttergem"foreman"gem"sinatra"gem"mogli"gem"json"gem"httparty"gem"thin"gem"data_mapper"gem"heroku"group:productiondogem"pg"gem"dm-postgres-adapter"endgroup:development,:t

  9. ruby - 更改 $LOAD_PATH 时，为什么使用 unshift 而不是 push？ - 2

    我发现ruby加载路径是一个数组，很多项目都是这样使用的:$:.unshift(File.expand_path("../../lib",__FILE__))可以将本地文件添加到ruby路径数组的前面，方便我们require或者load。所以，我希望知道为什么我们不使用push将文件添加到数组的末尾？ 最佳答案 假设您有一个“date.rb”文件(为什么不呢)并且您想要加载这个文件，而不是标准库日期。如果您使用追加，当您调用require'date'时您的文件将永远不会被加载，因为它位于数组的末尾并且标准日期会在之前找到。因此，如果

  10. ruby - 迭代在 Ruby 中是如何工作的？ - 2

    我最近开始编写Ruby代码，但我对block参数有误解。以下面的代码为例:h={#Ahashthatmapsnumbernamestodigits:one=>1,#The"arrows"showmappings:key=>value:two=>2#ThecolonsindicateSymbolliterals}h[:one]#=>1.Accessavaluebykeyh[:three]=3#Addanewkey/valuepairtothehashh.eachdo|key,value|#Iteratethroughthekey/valuepairsprint"#{value}:#{ke

随机推荐