2vcTnguyvU
.pdfrandom_shuffle( b ,e, rand) |
перемешивает элементы с помощью |
|
указанного генератора случайных чисел |
|
rand |
Численные алгоритмы
Численные алгоритмы включают суммирование, скалярное произведение и смежную разность. В следующей программе численная функция accumulate() выполняет суммирование вектора, а inner_product () подссчитывает скалярное произведение.
#include <cstdlib> #include <iostream> #include <vector>
# include <numeric> using namespace std;
int main(int argc, char *argv[]) { double d1[3]={ 1.2, 4.7, 5.7}; double d2[3]={ 1.7, -2.5, 3.6};
double sum, inner_p; vector<double> v1(d1, d1+3);
vector<double> v2(d2, d2+3); sum=accumulate(v1.begin(), v1.end(),0.0); inner_p=inner_product(v1.begin(), v1.end(), v2.begin(), 0.0); cout<<"Summa = "<<sum<<" Scalar muiti = " <<inner_p<<endl; system("PAUSE"); return EXIT_SUCCESS; }
Вот библиотечные прототипы для двух накапливающих алгоритмов: template<class InputIter, class T>
T accumulate (InputIter b, InputIter e, T t); Это стандартный алгоритм накопления, причем за начальное значение суммы принимается значение суммы t. К этой сумме последовательно добавляются элементы из диапазона от b до e.
template<class InputIter, class T> T accumulate (InputIter b, InputIter e, T t, BinOP bop);
Этот алгоритм накопления, причем начальное значение равно t. К этому значению последовательно “прибавляются“ элементы из диапазона от b до e, но вместо сложения применяется заданная бинарная операция bop.
Функции
При использовании STL полезны объекты-функции. Функциональные объекты - это объекты, для которых определён operator(). Например, многие из рассмотренных ранее алгоритмов имеют форму, в которой в качестве аргумента может передаваться заданный пользователем бинарный оператор. Ряд объектов-функций находятся в библиотеке function, но их можно создать и самостоятельно. Объекты-функции - это классы, в которых определен
110
operator( ). Эти операторы проектируются встроенными, чтобы получить более эффективный код. В следующей программе выполнено накопление с помощью “целого минуса” в качестве бинарной операции над массивом v1[ ]. Поэтому значения с двойной точностью обрезаются и результат будет -10.
#include <cstdlib> #include <iostream> #include <vector>
# include <numeric> using namespace std;
int main(int argc, char *argv[])
{ double d1[3]={ 1.2, 4.7, 5.7}; double sum; vector<double> v1(d1, d1+3); sum=accumulate(v1.begin(), v1.end(),0.0, minus<int>());
cout<<"Summa = |
"<<sum<< endl; |
system("PAUSE"); |
return EXIT_SUCCESS; } |
Существует три вида объектов-функций:
•арифметические объекты;
•сравнивающие объекты;
•логические объекты.
Чтобы позволить адаптерам и другим компонентам манипулировать функциональными объектами, которые используют один или два параметра, требуется, чтобы они соответственно обеспечили определение типов (typedefs) argument_type и result_type для функциональных объектов, которые используют один параметр, и first_argument_type, second_argument_type и result_type для функциональных объектов, которые используют два параметра. Чтобы упростить определение типов (typedefs) параметров и результата, используют следующие базовые классы (Base):
template <class Arg, class Result> struct unary_function {
typedef Arg argument_type; typedef Result result_type; }:
template <class Arg1, class Arg2, class Result>
111
struct binary_function {
typedef Arg1 first_argument_type; typedef Arg2 second_argument_type; typedef Result result_type; };
Арифметические операции (Arithmetic operations)
Библиотека обеспечивает базовые классы функциональных объектов для всех арифметических операторов языка.
template <class T>
struct plus : binary_function<T, T, T> {
Т operator()(const T& x, const T& y) const { return x + y; } }; template <class T>
struct minus : binary_function<T, T, T> {
Т operator()(const T& x, const T& y) const { return x - y; } }; template <class T>
struct times : binary_function<T, T, T> {
Тoperator()(const T& x, const T& y) const ( return x * y; } }; template <class T>
struct divides : binary_function<T, T, T> {
Тoperator()(const T& x, const T& y) const { return x / y; } }; template <class T>
struct modulus : binary_function<T, T, T> {
Тoperator()(const T& x, const T& y) const { return x % y; } }; template <class T>
struct negate : unary_function<T, T> {
Тoperator()(const T& x) const { return -x; } };
Сравнения (Comparisons)
Библиотека обеспечивает базовые классы функциональных объектов для всех операторов сравнения языка
template <class T>
struct equal_to : binary_function<T, T, bool> {
bool operator()(const T& x, const T& y) const { return x == y; } }; template <class T>
struct not_equal_to : binary_function<T, T, bool> {
bool operator()(const T& x, const T& y) const { return x != y; } }; template <class T>
struct greater : binary_function<T, T, bool> {
bool operator()(const T& x, const T& y) const { return x > y; } }; template <class T>
112
struct less : binary_function<T, T, bool> {
bool operator()(const T& x, const T& y) const { return x < y; } }; template <class T>
struct greater_equal : binary_function<T, T, bool> {
bool operator()(const T& x, const T& y) const { return x >= y; } }; template <class T>
struct less_equal : binary_function<T, T, bool> {
bool operator()(const T& x, const T& y) const { return x <= y; } };
Логические операции (Logical operations) template <class T>
struct logical_and : binary_function<T, T, bool> {
bool operator()(const T& x, const T& y) const { return x && y; } }; template <class T>
struct logical_or : binary_function<T, T, bool> {
bool operator()(const T& x, const T& y) const { return x || y; } }; template <class T>
struct logical_not : unary_function<T, bool> { bool operator()(const T& x) const { return !x; } };
Адаптеры функций (Function adaptors)
Адаптеры функций делают возможным создание объектов-функций с помощью адаптирования. Можно выделить следующие группы адаптеров функций:
•отрицающий адаптер - для отрицания предикатных объектов;
•связывающий адаптер - для связывания аргументов функции;
•адаптеры для указателя на функцию.
•
Отрицатели (Negators)
Отрицатели not1 и not2 берут унарный и бинарный предикаты соответственно и возвращают их дополнения.
template <class Predicate>
class unary_negate : public unary_function<Predicate::argument_type, bool> { protected:
Predicate pred; public:
unary_negate(const Predicate& x) : pred(x) {}
bool operator()(const argument_type& x) const { return !pred(x); } }; template <class Predicate>
unary_negate<Predicate> not1(const Predicate& pred) {
113
return unary_negate<Predicate>(pred); } template <class Predicate>
class binary_negate : public binary_function<Predicate::first_argument_type, Predicate::second_argument_type, bool> {
protected: Predicate pred; public:
binary_negate(const Predicate& x) : pred(x) {} bool operator()(const first_argument_type& x, const second_argument_type& y) const {
return !pred(x, y); } }; template <class Predicate>
binary_negate<Predicate> not2(const Predicate& pred) { return binary_negate<Predicate>(pred); }
Пример.
#include <iostream> #include <algorithm> using namespace std;
int array [4] = { 4, 9, 7, 1 }; int main ( ) {
sort (array, array + 4, not2 (greater<int> ())); for (int i = 0; i < 4; i++)
cout << array[i] << endl; return 0; }
Привязки (Binders)
Привязки bind1st и bind2nd берут функциональный объект f двух параметров и значение x и возвращают функциональный объект одного параметра, созданный из f с первым или вторым параметром соответственно, связанным с х.
template <class Predicate>
class binder1st : public unary_function { protected:
Operation op; Operation::first_argument_type value; public:
binder1st(const Operation& x, const Operation::first_argument_type& y) : op(x), value(y) {}
result_type operator()(const argument_type& x) const {
return op(value, x); |
} }; |
|
114 |
template <class Operation, class T>
binder1st<0peration> bind1st(const Operation& op, const T& x) { return binder1st<0peration>(op, Operation::first_argument_type(x)); } template <class Operation>
class binder2nd : public unary_function<0peration::first_argument_type, Operation::result_type> {
protected: Operation op;
Operation::second_argument_type value; public:
binder2nd(const Operation& x, const Operation::second_argument_type& y) : op(x), value(y) {}
result_type operator()(const argument_type& x) const { return op(x, value); } };
template <class Operation, class T>
binder2nd<Operation> bind2nd(const Operation& op, const T& x) { return binder2nd<0peration>(op, Operation::second_argument_type(x)); }
Например, find_if(v.begin(), v.end(), bind2nd(greater<int>(), 5)) находит первое целое число в векторе v большее, чем 5; find_if(v.begin(), v.end(), bind1st(greater<int>(), 5)) находит первое целое число в v меньшее, чем 5.
#include <iostream.h> #include <stl.h>
int array [3] = { 1, 2, 3 }; int main ( ) {
int* p = remove_if (array, array + 3, binder1st<less<int> > (less<int> (), 2)); for (int* i = array; i != p; i++)
cout << *i << endl; return 0; } #include <iostream.h>
#include <stl.h>
int array [3] = { 1, 2, 3 }; int main ( ) {
int* p = remove_if (array, array + 3, bind1st(less<int> (), 2)); for (int* i = array; i != p; i++)
cout << *i << endl; return 0; }
Адаптеры указателей на функции
Чтобы позволить указателям на (унарные и бинарные) функции работать с функциональными адаптерами, библиотека обеспечивает следующее:
template <class Arg, class Result>
115
class pointer_to_unary_function : public unary_function<Arg, Result> { protected:
Result (*ptr)(Arg); public:
pointer_to_unary_function() {} pointer_to_unary_function(Result (*x)(Arg)) : ptr(x) {} Result operator()(Arg x) const { return ptr(x); } }; template <class Arg, class Result>
pointer_to_unary_function<Arg, Result> ptr_fun(Result (*x)(Arg)) { return pointer_to_unary_function<Arg, Result>(x); }
template
class pointer_to_binary_function : public binary_function { protected:
Result (*ptr)(Arg1, Arg2); public: pointer_to_binary_function() {}
pointer_to_binary_function(Result (*x)(Arg1, Arg2)) : ptr(х) {} Result operator()(Arg1 x, Arg2 y) const { return ptr(x, y); } }; template <class Arg1, class Arg2, class Result> pointer_to_binary_function<Arg1, Arg2, Result> ptr_fun(Result (*x)(Arg1, Arg2)) {
return pointer_to_binary_function<Argl, Arg2, Result>(x); }
Например, replace_if(v.begin(), v.end(), not1(bind2nd(ptr_fun(strcmp), "C")), "C++") заменяет все "С" на "C++" в последовательности v.
Лабораторная работа № 11
Тема: Стандартная библиотека шаблонов -STL
Цель: Изучить использование STL Задание № 1
Краткие теоретические сведения
Для того чтобы определить объект контейнерного типа необходимо сначала включить соотвествующий заголовочный файл:
#include <vector> using namespace std;
ostream& operator<< (ostream& out, const vector<int>& v)
{
copy(v.begin(), v.end(), ostream_iterator<int>(out," "));
return out; |
} |
int main () |
{ |
|
116 |
vector<int> vi; int i; for (i = 0; i < 10; ++i) vi.insert(vi.begin(), i); cout << vi << endl;
int half = vi.size() / 2; for (i = 0; i < half; ++i)
vi.erase(vi.begin()); cout << vi << endl; return 0; }
Пример использования итераторов #include <vector>
#include <algorithm> using namespace std; int main ()
{
typedef vector<int>::iterator iterator; int d1[10] = {0,1,2,2,3,4,2,2,6,7};
//Set up a vector. vector<int> v1(d1+0, d1+10);
//Try find.
iterator it1 = find(v1.begin(), v1.end(), 3); // Try find_if.
iterator it2 = find_if(v1.begin(), v1.end(), bind1st(equal_to<int>(), 3)); // Try both adjacent_find variants.
iterator it3 = adjacent_find(v1.begin(), v1.end());
iterator it4 = adjacent_find(v1.begin(), v1.end(), equal_to<int>()); // Output results.
cout << *it1 << " " << *it2 << " " << *it3 << " " << *it4 << endl; return 0; }
1.Используя STL создать вектор, список, двустороннею очередь для хранения дат. Реализовать для всех контейнеров операции push_back, pop_back, push_front, pop_front, insert, erase, sort (объяснить какие операции не подходят для какого типа контейнера и почему). Результаты вывести на экран.
2.Напишите программу, которая читает последовательность целых чисел из стандартного ввода с помощью потокового итератора чтения ostream_iterator. Нечетные числа поместите в один файл посредством ostream_iterator, разделяя значения пробелом. Четные числа таким же образом запишите в другой файл, при этом каждое значение должно размещаться в отдельной строке.
117
3. Используя стандартную библиотеку, разработайте текстовую поисковую систему, позволяющую прочитать текстовый файл и сохранить следующую информацию: само слово, номер строки и позицию в строке; слова привести к стандартной форме; знаки препинания убрать. Выделите следующие этапы:
•чтение текстового файла, каждую строку поместите в вектор, используя функцию istream& getline (istream &is, string str, char delimiter);
•для чтения данных из файла разработайте функцию, которая имеет возврашаемое значение указатель на строковый вектор:
vector<string> * retrive_text() { string file_name;
cin>>file_name;
// обработка ошибки открытия файла ifsream infile(file_name.c_str(), ios::in); if(!infile)
cerr<<” text”; exit(-1); } else cout<<’\n’;
vector<string> *имя=new....; string textline;
typedef pair<string::size_type, int> stats; stats maxline;
int linenum=0;
while(getline(infile, textline, ‘\n’)) { cout<<”считана строка: “<<textline<<’\n’; if (maxline.first<textline.size() ){
maxline.first=textline.size();
maxline.second=linenum;
}
имя->push_back(textline); linenum++;
}
return имя;
}
• теперь нужно разбить строки на слова, находя пробелы. Требуемая функциональность обеспечивается функцией find_first_of() , которая возврашает позицию первого символа, соотвествующего одному из заданных в строке-параметре. Чтобы узнать длину слова, введите переменные
//pos –позиция на 1 больше конца слова
//prev_posпозиция начала слова
хотя позиция подстроки имеет тип int, более правильное и переносимое
118
объявление результата возврашаемого функцией find() string::size_type
например: string::size_type pos=0;
После того как выделили слово , необходимо поместить его в строковый вектор: vector<string> words;
while((pos=textline.find_first_of(‘ ‘, pos))!=string::npos)
{ words.push_back(textline.substr(prev_pos, pos-prev_pos)); prev_pos=++pos;}
//нужно еще обработать последнее слово
•затем нужно убрать знаки препинания и другие нежелательные элементы, найденный элемент удалить с помощью функции erase();
кроме сохранения слов в векторе, сохраняется также позиция слова в строке и номер строки.
•теперь постройте отображение позиций слов. Ключом будет уникальная строка, а значением будет позиция : номер строки, номер колонки.
•распечайте результат.
4.Напишите программу, включающую следующие этапы:
•создание трех векторов слов, прочитать из файлов
•распечатка векторов на экране;
•слияние всех векторов в один;
•отсортировать его в алфавитном порядке;
•удалить все дубликаты;
•снова отсортировать по длине слова (величину длины слова ввести с клавиатуры);
•подсчитать число слов;
•напечатать получившийся вектор..
5.Используя предоопределенные объекты-функции и адаптеры, создайте объекты-функции для решения следующих задач:
•найти все значения, болшие или равные 512;
•найти все строки, не равные “seven days”.
№ 2 Краткие теоретические сведения
В map хранятся пары ключ/значение. Ключ играет роль индекса для доступа к ассоциированному с ним значению. Чтобы определить объект класса MAP, нужно указать, как минимум, типы ключа и значения. Например:
map<string,int> mymap;
119