Xóa các phần tử trong stl :: vector bằng cách sử dụng các chỉ mục

Question

Tôi có một stl::vector<int> và tôi cần xóa tất cả các phần tử tại các chỉ mục đã cho (vector thường có chiều cao cao). Tôi muốn biết, đó là cách hiệu quả nhất để thực hiện một hoạt động như vậy trong tâm trí rằng thứ tự của vector gốc cần được bảo toàn.

Mặc dù, tôi đã tìm thấy bài đăng có liên quan về vấn đề này, một số trong số họ cần xóa một số single element hoặc multiple elements trong đó remove-erase idiom dường như là một giải pháp tốt. Trong trường hợp của tôi, tuy nhiên, tôi cần xóa nhiều phần tử và vì tôi đang sử dụng chỉ mục thay vì giá trị trực tiếp, bạn không thể áp dụng remove-erase idiom, phải không? Mã của tôi được đưa ra dưới đây và tôi muốn biết nếu nó có thể làm tốt hơn về hiệu quả?

bool find_element(const vector<int> & vMyVect, int nElem){ 
    return (std::find(vMyVect.begin(), vMyVect.end(), nElem)!=vMyVect.end()) ? true : false; 
} 

void remove_elements(){ 

    srand (time(NULL)); 

    int nSize = 20; 
    std::vector<int> vMyValues; 
    for(int i = 0; i < nSize; ++i){ 
      vMyValues.push_back(i); 
    } 

    int nRandIdx; 
    std::vector<int> vMyIndexes; 
    for(int i = 0; i < 6; ++i){ 
     nRandIdx = rand() % nSize; 
     vMyIndexes.push_back(nRandIdx); 
    } 

    std::vector<int> vMyResult; 
    for(int i=0; i < (int)vMyValues.size(); i++){ 
     if(!find_element(vMyIndexes,i)){ 
      vMyResult.push_back(vMyValues[i]); 
     } 
    } 
} 

Answer 1

Tôi nghĩ rằng nó có thể hiệu quả hơn, nếu bạn chỉ cần sắp xếp các chỉ mục của bạn và sau đó xóa các phần tử đó khỏi vectơ của bạn từ mức cao nhất đến thấp nhất. Việc xóa chỉ mục cao nhất trong danh sách sẽ không làm mất hiệu lực các chỉ mục thấp hơn mà bạn muốn xóa, vì chỉ các phần tử cao hơn các chỉ mục đã xóa sẽ thay đổi chỉ mục của chúng.

Nếu nó thực sự hiệu quả hơn sẽ phụ thuộc vào tốc độ phân loại. Một chuyên gia nữa về giải pháp này là, bạn không cần một bản sao của vector giá trị của bạn, bạn có thể làm việc trực tiếp trên vectơ ban đầu. mã nên giống như thế này:

... fill up the vectors ... 

sort (vMyIndexes.begin(), vMyIndexes.end()); 

for(int i=vMyIndexes.size() - 1; i >= 0; i--){ 
    vMyValues.erase(vMyValues.begin() + vMyIndexes[i]) 
} 

Answer 2

để tránh di chuyển các yếu tố giống nhau nhiều lần, chúng ta có thể di chuyển chúng bởi các dãy giữa chỉ số xóa

// fill vMyIndexes, take care about duplicated values 
vMyIndexes.push_back(-1); // to handle range from 0 to the first index to remove 
vMyIndexes.push_back(vMyValues.size()); // to handle range from the last index to remove and to the end of values 
std::sort(vMyIndexes.begin(), vMyIndexes.end()); 
std::vector<int>::iterator last = vMyValues.begin(); 
for (size_t i = 1; i != vMyIndexes.size(); ++i) { 
    size_t range_begin = vMyIndexes[i - 1] + 1; 
    size_t range_end = vMyIndexes[i]; 
    std::copy(vMyValues.begin() + range_begin, vMyValues.begin() + range_end, last); 
    last += range_end - range_begin; 
} 
vMyValues.erase(last, vMyValues.end()); 

