STL Veri Yapısı - map

Giriş
set, multiset, map, multimap associative container olarak anılırlar. STL'deki tüm veri yapıları gibi Map te non-instrusive bir sınıftır.

Non-Intrusive Veri Yapısı Nedir?
Eğer bir veri yapısı içerdiği veri nesnesinden yardım istemiyorsa yani aşağıdaki gibiyse non-intrusive - işe karışmayan - olarak adlandırılır. Aşağıdaki kodda kullanıcı nesnesi düğümler için kendi sınıfında alan sağlamak zorunda değil.

struct MyData {
    // data to be stored
};

template <class T>
class RbTree {
    // implementation
};

// usage:
RbTree<MyData> treeInstance;

Intrusive Veri Yapısı Nedir?
Eğer bir veri yapısı işleyebilmek için kullanıcı tarafından sağlanan veri nesnesinden yardım istiyorsa intrusive - işe karışan - olarak adlandırılır. Aşağıdaki kodda kullanıcı nesnesinin left ve right düğümler için değişken sağlaması gerekiyor.

struct MyDataNode {
    MyDataNode* rbe_left;
    MyDataNode* rbe_ight;
    char rbe_color;
    // data to be stored
};

template <class Entry>
class RbTree {
    // implementation
};

// usage:
RbTree<MyDataNode> treeInstance;

Map Tanımlama
Referans tipler value olarak tanımlanamaz. Aşağıdaki kod derlenmez.

std::map<std::string, Location&> m;

Static İnitialization
C++11 ile static initalization yapmak kolay. Eğer C++11 kullanmıyorsak, boost::assign kullanılabilir.
Süslü parantezler içine key,value değerleri yazılır. Şöyle yaparız.

#include <map>
using namespace std;

map<int, char> m = {{1, 'a'}, {3, 'b'}, {5, 'c'}, {7, 'd'}};

Daha karışık tanımlamalarda şöyle yaparız.

static  std::map<std::string, std::map<std::string, std::string>>  MyMap = {
   {"AA", {{"busy_timeout", "test"}}},
   {"BB", {{"cache_size", "10000"}}}
};

Map'i Dolaşmak
Iterator ve auto ile map'i dolaşmak için şöyle yaparız.

for (auto& x: mymap) {
  std::cout << x.first << " => " << x.second << '\n';
}  

Sıralama
Sıralama için Strict Weak Ordering kullanılır.
Default Comparator
map veri yapısına dışarıdan comparator vermezsek std::less()'i kullanır.

template<
    class Key,
    class T,
    class Compare = std::less<Key>,
    class Allocator = std::allocator<std::pair<const Key, T> >
> class map;

Dolayısıyla map küçükten büyüğe doğru sıralama yapar. Kendi comparator'umuzu tanımlamak istersek 3 seçeneğinimiz var. Başka bir STL Comparator tanımlamak, Functor kullanmak, Function Pointer kullanmak.

< operator tanımlamak
Bir çok primitif tipin ve STL sınıfının < operatörü var. Eğer kendi key sınıfımıza da tanımlamak istersek ya global bir < operatörü tanımlarız ya da member operator yaparız.

bool operator<(const Box &left, const Box &right)
{
    return (left.i < right.i);
}

STL Comparator Tanımlamak
Büyükten küçüğe doğru sıralama yapması için 3. parametreye sıralama algoritması verilebilir. Örnekte std::greater veriliyor.

std::map<double, std::deque<Object>, std::greater<double>> m;

Neden std::greater nesnesini yaratmıyoruz ? Örnekte map template'a compare işlemi için verilen std::greater, default constructor içinde

explicit map (const key_compare& comp = key_compare().....);

şeklinde yaratıldığı için çalışıyor.

Functor Tanımlamak
Örnek'te functor tanımlanıyor ve yine STL örneğinde olduğu gibi functor nesnesini yaratmamız gerekmiyor. Burada dikkat edilmesi gereken nokta, functor'ın operatörü const olmalı. Yani verilen key'leri değiştirmeyeceğini garanti etmeli!

#include<map>
#include<string>

template<typename KeyType>
struct ReverseSort {
  bool operator() (const KeyType& key1, const KeyType& key2) const {
    return (key1 > key2);
  }
};

int main() {
  using namespace std;
  map<int, string> map1;
  map<int, string, ReverseSort<int> > map2 (map1.cbegin(), map1.cend());

  return 0;
}

Function Pointer Tanımlamak
Function Pointer kullanmak diğer seçenekler arasında en zor olanı. Kendi function pointer'ımızı kullanmak istesersek, aşağıdaki Case Insensitive örneğinde olduğu gibi function pointer imzasını template içinde tanımlamak ve constructor metoduna da function metodunu geçmek gerekirdi.
Case Insensitive Key
Bazen map'in anahtar alanı string ise ve örnekteki gibi case insensitive anahtar kullanmak istiyorsak

