std::map.erease metodu

erase metodu - C++98

İmzası şöyle

void erase (iterator pos);           // (until C++11)

Açıklaması şöyle

The erase operations of the node-based containers (maps, sets, lists) invalidate only iterators and references to the element that was erased, but not any other iterators.

Yani sadece erase edilen eleman'a olan iterator bozulur. Bir başka thread içinde diğer elemanlara iterator varsa bunlar etkilenmez.

STL içindeki bazı veri yapıları kendisine ait erase() metoduna geçilen iterator nesnesini otomatik olarak ilerletiyor. Ancak map bu veri yapılarından değil. erase() metodu void dönüyor. Dolayısıyla döngü içinde bir şey silmek istiyorsak aşağıdakine benzer bir kod parçası kullanmamız gerekli.

for (it = tableMap.begin(); it != tableMap.end(); )
{
    if (tableId == it->first.first) { tableMap.erase(it++); }
    else                            { ++it; }
}

erase metodu - C++11
İmzası şöyle. Iterator const kabul ediliyor.

iterator erase (const_iterator pos ); // (since C++11)

Metod artık iterator dönüyor. Şöyle yaparız.

auto it = m_map.erase(beginIt, endIt);

erase metodu - C++17
İmzası şöyle. Niçin const'luktan sonra bu metod gerekti bilmiyorum.

iterator erase (iterator pos );       // (since C++17)

erase ile silme

Açıklaması şöyle. Yani silinen elemana iterator geçersiz hale gelir.

References and iterators to the erased elements are invalidated. Other references and iterators are not affected.

Örnek - reverse iterator

reverse iterator ile direkt silme doğru değil. reverse iterator önce base() metodu ile forward itertor halie getirilir ve daha sonra silinir. Şöyle yaparız. 

map<int,int> mymap = {{1,0},{2,1},{9,2},{10,3},{11,4}};
for(auto it = mymap.rbegin(); it != mymap.rend(); ){
    auto v = --(it.base());
    v = mymap.erase(v);
    it = map<int,int>::reverse_iterator(v);
}

std::map [] operator

Giriş

Bu operator eğer aranan key yoksa default constructor kullanarak bir value ile doldurur. Açıklaması şöyle

T& operator[](const key_type& x);

1 Effects: If there is no key equivalent to x in the map, inserts value_type(x, T()) into the map.

Eğer value tipinin default constructor metodu yoksa hata alırız. Aşağıdaki kod derlenmez!

std::map< int, std::reference_wrapper< foo > > my_map;
foo a;
my_map[ 0 ] = std::ref( a );

Örnek - primitive tip

Şöyle yaparız

std::map<std::string,std::size_t> counters;
//...
counters[key]++;

Açıklaması şöyle

++counters[key]; is completely valid. std::map::operator[] inserts a value-initialized element if the key does not exist in the map. This is the idiomatic way of doing what you explained.

std::map.at metodu

Giriş

C++11 ile geliyor.

at metodu, [] operator ile benzer. Bu metod aynı std::vector'de olduğu gibi eğer verilen anahtar değer mevcut değilse exception atar.

Returns a reference to the mapped value of the element identified with key k.

If k does not match the key of any element in the container, the function throws an out_of_range exception.

Metodun için şuna benzer. lower_bound ile >= koşulunu sağlayan bir anahtar aranılır. Böyle bir anahtar varsa belirtilen değer ve bulunan anahtarın eşit olup olmadıkları karşılaştırılır.

mapped_type&
at(const key_type& __k)
{
    iterator __i = lower_bound(__k);
    if (__i == end() || key_comp()(__k, (*__i).first))
        __throw_out_of_range(__N("map::at"));
    return (*__i).second;
}

Örnek

Şöyle yaparız

std::map<int, int> test;
try {
  test.at(10);
} catch(std::out_of_range& e) {
  ...
}

 

std::map.find metodu

Giriş

std::map.find() bir iterator döner. Bu sonucu std::map.end() ile karşılaştırmak gerekir. Klasik kullanımda şöyle yaparız

const std::map<int, std::string> numberToStr{{1, "one"}, {2,"two"}};
int main() {
  auto it = numberToStr.find(2);
  if (it ==numberToStr.end()){
    return 1;
  }
  const auto&[_, str] = *it;
  std::cout << str;
}

Bu kullanımı std::optinal ile birleştirmek mümkün. Şöyle bir yardım metod olsunn

template <typename Key, typename Value, typename... Rest>
std::pair<std::optional<Key>, std::optional<Value>> my_find(const std::map<Key, Value,
   Rest...>& map, const Key& to_find)
{
  auto it = map.find(to_find);
  if (it == map.end())
    return {};
  else
    return {it->first, it->second};
}

Kullanmak için şöyle yaparız

const auto&[_, str] = my_find(numberToStr, 2);
// _ is std::optional<int>, str is std::optional<str>
if (!str){
  return 1;
}
std::cout << *str;

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