Có thùng chứa được sắp xếp trong STL

Question

TẤT CẢ,

Có thùng chứa được sắp xếp trong STL không? Ý tôi là như sau:

Tôi có một std :: vector trong đó Foo là một lớp được tạo tùy chỉnh. Tôi cũng có một so sánh của một số loại mà sẽ so sánh các lĩnh vực của lớp Foo.

Bây giờ, ở đâu đó trong mã của tôi Tôi đang làm:

std::sort(myvec.begin(), myvec.end(), comparator); 

mà sẽ sắp xếp các vector theo các quy tắc tôi xác định trong so sánh.

Bây giờ tôi muốn chèn phần tử của lớp Foo vào vectơ đó. Nếu tôi có thể tôi muốn chỉ cần viết:

mysortedvector.push_back(Foo()); 

và điều gì sẽ xảy ra là vector sẽ đặt yếu tố mới này theo so sánh với vị trí của nó.

Thay vào đó, ngay bây giờ tôi phải viết:

myvec.push_back(Foo()); 
std::sort(myvec.begin(), myvec.end(), comparator); 

mà chỉ là một sự lãng phí thời gian, kể từ khi vector đã được sắp xếp và tất cả tôi cần là để đặt các yếu tố mới một cách thích hợp.

Bây giờ, vì bản chất chương trình của tôi, tôi không thể sử dụng tiêu chuẩn :: map <> vì tôi không có cặp khóa/giá trị, chỉ là một vectơ đơn giản.

Nếu tôi sử dụng stl :: list Tôi lại cần phải gọi sắp xếp sau mỗi lần chèn.

Cảm ơn bạn đã đưa ra bất kỳ đề xuất nào.

Answer 1

Có, std::set, std::multiset, std::map và std::multimap đều được sắp xếp bằng cách sử dụng std::less làm thao tác so sánh mặc định. Cấu trúc dữ liệu cơ bản được sử dụng thường là cây tìm kiếm nhị phân cân bằng, chẳng hạn như cây đỏ đen. Vì vậy, nếu bạn thêm một phần tử vào các cấu trúc dữ liệu này và sau đó lặp qua các phần tử được chứa, đầu ra sẽ được sắp xếp theo thứ tự sắp xếp. Sự phức tạp của việc thêm các phần tử N vào cấu trúc dữ liệu sẽ là O (N log N), hoặc tương tự như sắp xếp một vectơ của các phần tử N sử dụng bất kỳ kiểu phức tạp O (log N) chung nào.

Trong trường hợp cụ thể của bạn, vì bạn không có cặp khóa/giá trị, std::set hoặc std::multiset có lẽ là đặt cược tốt nhất của bạn.

Answer 2

Tôi không nghĩ rằng các chức năng tồn tại trong STL, một std :: vector chỉ có thể loại với phân vùng, nth_element, stable_partition, partial_sort, stable_sort và loại.

Bạn tuy nhiên có thể tạo ra một wrapper cho std :: vector

#include <vector> 

template <class T> 
class VectorSortWrapper 
{ 
public: 
    std::vector<T> m_VectorSorted; 

    void InsertSortedAscending(T item) 
    { 
     for(int i = 0; i < m_VectorSorted.size(); i++) 
     { 
      if(item.GetOrderValue() <= m_VectorSorted[i].GetOrderValue()) 
      { 
       m_VectorSorted.insert(m_VectorSorted.begin() + i, item); 
       break; 
      }  
     } 
    } 

    void InsertSortedDecending(T item) 
    { 
     for(int i = 0; i < m_VectorSorted.size(); i++) 
     { 
      if(item.GetOrderValue() >= m_VectorSorted[i].GetOrderValue()) 
      { 
       m_VectorSorted.insert(m_VectorSorted.begin() + i, item); 
       break; 
      }  
     } 
    } 

};