STL Bounding Algoritmaları

Giriş
STL algoritmalarını işlevlerine göre gruplamak anlamayı çok daha kolaylaştırıyor. Algoritmaları kullanmak için

#include <algorithm>

yapmak gerekir.

Tüm Bounding Algoritmaları
Tüm algoritmaların çalışmasını gösterin şekil şöyle

+- lb(2) == ub(2)       +- lb(6)        +- lb(8)
|        == begin()     |  == ub(6)     |   +- ub(8) == end()
V                       V               V   V
+---+---+---+---+---+---+---+---+---+---+---+
| 3 | 4 | 4 | 4 | 4 | 5 | 7 | 7 | 7 | 7 | 8 |
+---+---+---+---+---+---+---+---+---+---+---+
    ^               ^                       ^
    |               |                       |
    +- lb(4)        +- ub(4)                +- lb(9) == ub(9) == end()

    |- eq-range(4) -|

Tüm Bounding Algoritmaları Verinin Sıralı Olmuş Olmasını Bekler
STL'de şu algoritmalar dizinin sıralı olmasını bekler.

binary_search, lower_bound, upper_bound, equal_range, set_union, set_intersection, set_difference, set_symmetric_difference, inplace_merge, includes.

equal_range
std::equal_range yazısına taşıdım.

lower_bound
std::lower_bound yazısına taşıdım.

upper_bound

std::upper_bound yazısına taşıdım.

lower_bound ve  upper_bound beraber

Açıklaması şöyle

Think of lower_bound and upper_bound as returning the range of where that item would be placed in the sorted array. If the search item doesn't occur in the sequence, they will always return the same iterator.

lower_bound + upper_bound ve lexicographic karşılaştırma
Normalde lower_bound ve upperd_bound denince hep sayısal büyüklük küçüklük kullanılıyormuş gibi bir algı var. Büyüklük küçüklük karşılaştırması lexicographic yani sözlük sıralamasına ve hatta tarihlere göre bile yapılabilir. Elimizde şöyle bir yapı olsun.

struct value {
  string code;
  string date;
  string name;
};

date alanı YYYY-MM-DD HH:MM:SS formatında tarih olsun. Belirtilen iki tarih arasındaki nesneler şöyle bulunur. lower_bound başlangıç tarihinden >= olan ilk değeri, upper_bound ise bitiş tarihinden > olan ilk değeri döndürdüğü için [from - to ] kapalı aralığındaki tarihler bulunur.

std::vector<value> get_between(const std::vector<value>& v,
        const std::string& from, const std::string& to)
{
  value fromv { "", from, "" };
  auto begin = std::lower_bound(v.begin(), v.end(), fromv,
    [](const auto& lhs, const auto& rhs) {
        return lhs.date < rhs.date;
  });

  value tov { "", to, "" };
  auto end = std::upper_bound(v.begin, v.end(), tov,
    [](const auto& lhs, const auto& rhs) {
        return lhs.date < rhs.date;
  });

  return std::vector<value>(begin, end);
}