[問題] map元素的刪除?

[ddt2 (賣生煎包卡喜哉~~)]

我想使用iterater來刪除map的元素

        map< int, Node * > child;
        map< int, Node * >::iterator q1;

我看到有種做法是用tmp_iterator來維持

        for(q1 = child.begin(); q1 != child.end();   ){
            if(刪除條件){
                map< int, Node * >::iterator tmp_q1 = q1;
                ++tmp_q1 ;
                child.erase(q1);
                q1 = tmp_q1;
             }else{
                ++q1;

             }
         }

compile可以過(我用vc++6)
不過執行時會在 ++tmp_q1 ; 出錯
不知道有沒有人碰過這方面的問題??
還有該怎麼解決呢??


--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.122.76.102
推 UNARYvvv:似乎類似 8174 篇所說的..
推 renderer:child.clear();  !!!???
推 UNARYvvv:他用erase是要刪除特定項目,應該不是需要clear
推 renderer:ql = child.erase(ql);
推 khoguan:請詳述++tmp_q1; 會出什麼錯? 錯誤訊息？
→ sekya:恩  這個要用ql = child.erase(ql);
> -------------------------------------------------------------------------- <

作者: cplusplus (永夜) 看板: C_and_CPP
標題: Re: [問題] map元素的刪除? 
時間: Thu Jun 30 18:25:05 2005

※ 引述《ddt2 (賣生煎包卡喜哉~~)》之銘言：

請使用正確的方式

erase的宣告:

iterator erase(
   iterator _Where
);
iterator erase(
   iterator _First,
   iterator _Last
);
size_type erase(
   const key_type& _Key
);

For the first two member functions, a bidirectional iterator that designates
the first element remaining beyond any elements removed, or a pointer to the
end of the map if no such element exists.
For the third member function, returns the number of elements that have been
removed from the map.

所以你要步就使用第三種

要不就使用第一種然後接收它的傳回值再做處理就好了

這樣才是正確的方式

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.115.217.14

> -------------------------------------------------------------------------- <

作者: khoguan (Khoguan Phuann) 看板: C_and_CPP
標題: Re: [問題] map元素的刪除?
時間: Fri Jul  1 04:33:13 2005

※ 引述《cplusplus (永夜)》之銘言：
: erase的宣告:
: iterator erase(
:    iterator _Where
: );
: iterator erase(
:    iterator _First,
:    iterator _Last
: );
: size_type erase(
:    const key_type& _Key
: );

  嗯，剛才我再去查了一下。SGI 以及標準 C++ 所提供的 map
  其三種 erase()在上述的第一、第二種，其傳回型態是 void,
  而非如 sequence container 般，是傳回 iterator. 至於
  VC++提供的 STL 版本是向 Dinkumware 買的，其 map 的這
  兩個erase() 的確是傳回 iterator.

  Scott Meyers 在他的 Effective STL 一書中提到說，associative
  container 的 erase() 在標準中不傳回 iterator, 據解釋，
  是考慮到這樣會有unacceptable performance penalty。但他
  和許多人一樣，認為不然。看起來 Dinkumware 就是能夠做到
  不會有什麼 performance penalty, 所以傳回 iterator。不過
  這樣一來，就會有移植性的問題了。像是 g++ 就是依照標準，
  return void.

--
※ 發信站: 批踢踢實業坊(ptt.cc)
※ 編輯: khoguan         來自: 220.130.208.168      (07/01 04:44)
推 cplusplus:oh no 我都直接查msdn 忘了vc的stl是...orz
> -------------------------------------------------------------------------- <

作者: renderer (rendering) 看板: C_and_CPP
標題: Re: [問題] map元素的刪除? 
時間: Fri Jul  1 09:32:33 2005

