Làm cách nào để chèn một giá trị mới vào một tập hợp và xóa một giá trị khác cùng một lúc?

Question

Mỗi bộ chứa các phần tử theo thứ tự được chỉ định. Tôi muốn chỉ định một giới hạn về kích thước của một bộ và tự động xóa xóa phần tử cuối cùng nếu một phần tử mới hoàn toàn nhỏ hơn (theo thứ tự) được chèn và kích thước đã chỉ định đã đạt được.

Tất nhiên, tôi có thể làm một cái gì đó như sau:

class bounded_set 
{ 
private: 
    using set = std::set<Key, Compare, Allocator>; 
    using iterator = typename set::iterator; 

public: 
    bounded_set(std::size_t size) 
     : m_size(size) 
    { } 

    std::pair<iterator, bool> insert(Key const& value) 
    { 
     if (m_set.size() < m_size) 
      return m_set.insert(value); 

     auto last = std::prev(m_set.end()); 
     if (Compare()(value, *last)) 
     { 
      m_set.erase(last); 
      return m_set.insert(value); 
     } 
     return std::make_pair(last, false); 
    } 

private: 
    set m_set; 
    std::size_t m_size; 
}; 

Bên cạnh thực tế, rằng bounded_set không phải là tên tốt nhất (kể từ giáp container là một điều nổi tiếng trong thế giới của lập trình đồng thời), Tôi lo lắng về việc cấp phát bộ nhớ trong việc triển khai này. Nhiều khả năng, lúc đầu, không gian được sử dụng bởi last sẽ được giải phóng. Nhưng ngay sau đó, bộ nhớ mới cần được phân bổ cho value.

Điều tôi thực sự muốn làm là sử dụng bộ nhớ được phân bổ cho last và sao chép dữ liệu cho value đến địa điểm này, trong khi vẫn giữ thứ tự.

Answer 1

Nếu tôi hiểu chính xác câu hỏi của bạn, tùy thuộc vào cách cấu trúc dữ liệu cơ bản hoạt động, điều đó không nhất thiết có thể xảy ra mà bạn không phải viết bộ cấp phát bộ nhớ tùy chỉnh hoặc sử dụng bộ đệm từ thư viện. Ví dụ: std::set sử dụng cây đỏ đen làm cấu trúc dữ liệu cơ bản. Do đó vị trí bộ nhớ của các nút và các con trỏ quan hệ đến và đi từ các nút đó được gắn với tổng thứ tự của cây. Bạn không thể tái sử dụng bộ nhớ từ một nút là giá trị "nhỏ nhất" và đặt một giá trị khác ở đó không phải là một giá trị "ít" được sắp xếp hoàn toàn mới mà không phải sắp xếp lại tất cả các con trỏ đến nút đó sao cho nó ở vị trí thích hợp trong cây cho giá trị của nút đó.

Nếu bạn vẫn lo lắng về việc sử dụng bộ nhớ và muốn gắn với STL, thay vì std::set, có thể bạn nên xem xét hàng đợi ưu tiên có độ dài cố định hoặc một thứ gì đó có tính chất sử dụng mảng dựa trên mảng cấu trúc dữ liệu cơ bản để bộ nhớ không được cấp phát liên tục và phân bổ lại cho các nút mới.

Answer 2

Tôi thấy một số tùy chọn cho bạn và cơ hội bị mất bởi ủy ban tiêu chuẩn có thể dễ dàng giải quyết được vấn đề của bạn.

N3586 đề xuất giải pháp cho vấn đề của bạn.

std::pair<iterator, bool> insert(Key const& value) 
{ 
    if (m_set.size() < m_size) 
     return m_set.insert(value); 

    auto last = std::prev(m_set.end()); 
    if (Compare()(value, *last)) 
    { 
     auto temp = m_set.remove(last); 
     *temp = value; 
     return m_set.insert(temp); 
    } 
    return std::make_pair(last, false); 
} 

Trong viết lại giả thuyết này, temp là một node_ptr cho phép truy cập không const đến nút của value_type. Bạn có thể loại bỏ các nút, ghi vào nó, và chèn lại nó, tất cả mà không có bất kỳ phân bổ cho các nút.

Ủy ban đã lịch sự từ chối đề xuất này.

Trình phân bổ tùy chỉnh cho std::set có thể thực hiện thủ thuật một cách ít thanh lịch hơn. Trình phân bổ như vậy sẽ chỉ đơn giản là các nút bộ đệm và insert hiện tại của bạn sẽ hoạt động. Một bất lợi nhỏ với cách tiếp cận này là trong khi phân bổ tùy chỉnh giữ nút của bạn khỏi bị deallocated, nó không thể giữ Key của bạn bị hủy, và sau đó xây dựng, khi bạn thay đổi nó. Một số loại có hiệu quả hơn trong phân công, hơn là họ đang trong một chu kỳ phá hủy xây dựng. Và đôi khi cái cũ có thể là noexcept trong khi cái sau không thể.

Tóm lại, tôi xem cách tiếp cận phân bổ tùy chỉnh là phương sách cuối cùng. Bạn có thể làm cho nó hoạt động.Nhưng phải mất một số mã được hoạch định cẩn thận và không trực quan.

Việc sử dụng số push_heap, pop_heap được lưu ý. Tuy nhiên việc sử dụng nó là khó xử nếu bạn thực sự cần một trình lặp (iterator) cho phần tử được chèn vào hoặc bằng nhau được trả về. Nếu bạn có thể đối phó với một kiểu void trở lại, nó có thể trông giống như:

void insert(Key const& value) 
{ 
    if (m_set.size() < m_size) 
    { 
     m_set.push_back(value); 
     std::push_heap(m_set.begin(), m_set.end(), Compare{}); 
    } 

    if (Compare()(value, m_set.front())) 
    { 
     std::pop_heap(m_set.begin(), m_set.end(), Compare{}); 
     m_set.back() = value; 
     std::push_heap(m_set.begin(), m_set.end(), Compare{}); 
    } 
} 

Nhưng đó là vụng về để tìm kiếm trên đống cho giá trị mới được chèn, và push_heap không cung cấp thông tin này.

Vẫn còn một tùy chọn khác là sắp xếp vectơ + sắp xếp chèn. Bạn sẽ phải tự mình viết, nhưng đó là một nhiệm vụ lập trình tương đối nhỏ. Lý do bạn muốn sắp xếp chèn là bạn sẽ luôn sắp xếp một mảng được sắp xếp ngoại trừ phần tử cuối cùng. Và sắp xếp chèn là tối ưu cho công việc này.

Không có giải pháp nào trong số này là hoàn hảo và không có gì ngoài việc N3586 cung cấp bất kỳ thứ gì tiếp cận giải pháp "ngoài hộp", nghĩa là không yêu cầu nhiều hơn một số dòng mã. Và N3586 không tồn tại. Nếu bạn nghĩ rằng nó nên tồn tại, hãy liên hệ với đại diện cơ thể quốc gia C++ của bạn, và nói với họ như vậy. Hoặc tự mình tham gia vào ủy ban C++ và vận động hành lang cho nó.