Câu hỏi Xóa mục khỏi vectơ, trong khi trong vòng lặp for 'C for' C ++ 11?


Tôi có một vector của IInventory *, và tôi đang lặp qua danh sách bằng cách sử dụng phạm vi C ++ 11 cho, để làm công cụ với mỗi một.

Sau khi làm một số công cụ với một, tôi có thể muốn loại bỏ nó khỏi danh sách và xóa đối tượng. Tôi biết tôi có thể gọi delete trên con trỏ bất cứ lúc nào để làm sạch nó, nhưng cách thích hợp để loại bỏ nó khỏi vector là gì, trong khi trong phạm vi for vòng lặp? Và nếu tôi xóa nó khỏi danh sách thì vòng lặp của tôi có bị vô hiệu không?

std::vector<IInventory*> inv;
inv.push_back(new Foo());
inv.push_back(new Bar());

for (IInventory* index : inv)
{
    // Do some stuff
    // OK, I decided I need to remove this object from 'inv'...
}

76
2018-04-28 04:00


gốc


Nếu bạn muốn được ưa thích, bạn có thể sử dụng std::remove_if với một vị ngữ "làm công cụ" và sau đó trả về true nếu bạn muốn xóa phần tử đó. - Benjamin Lindley
Có một lý do tại sao bạn không thể chỉ cần thêm một bộ đếm chỉ mục và sau đó sử dụng một cái gì đó như inv.erase (index)? - TomJ
@TomJ: Điều đó vẫn sẽ làm hỏng sự lặp lại. - Ben Voigt
@TomJ và nó sẽ là một kẻ giết người hiệu suất - trên mỗi lần xóa, bạn có thể di chuyển tất cả các yếu tố sau khi xóa một. - Ivan
@BenVoigt Tôi khuyên bạn nên chuyển sang std::list phía dưới - bobobobo


Các câu trả lời:


Không, bạn không thể. Dựa trên phạm vi for là khi bạn cần truy cập từng phần tử của vùng chứa một lần.

Bạn nên sử dụng bình thường for vòng lặp hoặc một trong những người anh em họ của nó nếu bạn cần sửa đổi vùng chứa khi bạn đi cùng, truy cập phần tử nhiều lần, hoặc lặp lại theo cách không tuyến tính thông qua vùng chứa.

Ví dụ:

auto i = std::begin(inv);

while (i != std::end(inv)) {
    // Do some stuff
    if (blah)
        i = inv.erase(i);
    else
        ++i;
}

71
2018-04-28 04:02



Sẽ không xóa-loại bỏ thành ngữ áp dụng ở đây? - Naveen
@ Naveen Tôi quyết định không cố gắng làm điều đó bởi vì dường như anh ấy cần phải lặp qua tất cả các mục, làm tính toán với nó, và sau đó có thể loại bỏ nó khỏi container. Xóa-xóa nói rằng bạn chỉ xóa các phần tử mà trả về vị từ true, AFAIU, và nó có vẻ tốt hơn theo cách này để không trộn lẫn logic lặp lại với vị từ. - Seth Carnegie
@SethCarnegie Xoá bỏ-loại bỏ với một lambda cho vị ngữ thanh lịch cho phép rằng (vì đây là đã C ++ 11) - Potatoswatter
Không thích giải pháp này, nó là O (N ^ 2) cho hầu hết các container. remove_if tốt hơn. - Ben Voigt
@ Kolyunya Không có gì tốt vì anh ta không lưu trữ trình kết thúc. - magras


Mỗi lần một phần tử được lấy ra khỏi vectơ, bạn phải giả định các trình vòng lặp tại hoặc sau phần tử đã xóa không còn hợp lệ nữa, vì mỗi phần tử kế thừa thành phần bị xóa được di chuyển.

Một vòng lặp dựa trên phạm vi chỉ là cú pháp cú pháp cho vòng lặp "bình thường" bằng cách sử dụng các trình vòng lặp, do đó, áp dụng ở trên.

Điều đó đang được nói, bạn có thể chỉ đơn giản là:

inv.erase(
    std::remove_if(
        inv.begin(),
        inv.end(),
        [](IInventory* element) -> bool {
            // Do "some stuff", then return true if element should be removed.
            return true;
        }
    ),
    inv.end()
);