※ 引述《khoguan (Khoguan Phuann)》之銘言：
:   嗯，剛才我再去查了一下。SGI 以及標準 C++ 所提供的 map
:   其三種 erase()在上述的第一、第二種，其傳回型態是 void,
:   而非如 sequence container 般，是傳回 iterator. 至於
:   VC++提供的 STL 版本是向 Dinkumware 買的，其 map 的這
:   兩個erase() 的確是傳回 iterator.
:   Scott Meyers 在他的 Effective STL 一書中提到說，associative
:   container 的 erase() 在標準中不傳回 iterator, 據解釋，
:   是考慮到這樣會有unacceptable performance penalty。但他
:   和許多人一樣，認為不然。看起來 Dinkumware 就是能夠做到
:   不會有什麼 performance penalty, 所以傳回 iterator。不過
:   這樣一來，就會有移植性的問題了。像是 g++ 就是依照標準，
:   return void.


    那那那 這個問題的標準寫法是什麼呢

    把要 erase 的 keys 存到 vector

    然後 iterate 這個 vector 把 map 裏的 pair erase 掉嗎 ？？？


--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 61.222.148.171

> -------------------------------------------------------------------------- <

作者: khoguan (Khoguan Phuann) 看板: C_and_CPP
標題: Re: [問題] map元素的刪除?
時間: Fri Jul  1 10:48:03 2005

※ 引述《renderer (rendering)》之銘言：
:     那那那 這個問題的標準寫法是什麼呢
:     把要 erase 的 keys 存到 vector
:     然後 iterate 這個 vector 把 map 裏的 pair erase 掉嗎 ？？？

  所謂「標準寫法」其實和原po寫的差不多，只是沒有另外設一個
  暫時變數來存下一個 iterator 的值，而是用 postfix ++ 來做。

  if (/* 符合條件 */)
     child.erase(i++);
  else
     ++i;

  這樣，照說原po的寫法應該也行才對，就用他的程式，加頭加尾
  寫了個完整的小程式測驗，是可以正確執行的。已用推文請他詳
  述他所說的 ++tmp_q1; 執行時會出錯到底是出什麼錯？錯誤訊息
  為何？

  很多人都不曉得要詳列這些該列的資訊，增加有心協助的眾人的
  困擾，無法對症下藥。

--
※ 發信站: 批踢踢實業坊(ptt.cc)
※ 編輯: khoguan         來自: 220.130.208.168      (07/01 10:57)
→ cplusplus:應該用第三種?
→ cplusplus:如果是單純比較KEY的話 用第三種不省掉許多事
→ khoguan:是的。若單純比較key值，就用第三種，直接支援。
> -------------------------------------------------------------------------- <

作者: renderer (rendering) 看板: C_and_CPP
標題: Re: [問題] map元素的刪除? 
時間: Fri Jul  1 12:58:01 2005

※ 引述《khoguan (Khoguan Phuann)》之銘言：
: ※ 引述《renderer (rendering)》之銘言：
: :     那那那 這個問題的標準寫法是什麼呢
: :     把要 erase 的 keys 存到 vector
: :     然後 iterate 這個 vector 把 map 裏的 pair erase 掉嗎 ？？？
:   所謂「標準寫法」其實和原po寫的差不多，只是沒有另外設一個
:   暫時變數來存下一個 iterator 的值，而是用 postfix ++ 來做。
:   if (/* 符合條件 */)
:      child.erase(i++);
:   else
:      ++i;

  對喔  iterator++ 是 iterator 自己先加 然後傳一份原來的給 statement 做處理
  不過在感情上總覺得 它不是掛了嗎 怎麼還有辦法 ++  Orz

  問一個額外的問題 對於 primitive type 如 int
  i++ 編輯器的處理是

    做完 statement 再加 i   還是
    i 自己先加 但是傳一份原本的 i 給 statement 做處理


  感謝


--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 61.222.148.171
推 cloudrick:iterator++是先取值再前進吧 ?!
→ aoc90058:先取值後加 原po搞錯了吧
推 UNARYvvv:這篇問 i++ 的事情還是自己看組語最準確
→ UNARYvvv:renderer 應該很常用 VC 吧? 設斷點執行再ALT+8
推 renderer:我不會組語 orz
推 renderer:我沒有搞錯啦 在這裏的確是先加了
→ renderer:然後取未加前的原值給 erase 用
推 renderer:再想想 cloudrick aoc90058 大大說的也沒錯
→ renderer:先取值再前進  先取值後加
> -------------------------------------------------------------------------- <

作者: khoguan (Khoguan Phuann) 看板: C_and_CPP
標題: Re: [問題] map元素的刪除?
時間: Fri Jul  1 15:04:59 2005

