6 Mart 2019 Çarşamba

STL Searching Algoritmaları

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

adjacent_find metodu
İki tane denk eleman buluncaya kadar aramaya devam eder.

Örnek
Şöyle yaparız.
auto next = std::adjacent_find(v.begin(), v.end(), std::not_equal_to<Foo>());
Örnek
Şöyle yaparız. Yanyana iki eleman aynı işaret sahipse -örneğin pozitif ise - predicate false döner ve iterator ilerler. Negatif sayıya denk gelince adjacent_find bu değerin iteratorünü döndürür.
template<typename ForwardIt>
std::size_t getLongestSameSignSequenceLength(ForwardIt first, ForwardIt last)
{
  auto const signdiff = [](auto a, auto b){ return (a < 0) != (b < 0); };

  std::size_t maxlen = 0;

  while (first != last) {
    ForwardIt change = std::adjacent_find(first, last, signdiff);
    if (change != last) { ++change; }

    std::size_t len = std::distance(first, change);
    if (len > maxlen) { maxlen = len; }

    first = change;
  }

  return maxlen;
}
binary_search metodu
Metodun içi şuna benzer.
vector<int> text{ 10,9,8,7,6,5,4,3,2,1 };
int sought = 3;
// text must be sorted
// beg and end will denote the range we're searching
auto beg = text.begin(), end = text.end();
auto mid = text.begin() + (end - beg) / 2; // original midpoint
// while there are still elements to look at and we haven't yet found sought
while (mid != end && *mid != sought) {
  if (sought < *mid) // is the element we want in the first half?
    end = mid; // if so, adjust the range to ignore the second half
  else // the element we want is in the second half
    beg = mid + 1; // start looking with the element just after mid
  mid = beg + (end - beg) / 2;// new midpoint
}

find metodu
İmzası şöyle
template< class InputIt, class T >
InputIt find( InputIt first, InputIt last, const T& value );
Bu çağrının maliyeti O(N). find işlemi için == operatörü tanımlı olmalı. find algoritmasının sırayla her bir nesneyi karşılaştırırken "loop unwinding" yani "döngü açma" yöntemi kullanır.
Bazı veri yapıları lineer arama yapmak için uygun değildir. Bunlar map, set, unordered_map,unordered_set gibi binary tree veya hash kullanan veri yapılarıdır. Dolayısıyla bu tür veri yapıları kendi find metodlarını sunarlar.

Örnek
Elimizde bir vector olsun. Şöyle yaparız.
std::vector<Foo> v;

std::find(v.begin(), v.end(), foo);
Foo sınıfının operator== metodu olmalıdır. Şöyle yaparız.
struct Foo
{
  bool operator==(const RenderJob& rhs) const { ... }};

find_end metodu
Örnek ver

find_first_of metodu
Örnek ver

find_if metodu
İmzası şöyle.
template< class InputIt, class UnaryPredicate >
InputIt find_if( InputIt first, InputIt last,
             UnaryPredicate p );
Şöyle yaparız.
string str = "This is me";
auto itr = std::find_if(str.begin(), str.end(), std::is_space);
search metodu
İmzası şöyle.
template<class ForwardIterator1, class ForwardIterator2,
         class BinaryPredicate>
ForwardIterator1
search(ForwardIterator1 first1, ForwardIterator1 last1,
       ForwardIterator2 first2, ForwardIterator2 last2,
       BinaryPredicate pred);

search_n metodu
Örnek ver


Hiç yorum yok:

Yorum Gönder