14 Nisan 2020 Salı

STL Min/Max Algoritmaları

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

std::max Açıklaması
std::max iki şekilde kullanılabilir.
1. İki tane değerin büyük olanını bulmak için
2. Bir değer dizisindeki en büyük olanı bulmak için. Bu kullanım std::max_element() ile aynı gibi görünse de, std::max_element() bir iterator aralığı alır.

std::max - T + T
İmzası şöyle.
template<class T> constexpr const T& max(const T& a, const T& b);
Açıklaması şöyle. max iki sayının en büyüğünü bulmak için kullanılır.
Requires: Type T is LessThanComparable (Table 18).
Returns: The larger value.
RemarksReturns the first argument when the arguments are equivalent.
İki girdi eşit ise ilkini dönmesi beklenir. Şu kod doğru değil.
template<typename T>
T max (T a, T b)
{
  // if b < a then yield a else yield b
  return  b < a ? a : b;
}
Örnek
Eğer birinci ve ikinci parametre tipleri aynı değilse hata alabiliriz. Bu durumda derleyiciye yardımcı olmak için T tipini belirtmek gerekir. Elimizde şöyle bir kod olsun.
vector<long long int> a= ...; 
Burada derleyici ilk parametre olan 0 değerini int, ikinci parametreyi ise long long int algılayıp hata verecektir. Hatayı düzeltmek için şöyle yaparız.
std::max<long long int>(0, a[i]-b[i])
std::max - std::initializer_list
Örnek
Şöyle yaparız.
w = std::max({ x, y, z });
Eskiden şöyle yapardık.
w = std::max(std::max(x, y), z);
std::max_element metodu
İlk max nesneyi döndürür. std::max_element metodu yazısına taşıdım.

std::min - T + T
std::min yazısına taşıdım

std::min_element metodu
Bir iterator döner. Dizi içindeki en küçük elemanı bulur.
Örnek
Şöyle yaparız
vector<double> v{2, 0, 4};
double minT = *std::min_element(v.begin(), v.end(),
                               [](double i1, double i2) {
                                   return i1 < i2;
                               });
Örnek
Aradığımı değere en yakın noktayı bulmak için şöyle yaparız
std::map<int, int> mymap;

mymap[1] = 10;
mymap[2] = 40;
mymap[3] = 100;
mymap[4] = 200;
mymap[5] = 500;

int wantedvalue = 50;


auto it = std::min_element( mymap.begin(), mymap.end(),
  [&](const auto &p1, const auto &p2)
  {
    return
      std::abs(( long )p1.second - wantedvalue) < 
      std::abs(( long )p2.second - wantedvalue);
  });

std::cout << "The closest value of " << wantedvalue << " in the map is located";
std::cout << " on " << it->first << " and is " << it->second << std::endl;

std::minmax metodu
std::tuple döndürür
Örnek
Şöyle yaparız.
using namespace std::string_view_literals;

auto [a, b] = std::make_pair("foo"sv, "bar"sv);
std::tie(a, b) = std::minmax({a, b});
std::cout << "a: " << a << ", b: " << b << '\n';
Çıktı olarak şunu alırız.
a: bar, b: foo
std::minmax_element metodu
Açıklaması şöyle. Bu metod en son max element'i döndürüyor. std::max_element() ise ilk max elementi döndürür.
The definition problem surfaces when one tries to design a minmax_element, using the procedure proposed in (Cormen, Leiserson, Rivest: "Introduction to Algorithms", section 9.1). It should be possible to derive an algorithm using only 3n/2 comparisons if [first,last) has n elements, but if one tries to write a function called first_min_first_max_element() which returns both std::min_element and std::max_element in a pair, the trivial implementation does not work. The problem, rather subtly, is about equal elements: I had to think for a while to find a way to perform only three comparisons per pair and return the first min and first max elements. For a long time, it seemed any attempts at doing so would consume four comparisons per pair in the worst case. This implementation achieves three.
It is not possible (or even desirable) to change the meaning of max_element, but it is still beneficial to provide a function called minmax_element, which returns a pair of min_element and max_element. Although it is easy enough to call min_element and max_element, this performs 2(n-1) comparisons, and necessitates two passes over the input. In contrast, minmax_element will perform the fewer comparisons and perform a single pass over the input. The savings can be significant when the iterator type is not a raw pointer, or even is just a model of the InputIterator concept (although in that case the interface would have to be changed, as the return type could not be copied, so one could e.g. return a value).
Şöyle yaparız.
int arr[10];
...
auto minmax = minmax_element(begin(arr), end(arr));

cout << "min element " << *(minmax.first) << "\n";
cout << "max element " << *(minmax.second) << "\n";



Hiç yorum yok:

Yorum Gönder