STL Veri Yapısı - Sorted Vector

Giriş
Scott Meyers'in Effective STL kitabında bir vector'ü sıralı tutma anlatılıyor. Sıralı vector'lerde lower_bound, upper_bound, equal_range gibi algoritmalar kullanılabilir.

Kitapta sıralama için ve arama (lookup) işlemi için şu kod kullanılıyor.

typedef pair<string, int> Data; // type held in the "map"

class DataCompare { // class for comparison
public:
  bool operator()(const Data& lhs, const Data& rhs) const  //for sorting
  {
    return keyLess(lhs.first, rhs.first);
  }
  bool operator()(const Data& Ihs, const Data::first_type& k) const //for lookups
  { //(form 1)
    return keyLess(lhs.first, k);
  }
  bool operator()(const Data::first_type& k, const Data& rhs) const //for lookups
  { // (form 2)
    return keyLessfk, rhs.first);
  }
....

Hem sıralı hem de eleman sayısı sınırlı bir vector şöyle. Bana en yakın ilk 20 noktayı saklayabilirim. vector'ün uzunluğu 20'yi geçerse bana en uzak elemanı std::max_element ile bulup siliyorum.

template <typename T, typename Compare = std::less<T>>
std::vector<T> filter_vector(std::vector<T> v, 
                             typename std::vector<T>::size_type n) {
    std::vector<T> q;
    for (auto i: v) {
        q.push_back(i);
        if (q.size() > n) {
            q.erase(std::max_element(q.begin(), q.end(), Compare()));
        }
    }
    return q;
}