Xóa các phần tử cụ thể trong tiêu chuẩn std :: map

Question

Tôi muốn xóa một số phần tử trong sơ đồ std :: của tôi.
Tôi đã viết kỹ thuật xóa + remove_if mà tôi luôn làm với các vùng chứa chuỗi khác.
Nhưng nó không được biên dịch với bản đồ. Tại sao?
Và tôi có thể thực hiện công việc này bằng cách nào?

std::map<int, int> m; 

bool foo(const std::pair<int, int>& p) 
{ 
    return p.second > 15; 
} 

int _tmain(int argc, _TCHAR* argv[]) 
{ 
    m.insert(make_pair(0, 0)); 
    m.insert(make_pair(1, 10)); 
    m.insert(make_pair(2, 20)); 
    m.insert(make_pair(3, 30)); 

    m.erase(
     remove_if(m.begin(), m.end(), foo), 
     m.end()); // compile error 

    return 0; 
} 

Answer 1

Viết nó như thế này cho bản đồ, vì remove_if sẽ không làm việc cho map lặp (nó chỉ đơn thuần là đặt yếu tố vi phạm ở cuối, và map lặp không cho phép cho việc này):

template <typename Map, typename F> 
void map_erase_if(Map& m, F pred) 
{ 
    typename Map::iterator i = m.begin(); 
    while ((i = std::find_if(i, m.end(), pred)) != m.end()) 
     m.erase(i++); 
} 

hoặc nếu bạn muốn một lớp lót:

template <typename Map, typename F> 
void map_erase_if(Map& m, F pred) 
{ 
    for (typename Map::iterator i = m.begin(); 
     (i = std::find_if(i, m.end(), pred)) != m.end(); 
     m.erase(i++)); 
} 

Answer 2

Thành ngữ này chỉ hoạt động cho chuỗi như container - mục trong một bản đồ (kết hợp) có thể không được tái đặt hàng (phím không thay đổi - vì vậy làm thế nào bạn có thể có thể mong đợi để di chuyển một mục để một số vị trí khác - ví dụ như kết thúc). Các cách chính xác để làm điều này là để tìm sự xâm nhập và loại bỏ nó - tức là it = map.find(); map.erase(it++)

Answer 3

Vì std::map không phải là "chứa chuỗi" :) remove_if sẽ cố gắng để đưa các yếu tố vô dụng đến cuối bản đồ, nhưng điều này sẽ gây ra vi phạm cấu trúc dữ liệu ngầm (cây đỏ đen trong hầu hết các trường hợp) của bản đồ. Cấu trúc dữ liệu ngầm định xác định vị trí của mỗi phần tử trong bản đồ và đó là lý do tại sao remove_if không được phép cho std::map.

Bạn nên xóa các phần tử từ std::map cái khác (hoặc cho một số khoảng) trong vòng lặp.

Somethin như thế này:

it = m.begin(); 
while ((it = std::find_if(it, m.end(), pred)) != m.end()) 
    m.erase(it++); 

Answer 4

"Với container chuỗi khác" là lỗi của bạn - map là một kết chứa! Trong container kết hợp, yếu tố này được xác định bởi chính họ (như trái ngược với trật tự chèn của họ trong các thùng chứa chuỗi), và bạn xóa các yếu tố bằng phím:

m.erase(12); 

Tẩy xoá bởi giá trị quan trọng có mức độ phức tạp tương tự như tra cứu (ví dụ O (log n) cho bản đồ, O (1) cho bản đồ không có thứ tự, vv). Ngoài ra, bạn có thể xóa bằng trình lặp trong thời gian không đổi. Xóa một iterator làm mất hiệu lực mà iterator, nhưng không có những người khác (một lần nữa không giống như trong các thùng chứa chuỗi), vì vậy nếu bạn muốn để lặp qua một bản đồ, thành ngữ điển hình là thế này:

for (auto it = m.cbegin(); it != m.cend();) // no "++"! 
{ 
    if (it->second > 15) // your own condition goes here 
    { 
    m.erase(it++); 
    } 
    else 
    { 
    ++it; 
    } 
} 

Answer 5

Hãy thử một cái gì đó như thế này

#include <iostream> 
#include <map> 
#include <algorithm> 

class foo 
{ 
public: 
    enum CompType { GREATER=1, LESS=-1 }; 
    foo(int nVal=15, enum CompType ctype=GREATER) 
    : m_nVal(nVal) 
    , m_bGreater(ctype==GREATER) 
    { 
    } 
    bool operator()(std::pair<int, int> p) 
    { 
     if (m_bGreater) 
      return p.second > m_nVal; 
     else 
      return p.second < m_nVal; 
    } 
private: 
    int m_nVal; 
    bool m_bGreater; 
}; 

void MapRemove(std::map<int, int> &m, foo &pred) 
{ 
    auto itr = std::find_if(m.begin(), m.end(), pred); 
    while (itr != m.end()) 
     itr = std::find_if(m.erase(itr), m.end(), pred); 
} 

int main(int argc, char *argv[]) 
{ 
    std::map<int, int> m; 

    m.insert(std::make_pair(0, 0)); 
    m.insert(std::make_pair(1, 10)); 
    m.insert(std::make_pair(2, 20)); 
    m.insert(std::make_pair(3, 30)); 

    MapRemove(m, foo()); 

    for (auto itr=m.begin(); itr!=m.end(); ++itr) 
     std::cout << "(" << itr->first << ", " 
        << itr->second << ")" << '\n'; 

    return 0; 
} 

Answer 6

Nhưng nó không được biên dịch với bản đồ. Tại sao?

Khi sử dụng remove_if, loại trình lặp không tham chiếu phải đáp ứng các yêu cầu của CopyAssignable. Đó là nó có thể được chỉ định một giá trị khác.

Đối với std::map<int, int> giá trị là std::pair<const int, int> đại diện cho cặp giá trị khóa của bản đồ và không phải là CopyAssignable. Lý do cho điều này const int cho khóa là cách bản đồ hoạt động nội bộ như những người khác đã chỉ ra.

Bằng cách này bạn sẽ nhận được các lỗi biên dịch tương tự cho thùng chứa chuỗi như thế này:

std::vector<std::pair<const int, int>>;