45
2018-04-28 04:34



"bởi vì có khả năng là vector đã phân bổ lại khối bộ nhớ trong đó nó giữ các phần tử của nó"Không, một vector sẽ không bao giờ phân bổ lại do cuộc gọi đến erase. Lý do các trình vòng lặp không hợp lệ là vì mỗi phần tử kế thừa thành phần bị xóa được di chuyển. - ildjarn
@ildjarn Tôi đứng sửa chữa, thưa ngài! - Branko Dimitrijevic
Chụp mặc định [&]sẽ là thích hợp, để cho phép anh ta "làm một số công cụ" với các biến địa phương. - Potatoswatter
Điều này trông không đơn giản hơn một vòng lặp dựa trên vòng lặp, ngoài ra bạn phải nhớ bao quanh remove_if với .erase, nếu không thì không có gì xảy ra. - bobobobo
@bobobobo Nếu bằng "vòng lặp dựa trên vòng lặp", ý của bạn là Câu trả lời của Seth Carnegie, đó là O (n ^ 2) trung bình. std::remove_if là O (n). - Branko Dimitrijevic


Bạn lý tưởng không nên sửa đổi vectơ trong khi lặp lại nó. Sử dụng thành phần xóa-xóa. Nếu bạn làm vậy, bạn có thể gặp phải một số vấn đề. Kể từ trong một vector một erase vô hiệu hóa tất cả các trình vòng lặp bắt đầu với phần tử bị xóa lên đến end() bạn sẽ cần đảm bảo rằng các trình vòng lặp của bạn vẫn hợp lệ bằng cách sử dụng:

