STL Veri Yapısı - Vector Eleman Silme Metodları

erase metodu

erase() metodu silinen elemendan bir sonraki elemanı gösteren bir iterator döner. Erase edilen nesnelerin destructor metodları çağırılır. Metodun imzası şöyledir.

iterator erase (const_iterator position);
iterator erase (const_iterator first, const_iterator last); 

Girdi olarak iterator beklediği için şu kod derlenmez.

vector<int> v{1, 2, 3};
v.erase(&v[0]);

Iterator invalidation rule şöyle der

every iterator and reference after the point of erase is invalidated

Complexity: The destructor of T is called the number of times equal to the number of the elements erased, but the move assignment operator of T is called the number of times equal to the number of elements in the vector after the erased elements.

1. O(n)'de silmek - Erase Remove Idiom
Erase Remove Idiom yazısına taşıdım.

2. O(1)'de silmek

Eğer elemenların sırası önemli değilse, erase metodu yerine O(1)'de çalışan sondaki elemanı silinen elemanın yerine taşıyan şu yöntem kullanılabilir.

0 1 2 3 4 5 6

eğer 3. elemanı silersek vector şöyle olur

0 1 2 6 4 5

Kod şöyle yazılabilir.

vec [i] = std::move(vec.back());
vec.pop_back();

pop_back metodu
Sondaki elemanı siler. Elemanın primitive tip değilse destructor'ı çağrılır. Eğer elema primitive tipse belki vector'ün bellek alanında yaşamaya devam eder ancak vector boyunu küçülttüğü için at() metodu ile erişmek istersek exception alırız. Metod şöyledir.

void pop_back()
{
  --this->_M_impl._M_finish;
  this->_M_impl.destroy(this->_M_impl._M_finish);
}

Genelde şöyle yaparız.

auto val = vec.back();
vec.pop_back();

pop_back void döndüğü için şu kod derlenmez.

auto val = vec.pop_back();

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;
}