std::map<std::string, 
         std::string, 
         bool(*)(const std::string&, const std::string&)> 
     my_map(case_insensitive_string_cmp);

my_map["Helloooo"] = "foo";
my_map["HELLOOOO"] = "bar";
std::cout << my_map["hellOOOO"] << std::endl;

Case insensitive karşılaştırma ise aşağıda.

#include <cctype>
#include <algorithm>
#include <string>

bool case_insensitive_cmp(char lhs, char rhs)
{
  return std::toupper(lhs) < std::toupper(rhs);
}

bool case_insensitive_string_cmp(const std::string& lhs, 
                                 const std::string& rhs)
{
  return std::lexicographical_compare(lhs.begin(), 
                                      lhs.end(),
                                      rhs.begin(),
                                      rhs.end(),
                                      case_insensitive_cmp);
}

Map'in Metodları
at metodu

at metodu yazısına taşıdım

emplace metodu
Açıklaması şöyle

Inserts a value_type object t constructed with std::forward<Args>(args)... if and only if there is no element in the container with key equivalent to the key of t.

Yani anahtar değer mevcutsa ekleme işlemi gerçekleşmez.

The insertion only takes place if no other element in the container has a key equivalent to the one being emplaced (keys in a map container are unique).

C++11 ile gelen bu metod ile map'in içine direkt nesne yerleştirilebilir.

std::map<int,std::string> m;

std::string val {"hello"};

m.emplace(1, val);

emplace metodu arama yapmadan önce value nesnesini içinde oluşturur. Aslında standartta böyle bir kural yok ancak çoğu kütüphane böyle çalışıyor. C++17 ile try_emplace metodu ile nasıl çalışması gerektiği de ortaya konacak.
Bu yüzden aşağıdaki kodda iki defa 1 çıktısını görürüz.

class HugeConstructor
{
public:
  HugeConstructor(int n)
  {
    std::cout << n << std::endl;
  }
};

int main()
{
    std::map<int, HugeConstructor> m;
    m.emplace(1, 10);
    m.emplace(1, 10);

    return 0;
}

Eğer key değeri zaten mevcutsa aşağıdaki kod leak verebilir.

struct X {};
std::map<int, std::unique_ptr<X> > map;

void f(int x) {
    map.emplace(x, new X);
}

erase metodu 

erase metodu yazısına taşıdım.

extract metodu - C++17

Node handle denen bir kavram geldi. Böylece map içindeki bir girdiyi bir başka veri yapısına taşımak mümkün. Benzer bir metod sd::set içinde de mevcut.
Örnek
Şöyle yaparız.

std::vector<std::pair<std::string, double>> v;
std::map<std::string, double> m{{"aLongString", 1.0},
                                {"anotherLongString", 2.0}};

auto extracted_value = m.extract("aLongString");
v.emplace_back(std::make_pair(std::move(extracted_value.key()),
                              std::move(extracted_value.mapped())));

extracted_value = m.extract("anotherLongString");
v.emplace_back(std::make_pair(std::move(extracted_value.key()),
                              std::move(extracted_value.mapped())));

find metodu

find metodu yazısına taşıdım.

insert metodu - pair
make_pair ile kullanılır.

my_map.insert(std::make_pair(0, std::ref(a)));

İşlemin başarılı olup olmadığıno kontrol etmek için şöyle yaparız.

std::map<int, char> m;
auto ret = m.insert(std::make_pair(1, 'A'));
if (ret.second)
  std::cout << "it worked" << std::endl;

İşlem başarısız ise mevcut pair'e iterator döner. Bu iterator kullanılabilir. Şöyle yaparız.

std::map<int, char> m;
auto ret = m.insert(std::make_pair(1, 'A'));
if (!ret.second)
    ret.first->second = 'A'; // assign the value in case it went wrong

insert metodu - iterator
İki map'i şöyle birleştiririz.

#include <map>
#include <iostream>

int main()
{
    std::map<int, int> v1 = {{1, 1}, {2, 1}, {3, 1}, {4, 1}, {5, 1}};
    std::map<int, int> v2 = {{3, 2}, {4, 2}, {5, 2}, {6, 2}, {7, 2}};
    std::multimap<int, int> dest1 {v1.begin(), v1.end()};

    dest1.insert(v2.begin(), v2.end());

    for (const auto &i : dest1) {
        std::cout << i.first << ':' << i.second << ' ';
    }
    std::cout << '\n';
}

Çıktı olarak şunu alırız.
Output: 1:1 2:1 3:1 3:2 4:1 4:2 5:1 5:2 6:2 7:2