T.B. cố định một lỗi, nhờ vào Steve Jessop mà kiên nhẫn cố gắng chỉ cho tôi nó

Answer 3

Nếu bạn muốn đảm bảo mọi thành phần chỉ được di chuyển một lần, bạn có thể lặp lại từng phần tử, sao chép chúng. vùng chứa, không sao chép những thứ bạn muốn xóa và sau đó xóa vùng chứa cũ và thay thế bằng vùng chứa mới :)

Answer 4

Điều bạn có thể làm là tách vectơ (thực sự là bất kỳ vùng chứa không liên kết nào) trong hai nhóm, một nhóm tương ứng với các chỉ mục cần xóa và một phần chứa phần còn lại.

template<typename Cont, typename It> 
auto ToggleIndices(Cont &cont, It beg, It end) -> decltype(std::end(cont)) 
{ 
    int helpIndx(0); 
    return std::stable_partition(std::begin(cont), std::end(cont), 
     [&](typename Cont::value_type const& val) -> bool { 
      return std::find(beg, end, helpIndx++) != end; 
    }); 
} 

sau đó bạn có thể xóa từ (hoặc lên đến) các điểm chia để xóa (chỉ giữ) các yếu tố tương ứng với chỉ số

std::vector<int> v; 
v.push_back(0); 
v.push_back(1); 
v.push_back(2); 
v.push_back(3); 
v.push_back(4); 
v.push_back(5); 

int ar[] = { 2, 0, 4 }; 
v.erase(ToggleIndices(v, std::begin(ar), std::end(ar)), v.end()); 

• Nếu 'giữ chỉ bởi chỉ số' hoạt động là không cần thiết, bạn có thể sử dụng remove_if insted của stable_partition (O (n) vs O (nlogn) phức tạp)
• Để làm việc cho mảng C là vùng chứa hàm lambda phải là [&] (declty pe (* (std :: bắt đầu (tiếp))) const & val) -> bool {return std :: find (beg, end, helpIndx ++)! = end; } nhưng sau đó.xóa() phương pháp là không còn là một lựa chọn

Answer 5

Erase-loại bỏ nhiều yếu tố ở các chỉ số cho

C++ 11 phiên bản sử dụng std :: di chuyển (xem dòng nhận xét-out cho C++ 98 phiên bản):

template <class ForwardIt, class SortedIndicesForwardIt> 
inline ForwardIt remove_at(
    ForwardIt first, 
    ForwardIt last, 
    SortedIndicesForwardIt indices_fist, 
    SortedIndicesForwardIt indices_last) 
{ 
    // flag elements to keep 
    typedef typename std::vector<bool> Flags; 
    Flags is_keep(
     static_cast<Flags::size_type>(std::distance(first, last)), true); 
    for(; indices_fist != indices_last; ++indices_fist) 
     is_keep[static_cast<Flags::size_type>(*indices_fist)] = false; 
    // move kept elements to beginning 
    typedef typename Flags::const_iterator FlagsIt; 
    ForwardIt dest = first; 
    for(FlagsIt keepIt = is_keep.begin(); first != last; ++first, ++keepIt) 
     if(*keepIt) 
      *dest++ = std::move(*first); // *dest++ = *first; //<= c++98 
    return dest; 
} 

Cách sử dụng Ví dụ:

std::vector<int> vec = /*...*/; 
std::vector<size_t> indices = /*...*/; 

std::sort(indices.begin(), indices.end()); 
vec.erase(
    remove_at(vec.begin(), vec.end(), indices.begin(), indices.end()), 
    vec.end() 
); 

Ghi chú:

• chỉ số cần phải được sắp xếp
• cờ mỗi phần tử (giữ hoặc loại bỏ) sử dụng một vector tạm bools
• Live example