※ 引述《renderer (rendering)》之銘言：
: ※ 引述《khoguan (Khoguan Phuann)》之銘言：
: :   所謂「標準寫法」其實和原po寫的差不多，只是沒有另外設一個
: :   暫時變數來存下一個 iterator 的值，而是用 postfix ++ 來做。
: :   if (/* 符合條件 */)
: :      child.erase(i++);
: :   else
: :      ++i;
:   對喔  iterator++ 是 iterator 自己先加 然後傳一份原來的給 statement 做處理
:   不過在感情上總覺得 它不是掛了嗎 怎麼還有辦法 ++  Orz

  您這種感情是有合理的基礎的。;-Q

:   問一個額外的問題 對於 primitive type 如 int
:   i++ 編輯器的處理是
:     做完 statement 再加 i   還是
:     i 自己先加 但是傳一份原本的 i 給 statement 做處理

  i++ 一般簡單的說法都是「先」取值「再」加一。這只是比較容易
  解釋，也比較容易聽得懂的說法。其實這兩者並無必然的先後關係。

  int i = 10;
  i++;
  cout << i;

  i++ 是一個式子(expression, 而 i++; 多了分號的是 statement)，
  這整個式子會有一個evaluate後的值，這個值當然還是它原來的值(10),
  但是，它另外也會有 side effect，也就是對 i 這個東東做加一的
  動作。所以執行到 cout << i; 這個statement時，i 已經變成了 11。
  但是加一這個動作到底是在那個精確的時間點完成的呢？

  i++; 敘述中的 i++ 是一個 full expression (因為它不是其他
  expression 的 subexpression, 若是 i++ + 1; 這個敘述中的 i++
  就只是 subexpression)。一個 full expression 後面會有一個
  概念上的 sequence point，所有在它之前的 side effect 到達
  這個點時，都必須全部完成（而這個點之後的 side effect 則
  必須尚未開始）。也就是在上一個 sequence point (A) 與下一個
  sequence point (B)之間的所有 side effect 都要在到達 B 時
  完成，不過，並不要求得要剛好就在 B 點完成，只要在這段期間內
  完成即可，而不硬性規定(unspecified)。這是為了給編譯環境依其
  軟硬體特性產生最有效率的機器碼，而容許這種彈性。

  至於最上面那個 child.erase(i++); 要進入那個函式之前，也會有
  一個 sequence point, 所以 i++ 的 side effect 的部份也會完成，
  i 這個 iterator 已經順利的指向下一個 map element 了。而erase()
  函式本身接到的引數是原先的 iterator 值(rvalue)，將它所對應的
  元素刪掉，對 map/set/list 等 node-based container 來說，不會
  讓其他的 iterator(包括已經指向下一個 map element 的 i) 也失效,
  所以 i 可以繼續安全的使用。

  嚴格說來，child.erase(i++); 裡的 ++ 是 overloaded operator function
  不過效果還是和內建的 ++ 類似，都會在進入 erase() 之前就完成。

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.130.208.168
推 jeunder:真熱心, 快去申請板主啦, 還在這不務正業 :(
※ 編輯: khoguan         來自: 220.130.208.168      (07/01 15:36)
推 khoguan:嗚~~ jeunder你們這些高人都不來帶領大家
→ sekya:但是我記得erase正確用法是 i = child.erase( i );
→ sekya:erase的內部動作，說不定會變整個array都變掉。
→ sekya:增刪各元素的時候，理論上iterator都要重取才對。
推 khoguan:map/set 和 vector/deque 不同
推 khoguan:請再看一下 8223 篇
> -------------------------------------------------------------------------- <

作者: renderer (rendering) 看板: C_and_CPP
標題: Re: [問題] map元素的刪除? 
時間: Fri Jul  1 16:37:30 2005

※ 引述《renderer (rendering)》之銘言：
:   對喔  iterator++ 是 iterator 自己先加 然後傳一份原來的給 statement 做處理
:   不過在感情上總覺得 它不是掛了嗎 怎麼還有辦法 ++  Orz


  當 iterator 的型別不是 primitive type 的時候  it++ 的 code 大概是這樣

    it_type it_type::operator ++ (int)
    {
      it_type original = *this;
      ++*this;
      return original;
    }

  的確是先加了再傳一份出來給 statement 使用呀

  aMap.erase(it++);
  在概念上是 先取值再加(先erase再加) 沒錯
  但實作上卻是 先加了再取原值(先加再erase原值)

  所以在感情上很茅盾的

  在概念上 aMap.erase(it++) 在 erase 過程中 it 早就死了  之後要怎麼 ++ 呢
  所以在概念上 會「感覺」 這個寫法是不對的

  但在實作上 先加了再取原值  卻讓 it 金蠶脫殼
  因為這樣 這個寫法可以 work

  aMap.erase(it++)  是合乎了 i++ 的語意原則
  但卻不合刪除動作給人的想像

  在感情上十分茅盾呀...


  所以

    if(/*合乎刪除原則*/)
    {
      aMap.erase(it++);
    }
    else
    {
      ++it;
    }

  似乎沒有

    if(/*合乎刪除原則*/)
    {
      it = aMap.erase(it);
    }
    else
    {
      ++it;
    }

  來得好

  奈何標準 erase 沒有回傳 iterator ...



--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 61.222.148.171
推 khoguan:sequence point的觀念真的不易掌握……
推 renderer:我的觀念有誤 請不要被我誤倒
→ renderer:請參考 khoguan 的解說  及 8235 篇
> -------------------------------------------------------------------------- <

作者: renderer (rendering) 看板: C_and_CPP
標題: Re: [問題] map元素的刪除? 
時間: Fri Jul  1 17:13:02 2005

※ 引述《khoguan (Khoguan Phuann)》之銘言：
:   至於最上面那個 child.erase(i++); 要進入那個函式之前，也會有
:   一個 sequence point, 所以 i++ 的 side effect 的部份也會完成，
:   i 這個 iterator 已經順利的指向下一個 map element 了。而erase()


  這麼說 即使是 int 的 i++  也是先加再留下原值囉 ???


--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 61.222.148.171

> -------------------------------------------------------------------------- <

作者: khoguan (Khoguan Phuann) 看板: C_and_CPP
標題: Re: [問題] map元素的刪除?
時間: Fri Jul  1 18:06:07 2005

※ 引述《renderer (rendering)》之銘言：
: ※ 引述《khoguan (Khoguan Phuann)》之銘言：
: :   至於最上面那個 child.erase(i++); 要進入那個函式之前，也會有
: :   一個 sequence point, 所以 i++ 的 side effect 的部份也會完成，
: :   i 這個 iterator 已經順利的指向下一個 map element 了。而erase()
:   這麼說 即使是 int 的 i++  也是先加再留下原值囉 ???

  之前寫那樣一篇就期望人家理解，的確是強人所難 :)

  我只能先簡單說，並無規定先後，由編譯器自便，但是到達
  sequence point 時，該evaluate的值，該做的 side effect
  都得要已經完成。至於哪個地方要有 sequence point 則有
  明確規定。

