Раздел «Алгоритмы».AlgorithmSTLSamples:

Примеры кода на STL

В данном документе будем считать, что в начале программ написаны следующие строки

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <iterator>
using namespace std;

Увеличить все элементы массива на 5 (for_each, transform, copy)

#define vi  vector<int>
#define vi_iter vector<int>::iterator
#define all(v) v.begin(),v.end()

template <typename T>
void printx(T &x) { cout << x << " "; }

template <typename T, T n>
T addn(T &x) { return x + n; }

template <typename T, T n>
void addn2(T &x) { x += n; }

template <typename T>
T add5(T &x) { return x + 5; }

int main()
{
   const int N = 8 ;
   vi v(N);

   // сгенерируем случайный массив
   generate(all(v), rand);        

   // увеличим каждый его элемента на 5
   transform(all(v), v.begin(), add5<int>); 

    // выведем
   for_each(all(v), printx<int>); 
   cout << "\n";
   
   // снова увеличим каждый его элемента на 5
   transform(all(v), v.begin(), addn<int,5>); 
   
   // снова выведем, но другим способом
   copy(all(v), ostream_iterator<int>(cout, " "));

    // еще один способ увеличить
   for_each(all(v), addn2<int,5>);

   cout << "\n";

   // снова выведем
   copy(all(v), ostream_iterator<int>(cout, " "));
   cout << "\n";

   return 0;
}

Скопировать один массив в конец другого (copy)

Здесь массивом мы будем называть шаблон vector

#include <stdlib.h>
int main()
{
   const int N = 8 ;
   vi v1(N), v2(N);

   // сгенерируем случайные массивы
   generate(all(v1), rand);
   generate(all(v2), rand);

    // выведем первый
   copy(all(v1), ostream_iterator<int>(cout, " "));
   cout << endl;

    // выведем второй
   copy(all(v2), ostream_iterator<int>(cout, " "));
   cout << endl;

   size_t s2 = v2.size();
   v2.resize(v2.size() + v1.size());

   // скопировать в конец
   copy(all(v1), v2.begin() + s2);

    // выведем второй
   copy(all(v2), ostream_iterator<int>(cout, " "));
   cout << endl;

   return 0;
}

Посчитать число элементов больше 10 (count_if, generate, functors, bind2nd)

struct rand_generator_double {
   double from, to;
   rand_generator_double(double from, double to) {
      this->from = from;
      this->to   = to;
   }
   double operator()() {
      return from + (to-from)*((double)rand())/RAND_MAX;
   }
};

int main()
{
   const int N = 100;
   vector<double> v(N);

   // сгенерируем случайные массивы
   generate(all(v), rand_generator_double(0., 20.) );

   cout << "Number of element greater than 10.0 is " << 
      count_if(all(v), bind2nd(greater<double>(), 10.0));

    return 0;
}

Пересечение двух множеств (set_intersection, sort)

Пример ввода/вывода:

$ ./set_intersection 
15 4 3 3 17 2 3 -1
3 17 1 15 1 14 22 -1
3 15 17

#include <vector>
#include <iostream>
#include <algorithm>
#include <iterator>
#define all(v) (v).begin(), (v).end()
#define vi vector<int>

using namespace std;

void read(vi& v)
{
    while (1)
    {
        int i;
        cin >> i;
        if (i == -1) break;
        v.push_back(i);
    }
}

int main() {
    vi s1, s2, s3;

    read(s1);
    read(s2);
    sort(all(s1));
    sort(all(s2));
    s3.resize(s1.size());
    copy(s3.begin(), 
        set_intersection(all(s1), all(s2), s3.begin()), 
        ostream_iterator<int>(cout, " "));
    return 0;
}

Пояснения

Функция set_intersection получает 5 параметров — итераторы начал и концов задающие множества, которые необходимо пересечь, и итератор, указывающий на на место контейнера, начиная с которого требуется записать результат. Возвращяемым значением этой функции является итератор, указывающий на следующий элемент после последнего, полученного в результате пересечения множеств. Алгоритм set_intersection работает за линейное время и требует, чтобы интервалы были предворительно отсортированны.

ostream_iterator(cout, " ") создаёт итератор, для вывода переменных типа int в поток cout, разделителем в данном случае определён пробел.

Для вывода результата мы используем алгоритм copy, который копирует содержимое между двумя итераторами начиная с третьего итератора, в данном случае, данное копирование приводит к выводу содержимого в поток cout.

AlgorithmClasifyForm
Type: Код, Задача
Scope: STL
Strategy:  
Language: C++
Complexity: Medium