for (MyVector::iterator b = v.begin(); b != v.end();) { 
    if (foo) {
       b = v.erase( b ); // reseat iterator to a valid value post-erase
    else {
       ++b;
    }
}

Lưu ý rằng bạn cần b != v.end() thử nghiệm như là. Nếu bạn cố gắng tối ưu hóa nó như sau:

for (MyVector::iterator b = v.begin(), e = v.end(); b != e;)

bạn sẽ chạy vào UB từ e không hợp lệ sau lần đầu tiên erase gọi điện.


10
2018-04-28 04:31



@ildjarn: Đúng, đúng! Đó là một lỗi đánh máy. - dirkgently
Đây không phải là thành phần xóa-xóa. Không có cuộc gọi đến std::remove, và nó là O (N ^ 2) không phải O (N). - Potatoswatter
@Potatoswatter: Tất nhiên là không. Tôi đã cố gắng chỉ ra các vấn đề với việc xóa khi bạn lặp lại. Tôi đoán từ ngữ của tôi đã không vượt qua muster? - dirkgently


Có một yêu cầu nghiêm ngặt để loại bỏ các yếu tố trong khi trong vòng lặp đó? Nếu không, bạn có thể thiết lập các con trỏ bạn muốn xóa để NULL và thực hiện một vượt qua vector để loại bỏ tất cả các con trỏ NULL.

std::vector<IInventory*> inv;
inv.push_back( new Foo() );
inv.push_back( new Bar() );

for ( IInventory* &index : inv )
{
    // do some stuff
    // ok I decided I need to remove this object from inv...?
    if (do_delete_index)
    {
        delete index;
        index = NULL;
    }
}
std::remove(inv.begin(), inv.end(), NULL);

5
2018-04-28 22:18





xin lỗi vì đã necroposting và cũng xin lỗi nếu c ++ chuyên môn của tôi được trong cách trả lời của tôi, nhưng nếu bạn cố gắng lặp qua từng mục và thực hiện các thay đổi có thể (như xóa một chỉ mục), hãy thử sử dụng một backwords cho vòng lặp.

for(int x=vector.getsize(); x>0; x--){

//do stuff
//erase index x

}

khi xóa chỉ mục x, vòng lặp tiếp theo sẽ dành cho mục "ở phía trước" lần lặp cuối cùng. tôi thực sự hy vọng điều này đã giúp ai đó


1
2018-05-25 20:09



chỉ cần không quên khi sử dụng x để truy cập vào một chỉ số nhất định, làm x-1 lol - lilbigwill99


OK, tôi đến trễ, nhưng dù sao đi nữa: Xin lỗi, không sửa lại những gì tôi đã đọc - nó  có thể, bạn chỉ cần hai trình lặp:

std::vector<IInventory*>::iterator current = inv.begin();
for (IInventory* index : inv)
{
    if(/* ... */)
    {
        delete index;
    }
    else
    {
        *current++ = index;
    }
}
inv.erase(current, inv.end());

Chỉ cần sửa đổi giá trị mà một iterator trỏ tới không làm mất hiệu lực bất kỳ trình lặp nào khác, vì vậy chúng ta có thể làm điều này mà không phải lo lắng. Thực ra, std::remove_if (Gcc thực hiện ít nhất) làm một cái gì đó rất giống nhau (sử dụng một vòng lặp cổ điển ...), chỉ cần không xóa bất cứ điều gì và không xóa.

Tuy nhiên, hãy lưu ý rằng đây không phải là luồng an toàn (!) - tuy nhiên, điều này cũng áp dụng cho một số giải pháp khác ở trên ...


1
2018-03-15 12:29



Cái quái gì vậy. Đây là một quá mức cần thiết. - Kesse
@ Kesse thật sao? Đây là thuật toán hiệu quả nhất bạn có thể nhận được với vectơ (không quan trọng nếu vòng lặp dựa trên phạm vi hoặc vòng lặp vòng lặp cổ điển): Bằng cách này, bạn di chuyển từng phần tử trong vectơ nhiều nhất một lần và lặp lại toàn bộ vectơ một lần. Bạn sẽ di chuyển các phần tử tiếp theo bao nhiêu lần và lặp lại trên vectơ nếu bạn đã xóa từng phần tử phù hợp qua erase (miễn là bạn xóa nhiều hơn một phần tử duy nhất, tất nhiên)? - Aconcagua


Tôi sẽ hiển thị ví dụ, ví dụ bên dưới xóa các phần tử lẻ khỏi vectơ:

void test_del_vector(){
    std::vector<int> vecInt{0, 1, 2, 3, 4, 5};

    //method 1
    for(auto it = vecInt.begin();it != vecInt.end();){
        if(*it % 2){// remove all the odds
            it = vecInt.erase(it);
        } else{
            ++it;
        }
    }

    // output all the remaining elements
    for(auto const& it:vecInt)std::cout<<it;
    std::cout<<std::endl;

    // recreate vecInt, and use method 2
    vecInt = {0, 1, 2, 3, 4, 5};
    //method 2
    for(auto it=std::begin(vecInt);it!=std::end(vecInt);){
        if (*it % 2){
            it = vecInt.erase(it);
        }else{
            ++it;
        }
    }

    // output all the remaining elements
    for(auto const& it:vecInt)std::cout<<it;
    std::cout<<std::endl;

    // recreate vecInt, and use method 3
    vecInt = {0, 1, 2, 3, 4, 5};
    //method 3
    vecInt.erase(std::remove_if(vecInt.begin(), vecInt.end(),
                 [](const int a){return a % 2;}),
                 vecInt.end());

    // output all the remaining elements
    for(auto const& it:vecInt)std::cout<<it;
    std::cout<<std::endl;

}

đầu ra aw dưới đây:

024
024
024

Hãy nhớ, phương pháp erase sẽ trả về trình lặp tiếp theo của trình lặp được truyền.

Từ đây , chúng tôi có thể sử dụng phương pháp tạo nhiều hơn:

template<class Container, class F>
void erase_where(Container& c, F&& f)
{
    c.erase(std::remove_if(c.begin(), c.end(),std::forward<F>(f)),
            c.end());
}

void test_del_vector(){
    std::vector<int> vecInt{0, 1, 2, 3, 4, 5};
    //method 4
    auto is_odd = [](int x){return x % 2;};
    erase_where(vecInt, is_odd);

    // output all the remaining elements
    for(auto const& it:vecInt)std::cout<<it;
    std::cout<<std::endl;    
}

Xem ở đây để xem cách sử dụng std::remove_if. https://en.cppreference.com/w/cpp/algorithm/remove


1
2017-07-29 01:56





Một giải pháp thanh lịch hơn nhiều sẽ là chuyển sang std::list (giả sử bạn không cần truy cập ngẫu nhiên nhanh).

list<Widget*> widgets ; // create and use this..

Sau đó, bạn có thể xóa bằng .remove_if và một hàm C ++ trong một dòng:

widgets.remove_if( []( Widget*w ){ return w->isExpired() ; } ) ;

Vì vậy, ở đây tôi chỉ viết một functor chấp nhận một đối số ( Widget*). Giá trị trả về là điều kiện để loại bỏ Widget* từ danh sách.

Tôi thấy cú pháp này ngon miệng. Tôi không nghĩ mình sẽ sử dụng remove_if cho std :: vectơ -- có quá nhiều inv.begin() và inv.end() tiếng ồn ở đó bạn có thể sử dụng tốt hơn xóa một số nguyên chỉ mục hoặc chỉ là một thao tác xóa dựa trên vòng lặp thông thường cũ (như được hiển thị bên dưới). Nhưng bạn không nên thực sự được loại bỏ từ giữa một std::vector rất nhiều, nên chuyển sang list cho trường hợp này thường xuyên giữa danh sách xóa được thông báo.

Tuy nhiên, lưu ý tôi không có cơ hội gọi delete trên Widget*đã bị xóa. Để làm điều đó, nó sẽ trông như thế này:

widgets.remove_if( []( Widget*w ){
  bool exp = w->isExpired() ;
  if( exp )  delete w ;       // delete the widget if it was expired
  return exp ;                // remove from widgets list if it was expired
} ) ;

Bạn cũng có thể sử dụng vòng lặp dựa trên vòng lặp thường xuyên như sau:

//                                                              NO INCREMENT v
for( list<Widget*>::iterator iter = widgets.begin() ; iter != widgets.end() ; )
{
  if( (*iter)->isExpired() )
  {
    delete( *iter ) ;
    iter = widgets.erase( iter ) ; // _advances_ iter, so this loop is not infinite
  }
  else
    ++iter ;
}

Nếu bạn không thích độ dài của for( list<Widget*>::iterator iter = widgets.begin() ; ..., bạn có thể dùng

for( auto iter = widgets.begin() ; ...

0
2018-04-30 02:50



Tôi không nghĩ bạn hiểu remove_if trên một std::vector thực sự hoạt động và cách nó giữ độ phức tạp với O (N). - Ben Voigt
Điều đó không quan trọng. Đang xóa từ giữa một std::vector sẽ luôn trượt từng phần tử sau phần tử bạn đã xóa một phần tử, tạo một std::list một lựa chọn tốt hơn nhiều. - bobobobo
Không, nó sẽ không "trượt từng phần tử lên một". remove_if sẽ trượt từng phần tử lên theo số lượng các khoảng trống được giải phóng. Vào thời điểm bạn sử dụng bộ nhớ cache, remove_if trên một std::vector có khả năng vượt trội hơn so với việc xóa std::list. Và bảo tồn O(1) truy cập ngẫu nhiên. - Ben Voigt
Sau đó, bạn có một câu trả lời tuyệt vời trong việc tìm kiếm một câu hỏi. Câu hỏi này nói về việc lặp lại danh sách, là O (N) cho cả hai vùng chứa. Và loại bỏ các phần tử O (N), cũng là O (N) cho cả hai thùng chứa. - Ben Voigt
Không cần đánh dấu trước; hoàn toàn có thể làm điều này trong một lần chuyền. Bạn chỉ cần theo dõi "yếu tố tiếp theo cần được kiểm tra" và "vị trí tiếp theo cần điền". Hãy nghĩ về nó như xây dựng một bản sao của danh sách, được lọc dựa trên vị từ. Nếu biến vị ngữ trả về true, bỏ qua phần tử, nếu không thì sao chép nó. Nhưng bản sao danh sách được thực hiện tại chỗ và việc hoán đổi / di chuyển được sử dụng thay vì sao chép. - Ben Voigt


Tôi nghĩ tôi sẽ làm như sau ...

for (auto itr = inv.begin(); itr != inv.end();)
{
   // Do some stuff
   if (OK, I decided I need to remove this object from 'inv')
      itr = inv.erase(itr);
   else
      ++itr;
}

0
2018-01-23 21:21