--
※ 發信站: 批踢踢實業坊(ptt.cc)
※ 編輯: khoguan         來自: 220.130.208.168      (07/01 22:38)

> -------------------------------------------------------------------------- <

作者: renderer (rendering) 看板: C_and_CPP
標題: Re: [問題] map元素的刪除? 
時間: Fri Jul  1 20:02:34 2005

※ 引述《khoguan (Khoguan Phuann)》之銘言：
: ※ 引述《renderer (rendering)》之銘言：
: :   這麼說 即使是 int 的 i++  也是先加再留下原值囉 ???
:   之前寫那樣一篇就期望人家理解，的確的是強人所難。
:   我只能先簡單說，並無規定先後，由編譯器自便，但是到達
:   sequence point 時，該evaluate的值，該做的 side effect
:   都得要已經完成。至於哪個地方要有 sequence point 則有
:   明確規定。


  我寫了一小段 code 來測試這件事：

    #include <iostream>


    int globalI = 0;

    void fun(int paramI)
    {
        std::cout << globalI << std::endl;
        std::cout << paramI << std::endl;
    }


    int main(int argc, char *argv[])
    {
        fun(globalI++);

        return 0;
    }

  結果是

    1
    0

  globalI++ 是先加了之後留原值給 fun


  所以我多年來 i++ 是「先做完 statement 後加」的觀念是錯的 @@
  好像真的得用 sequence point 的觀念來理解才得體

  所以 面對 aMap.erase(it++) 其實也不必有感情掙扎

  感謝準版主的指點


  另外 i++ + 1  i++ 之後有 sequence point 嗎