Sonuç olarak bir pair döner. Bu nesnenin second alanı çağrının başarılı olup olmadığını belirtir.

auto result = map.insert(make_pair(...,...));
if (result.second) {
  // insertion succeeded
}

insert_or_assign metodu
Key değeri yoksa yaratır, varsa yeni değeri atar, Şöyle yaparız.

std::map<int, ValueClass> value_classes;
value_classes.insert_or_assign(std::make_pair(0, ValueClass());

lower_bound
Verilen değerden >= olan ilk değeri döndürür. Map veri yapısı daha verimli olmak için std::lower_bound()'dan farklı olarak kendisi içinde aynı metodu tanımlamış.

merge metodu
Şöyle yaparız

template<typename K, typename V, typename F>
void mergeWithConflicts(std::map<K, V>& base, std::map<K, V> toMerge, F combine) {
  base.merge(toMerge);

  // All that's left in toMerge is conflicting keys
  for (const auto& [k, v] : toMerge) { 
    base[k] = combine(base[k], toMerge[k]);
  }
}

rbegin

Metodun için şöyle

reverse_iterator rbegin()
{
    return reverse_iterator(end());
}

En sonuncu veriye şöyle erişilir.

auto& myKey = myMap.rbegin()->first;

Aynı şeyi şöyle de yapabiliriz.

auto& myKey = std::prev(myMap.end())->first;

size

Eskiden C++ standarsında list,map gibi veriyapıları için "should be constant time" cümlesi kullanıldığı için bazı C++ kütüphanelerinde komik bir şekilde size() metodu O(n) çalışıyordu. Hatta bir projede bunu bilmediğimiz için çok ciddi performans problemi de yaşamıştık. C++11 ile bu cümle "shall be constant time" olarak değiştirildi. Artık size() metodo O(1)'de çalışıyor.

try_emplace metodu

Açıklaması şöyle. Eğer key değeri varsa move işlemini yapmaz.

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)

C++17 ile geliyor. Eğer key değeri varsa parametreyi dikkate almaz ve mevcut value değerini döner. Eğer key değeri yoksa value nesnesini yaratır. Bu metodun çıkış noktası kafa karışıklığını gidermek. Karışıklışı gösteren bir örnek şöyle.

std::map<std::string, std::unique_ptr<Foo>> m;
m["foo"] = nullptr;

auto ptr = std::make_unique_ptr<Foo>;
auto res = m.emplace("foo", std::move(ptr));

assert(ptr);    // ??? (may or may not fire)

try_emplace() yerine daha farklı bir şey olan insert_or_asssign() kullanılabilir. Şöyle yaparız.

m.try_emplace(0, std::cref(a));
m.insert_or_assign(0, std::cref(a));

Örnek
Şöyle yaparız.

auto& newvec = mymap.try_emplace(42, 100, true).first->second;

Şu kod ile aynıdır.

auto it = mymap.find(42); // search for an element with the key 42
bool is_key_in_map = it != mymap.end();
// if the element with the given key exists, then return it, otherwise
// construct it
auto& newvec = is_key_in_map? it->second: 
            mymap.emplace(42, std::vector<bool>(100, true)).first->second;

Örnek

Şöyle yaparız

struct Test
{
    Test(int i, int j){}
};
std::map<int, Test> tmap;
tmap.try_emplace(10, 10, 10);

upper_bound metodu
Verilen değerden >olan ilk değeri döndürür.
Örnek
Elimizde şöyle bir kod olsun. > koşulunu sağlayan ilk değeri buluruz. Sonra bir geriye giderek <= koşulunu sağlayan ilk değeri buluruz. Java'daki TreeMap.floorKey() ile aynı işlevi gerçekleştirir.

#include <map>

template<typename Key, typename Value>
const Key& floorKey(const std::map<Key, Value>& input,
                    const Key& key, const Key& default_value = {})
{
    auto it = input.upper_bound(key);

    return it == input.begin()
        ? default_value
        : (--it)->first;
}

Şöyle yaparız.

std::map<int, int> map =
{
  { 10, 100 },
  { 20, 200 },
  { 30, 300 },
  { 40, 400 },
  { 50, 500 },
  { 60, 600 },
  { 70, 700 },
  { 80, 800 },
};


std::cout << floorKey(map, 5, -1) << '\n'
          << floorKey(map, 9, -1) << '\n'
          << floorKey(map, 10, -1) << '\n'
          << floorKey(map, 11, -1) << '\n'
          << floorKey(map, 90, -1) << '\n';

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

-1 -1 10 10 80

Map'in Operatörleri

[] operator

std::map [] operator yazısına taşıdım