STL Veri Yapısı - set

Giriş
Şu satırı dahil ederiz.

#include <set>

Karşılaştırma İşlemi
Set karşılaştırma işlemi için Strict Weak Ordering kullanılır.

Big(O) Maliyeti
Ekleme ve silme işlemi oldukça ucuz. Açıklaması şöyle.

operation         std::set          std::vector
insert            log(N)            N
erase             log(N)            N

Tanımlama
Örnek - lambda
Şöyle yaparız.

auto different_cmp = [](int i, int j) -> bool {
  return j < i;
};

std::set<int, decltype(different_cmp)> integers(different_cmp);

integers.insert(3);
integers.insert(4);
integers.insert(1);

Constructor
Şöyledir

std::set<Foot> s;

Constructor - iterator
C++17 ile template argument deduction yapılabilir. Şöyle yaparız.

std::set s1 = {1,2,3,4}; 
std::set s2(s1.begin(), s1.end());

begin metodu
Set iterator'leri her zaman const özelliğine sahiptir. Döngü ile dolaşmak için şöyle yaparız.

std::set<Foo> s;

for (const Foo& f : s) {
  ...
}

count metodu
Bir değişkenin std::set içinde olup olmadığını anlamak için kullanılır. Aslnda bu metodun ismi contains olmalıymış.
Örnek
Şöyle yaparız.

std::set<int> accept { 1, 4, 6, 8, 255, 42 };
int x = 1;

if (!accept.count(x))
{
    // ...
}

Örnek
Şöyle yaparız.

bool contains (int i) {
  return std::set<int>({11, 62, -11, 110022, 22002}).count(i);
}

end metodu

Açıklaması şöyle.

Returns an iterator to the element following the last element of the container. This element acts as a placeholder; attempting to access it results in undefined behavior.

end metodu sadece iterator karşılaştırma için kullanılır. end() çağrısının döndürdüğü iterator'ün değerine erişmeye çalışmak tanımsızdavranıştır. Şu metod tanımsız davranışa sebep olur.

std::set<int> s {1, 2, 3};
cout << *s.end() << endl;

equal_range metodu
Bu metod sadece generic kod yazılabilsin diye var. Aslında std::set tekil elemanlar içerdiği için generic olmyana kodlarda kullanmak mantıklı değil.

extract metodu - iterator
C++17 ile geldi. std::map için de benzer bir metod var. Bir düğümü kopyalamaya gerek kalmadan başka bir veriyapısına kopyalamayı kolaylaştırır. Açıklaması şöyle.

Before C++17, you need to erase and insert again, which incurs a key copy plus node deallocation and allocation. After, you can extract the node, modify it, and reinsert it, which is free.

Örnek
Bir std::set'i başka bir std::vector'e kopyalamak için şöyle yaparız.

vector.reserve(set.size());
for (auto it = set.begin(); it != set.end(); ) {
    vector.push_back(std::move(set.extract(it++).value()));
}

find metodu
Örnek
Bu metodu kullanmak std::find() metodundan çok daha hızlı.

Örnek
Şöyle yaparız.

std::pair<int,int> p1(1,0);
std::pair<int,int> p2(2,1);
std::set<std::pair<int,int>> s;
s.insert(p1);
s.insert(p2);
auto it = s.find(p1);
std::cout << it->first << "," << it->second <<std::endl;

insert metodu
Bir pair döner. Insert işlemi başarılıysa - yani eleman mevcut değilse - pair'in second alanı true döner.
Örnek
Şöyle yaparız.

while (cin >> s)
  if (mySet.insert(s).second) {...}

Örnek
pair'in birinci elemanı itertor'ü döner. Şöyle yaparız.

std::set<int> s;

int i = 10;

auto p = s.insert(temp);
if (p.second) { // insertion succeed

  auto it = p.first;

  std::cout << "Inserted: " << *it << '\n';

  if (it != s.begin()) { // not the first, there is a previous element
    auto it1 = std::prev(it);
    std::cout << "Previous: " << *it1 << '\n';
  }
  else {
    std::cout << "Previous: None\n";
  }

  auto it2 = std::next(it);
  if (it2 != s.end()) { // there is a next element
    std::cout << "Next: " << *it2 << '\n';
  }
  else {
    std::cout << "Next: None\n";
  }
}

Örnek
Insert işlemi std::move ile birlikte kullanılırsa ve insert() başarısız olursa eklenmeye çalışılan nesne rvalue olsa bile değişmiş olabilir.

uto coll = std::set{ "hello"s };
auto s = "hello"s;
coll.insert(std::move(s));
assert("hello"s == s); // Always OK?

try_emplace metodu
Açıklaması şöyle.

Unlike insert or emplace, these functions do not move from rvalue arguments if the insertion does not happen, which makes it easy to manipulate maps whose values are move-only types, such as std::map<std::string,std::unique_ptr<foo>>. In addition, try_emplace treats the key and the arguments to the mapped_type separately, unlike emplace, which requires the arguments to construct a value_type  (that is, a std::pair)