--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 61.228.216.130
推 UNARYvvv:我覺得這篇重點是"準板主"那句耶XD,khoguan加油
推 khoguan:我只是個大肉腳，心事啥人知   (淚奔……)
> -------------------------------------------------------------------------- <

作者: crazying (追殺大象) 看板: C_and_CPP
標題: Re: [問題] map元素的刪除? 
時間: Fri Jul  1 22:13:23 2005

※ 引述《khoguan (Khoguan Phuann)》之銘言：
: ※ 引述《renderer (rendering)》之銘言：
: :   這麼說 即使是 int 的 i++  也是先加再留下原值囉 ???
:   之前寫那樣一篇就期望人家理解，的確的是強人所難。
:   我只能先簡單說，並無規定先後，由編譯器自便，但是到達
:   sequence point 時，該evaluate的值，該做的 side effect
:   都得要已經完成。至於哪個地方要有 sequence point 則有
:   明確規定。

剛好今天也遇到一個有趣的情況
想跟版眾請教一下

如果有這種寫法（當然這種寫法不太好  Orz）
if( A++ || B++ )
{
   ...
}

會不會 evaluate B++ 這個 statement
是視 A++ 的 statement 來決定
但是會不會執行 B=B+1(B++) 這個動作
是不是沒有一定的規定呢？

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.112.25.195

> -------------------------------------------------------------------------- <

作者: UNARYvvv (有趣生活) 看板: C_and_CPP
標題: Re: [問題] map元素的刪除? 
時間: Fri Jul  1 22:27:14 2005

※ 引述《crazying (追殺大象)》之銘言：
: 剛好今天也遇到一個有趣的情況
: 想跟版眾請教一下
: 如果有這種寫法（當然這種寫法不太好  Orz）
: if( A++ || B++ )
: {
:    ...
: }
: 會不會 evaluate B++ 這個 statement
         ^^^^^^^^ ^^^
: 是視 A++ 的 statement 來決定

: 但是會不會執行 B=B+1(B++) 這個動作
            ^^^^       ^^^
: 是不是沒有一定的規定呢？


感覺你好像已經自己回答自己了
可否解釋一下你說的那個「執行」是否有另外的意思呢??

A++ 如果被核定是 true 則 B++ 就不會執行啦

不然像是 if ( p!=NULL && *p==SOME_VALUE )
若第一個 expression 被核定為 false 之後還可能判斷第二個 expression
會是場災難的

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 61.70.137.117

> -------------------------------------------------------------------------- <

作者: khoguan (Khoguan Phuann) 看板: C_and_CPP
標題: Re: [問題] map元素的刪除? 
時間: Fri Jul  1 23:13:12 2005

※ 引述《renderer (rendering)》之銘言：
:   另外 i++ + 1  i++ 之後有 sequence point 嗎

  是指 i++ + 1;  嗎？要到 1之後 ;之前才會有一個 sequence point

  由於這個問題真的不容易掌握。在此列出幾個網頁，供有心人探索。

C FAQ 第三節
http://www.eskimo.com/~scs/C-faq/s3.html

上面內容比較簡短，一時不完全瞭解無妨，接著可看這篇深入的解說與分析

C++ Language Note: Control Flow in Expression Evaluation
http://www.fnal.gov/docs/working-groups/fpcltf/Pkg/ISOcxx/doc/Expressions.html

C FAQ 維護者其他的文章
http://www.eskimo.com/~scs/readings/index2.html
特別注意其中的 On precedence vs. order of evaluation
以及 On undefined behavior 那幾篇

以上文章的精微處，不是一般書上看得到的。研讀完後，相信大家
對 C/C++ 基本語法/語意一部份難解的疑問就會豁然開朗。

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 220.130.208.168
→ khoguan:弄懂了以後，要上來分享心得哦 :-)