Chỉ mục kiểu ArrayListOf cho std :: vector in C++?

Question

Tôi đang đi vào C + + từ Java, và có một tình hình thiết kế phổ biến trong đó tôi có một phần tử (không nguyên thủy) mà tôi muốn loại bỏ từ một std :: vector.

trong Java, tôi sẽ viết một cái gì đó như: arrayList.remove (arrayList.indexOf (myClassInstance));

trong C++, với std :: vector, cách tốt nhất/hiệu quả nhất/sạch nhất để làm việc này là gì?

điều tốt nhất tôi có thể nghĩ đến là tạo tham chiếu đến cá thể tôi đang tìm kiếm và sau đó lặp qua vectơ cho đến khi tôi tìm thấy tham chiếu đó. về cơ bản, để so sánh địa chỉ bộ nhớ của từng phần tử trong vectơ với tham chiếu cho đến khi tôi nhận được kết quả phù hợp.

Tôi đang đi đúng hướng? hoặc có cách nào tốt hơn để làm điều này? (có lẽ sử dụng một container std khác nhau, tôi đã chỉ sử dụng std :: vector cho đến nay.)

Answer 1

#include <algorithm> 

std::vector<Foo>::iterator it = std::find(vec.begin(), vec.end(), foo_2b_found); 
if (it != vec.end()) vec.erase(it); 

Answer 2

Sử dụng std::find để tìm phần tử và vector::erase để loại bỏ nó.

std::find về cơ bản lặp qua vectơ để tìm phần tử và bạn không thể làm tốt hơn với vectơ đơn giản (trường hợp tương tự với Java ArrayList). Bạn có nên sử dụng một container khác hay không tùy thuộc vào yêu cầu của bạn.

Answer 3

Nếu bạn muốn tìm kiếm tuyến tính qua các vector sau đó

seq.erase(std::find(seq.begin(), seq.end(), elt)); 

Nếu bạn có một vị và muốn loại bỏ tất cả các mục phù hợp với vị ngữ thì:

seq.erase(std::remove_if(seq.begin(), seq.end(), Pred), seq.end()); 

Không ai trong số những phương pháp này là cách hiệu quả nhất bởi vì chúng yêu cầu tra cứu tuyến tính và ngay cả khi phần tử của bạn được tìm thấy sớm, việc xóa là tốn kém bởi vì nó phải di chuyển tất cả các phần tử khác theo vị trí để giữ cho chúng tiếp tục S.

Sử dụng tiêu chuẩn :: danh sách sẽ giải quyết vấn đề sau: danh sách sẽ là tuyến tính nhưng xóa sẽ là thời gian cố định.

Nếu có thể lưu trữ các phần tử của bạn trong vùng chứa kết hợp sử dụng tra cứu khóa thì sẽ hiệu quả hơn: tra cứu O (log N) và loại bỏ thời gian liên tục.

Bản đồ băm có thể còn tốt hơn nữa, gần với việc tra cứu và loại bỏ thời gian liên tục.

Đối với những gì bạn đang đề xuất, tức là xóa bằng con trỏ của đối tượng, bạn có thể sử dụng tiêu chuẩn :: đặt cho loại T. Sau đó, sử dụng mySet.erase(pt); trong đó pt là con trỏ của bạn. Bạn cần phải quản lý vòng đời của con trỏ của bạn, tất nhiên, nhưng thực tế bạn biết cái nào để xóa khỏi bộ sưu tập của bạn cho thấy bạn có một bản sao của nó ở nơi khác.

Bạn có thể sử dụng std :: set, SharedPtrLess>

nơi bạn xác định SharedPtrLess như sau:

template< typename T > 
struct SharedPtrLess 
{ 
    bool operator()(boost::shared_ptr<T> left, boost::shared_ptr<T> right) const 
    { 
    return std::less<T>()(left.get(), right.get()); 
    } 
};