STL Veriyapısı - list

Giriş
Şu satırı dahil ederiz.

#include <list>

Bu veriyapısının verimliliği konusunda bazı olumsuz görüşler var.

std::list is an extremely inefficient class that is rarely useful. It performs a heap allocation for every element inserted into it, thus having an extremely high constant factor, particularly for small data types.

Allocator
Açıklaması şöyle. Eğer kendi allocator metodumuzu vermezsek std::allocator kullanılır.

std::list<T> allocates its internal nodes (say class Node<T>) using std::allocator_traits<Allocator>::rebind_alloc<Node<T>>, which is, by default, Alloc<Node<T>, Args> if Allocator is Alloc<T, Args>. So, when std::allocator is used, std::list<T> will use std::allocator<Node<T>> to allocate its internal nodes.

If you want to provide a custom allocator template Alloc and don't want std::list<T> to use Alloc<Node<T>>, you can provide a member template rebind for Alloc, then the allocator Alloc::rebind<Node<T>>::other will be used.

back metodu
En sondaki elemanı verir. Şöyle yaparız.

if (list.back()->Foo()) {...}

begin ve end metodları
Şöyle yaparız.

for (auto it = list.begin(); it != list.end(); it++)
  std::cout << *it <<std::endl;
}

clear metodu
Şöyle yaparız. Listedeki nesnelerin pointer olmamasın dikkat etmek gerekir.

list.clear();

emplace_back metodu
Bu metodun döndürdüğü sonuç tipi C++17 ile değiştirildi. C++17 ile referans dönüyor. Şöyle yaparız.

struct A {
  
  constexpr int v() const {
    return std::is_same<
      decltype(std::list<A>{}.emplace_back()),
      A&>::value ? 17 : 14;
    }
};

empty metodu
Şöyle yaparız.

while (!list.empty()) {
  list.pop_back();
}

erase metodu - iterator
İmzası şöyle

iterator erase( const_iterator pos );

Şöyle yaparız.

list <char> &myList = ...;
list<char>::iterator itr;

for (itr= myList.begin(); itr != myList.end(); itr++ )
{ 
  if (*itr == 'w' || *itr == 'W'){
    itr = myList.erase (itr);
  }
}

erase metodu - reverse iterator
Reverse iterator ile silmek için base metodunu kullanırız. Açıklaması şöyle.

The base iterator refers to the element that is next (from the std::reverse_iterator::iterator_type perspective) to the element the reverse_iterator is currently pointing to.

Şöyle yaparız.

auto pos = list.crbegin(); // Last element in the list
mylist.erase((pos+1).base()); 

erase metodu - indeks
Örnek ver

merge metodu
std::merge yerine kendi metodunu sunar. İki tane listemiz olsun.

std::list<int> list1 = { 5,9,0,1,3,4 };
std::list<int> list2 = { 8,7,2,6,4 }; 
list1.sort();
list2.sort();
std::cout << "list1:  " << list1 << "\n";
std::cout << "list2:  " << list2 << "\n";
list1.merge(list2);
std::cout << "merged: " << list1 << "\n";

Bu listeyi sıralayıp birleştirdikten sonra çıktı olarak şunu alırız. merge() metodu splice metodundan fakrlıdır çünkü merge list2'nin içeriğini bozmaz. splice() ise list2'nin içeriğini list1'e aktarır.

list1:   0 1 3 4 5 9
list2:   2 4 6 7 8
merged:  0 1 2 3 4 4 5 6 7 8 9

push_back metodu
En sona yeni bir eleman ekler. Şöyle yaparız.

list.push_back("2");

pop_back metodu
En sondaki elemanı listeden çıkarır. Şöyle yaparız.

list.pop_back();

reverse metodu
O(n)'de çalışır.

remove_if metodu
std::remove_if yerine kendi remove_if metodunu sunar. Şöyle yaparız.

list.remove_if([&](const MyClass& foo){
    return ...;
});

sort metodu
std::sort yerine kendi sort metodunu sunar. Mergesort kullandığı için maliyeti O(n logn).

splice metodu - concatinate
splice uç uca eklemek demek. Maliyeti O(1) çünkü aslında şöyle bir işleme benziyor. Node'ları yer değiştirerek iki listeyi birleştiriyor.

list1->back->next = list2->front;
list1->size += list2->size;

splice() metodu merge metodundan farklıdır çünkü splice sonucunda list2 boşalırken merge list2'yi boşaltmaz.
Örnek
Şöyle yaparız.  list1'e list2 eklenir

std::list<int> list1 = { 5,9,0,1,3,4 };
std::list<int> list2 = { 8,7,2,6,4 }; 

list1.splice(list1.end(), list2);

Örnek
Bu metod LRU listelerinde çok işe yarar. Şöyle yaparız.

template <typename Key, typename Value>
class lru_cache {
 public:
  using value_type = typename std::pair<Key, Value>;
  using value_it = typename std::list<value_type>::iterator;
  using operation_guard = typename std::lock_guard<std::mutex>;

  lru_cache(size_t max_size) : max_cache_size{max_size} {
    if (max_size == 0) {
      max_cache_size = std::numeric_limits<size_t>::max();
    }
  }

  void Put(const Key& key, const Value& value) {
    operation_guard og{safe_op};
    auto it = cache_items_map.find(key);

    if (it == cache_items_map.end()) {
      if (cache_items_map.size() + 1 > max_cache_size) {
        // remove the last element from cache
        auto last = cache_items_list.crbegin();

        cache_items_map.erase(last->first);
        cache_items_list.pop_back();
      }

      cache_items_list.push_front(std::make_pair(key, value));
      cache_items_map[key] = cache_items_list.begin();
    }
    else {
      it->second->second = value;
      cache_items_list.splice(cache_items_list.cbegin(), cache_items_list,
                              it->second);
    }
  }

  const Value& Get(const Key& key) const {
    operation_guard og{safe_op};
    auto it = cache_items_map.find(key);

    if (it == cache_items_map.end()) {
      throw std::range_error("No such key in the cache");
    }
    else {
      cache_items_list.splice(cache_items_list.begin(), cache_items_list,
                              it->second);

      return it->second->second;
    }
  }

 private:
  mutable std::list<value_type> cache_items_list;
  std::unordered_map<Key, value_it> cache_items_map;
  size_t max_cache_size;
  mutable std::mutex safe_op;
};

splice - iterator + list + iterator
Örnek
l2'nin başından itibaren eklemek için şöyle yaparız.

list<int> l1{1, 2, 3, 5, 6};
list<int> l2{2, 6, 8};
auto it = l1.begin();
advance(it, 2);

l2.splice(l2.begin(), l1, it);

unique metodu

std::unique yerine kendi unique metodunu sunar. Elimizde iki liste olsun. İki listeyi birleştirip, sıralar ve unique metodunu çağırırsak

std::list<int> list1 = { 5,9,0,1,3,4 };
std::list<int> list2 = { 8,7,2,6,4 }; 

list1.splice(list1.end(), list2);
list1.sort();
list1.unique();

çıktı olarak şunu alırız.

0 1 2 3 4 5 6 7 8 9