Главная страница
Навигация по странице:

  • 13.2.1

  • Объектноориентированное программирование


    Скачать 1.73 Mb.
    НазваниеОбъектноориентированное программирование
    Дата21.11.2018
    Размер1.73 Mb.
    Формат файлаpdf
    Имя файлаOOP-PrePrint.pdf
    ТипКонспект
    #57177
    страница14 из 15
    1   ...   7   8   9   10   11   12   13   14   15
    13.2
    STL-строки
    Не существует серьезной библиотеки, которая бы не включала в себя свой класс для представления строк или даже несколько подобных классов.
    STL – строки поддерживают как формат ASCII, так и формат Unicode.

    152 string
    – представляет из себя коллекцию, хранящую символы char в формате ASCII. Для того, чтобы использовать данную коллекцию, вам необ- ходимо включить
    #include
    wstring
    – это коллекция для хранения двухбайтных символов wchar_t
    , которые используются для представления всего набора символов в формате
    Unicode. Для того, чтобы использовать данную коллекцию, вам необходимо включить
    #include
    13.2.1
    Строковые потоки
    Используются для организации сохранения простых типов данных в STL строки в стиле C++. Ниже приведена простая программа, демонстрирующая возможности использования строковых потоков:
    //stl.cpp: Defines the entry point for the console application
    #include "stdafx.h"
    #include
    #include
    #include using namespace std; int _tmain (int argc, _TCHAR* argv [])
    { strstream xstr; for (int i = 0; i < 10; i++)
    { xstr << "Demo " << i << endl;
    } cout << xstr.str (); string str; str.assign (xstr.str (), xstr.pcount ()); cout << str.c_str (); return 0;
    }
    Строковый поток – это просто буфер, в конце которого установлен нуль терминатор, поэтому мы наблюдаем в конце строки мусор при первой рас- печатке, то есть реальный конец строки определен не посредством нуль тер- минатора, а с помощью счетчика, и его размер можно получить с помощью метода pcount()
    Далее мы производим копирование содержимого буфера в строку и пе- чатаем строку второй раз. На этот раз она печатается без мусора.
    Основные методы, которые присутствуют почти во всех STL коллек- циях, приведены ниже.

    empty
    – определяет, является ли коллекция пустой.

    size
    – определяет размер коллекции.

    153

    begin
    – возвращает прямой итератор, указывающий на начало коллек- ции.

    end
    – возвращает прямой итератор, указывающий на конец коллек- ции. При этом надо учесть, что реально он не указывает на ее последний элемент, а указывает на воображаемый несуществующий элемент, следую- щий за последним.

    rbegin
    – возвращает обратный итератор, указывающий на начало коллекции.

    rend
    – возвращает обратный итератор, указывающий на конец кол- лекции. При этом надо учесть, что реально он не указывает на ее последний элемент, а указывает на воображаемый несуществующий элемент, следую- щий за последним.

    clear
    – удаляет все элементы коллекции, при этом, если в вашей кол- лекции сохранены указатели, то вы должны не забыть удалить все элементы вручную посредством вызова delete для каждого указателя.

    erase
    – удаляет элемент или несколько элементов из коллекции.

    capacity
    – вместимость коллекции определяет реальный размер – то есть размер буфера коллекции, а не то, сколько в нем хранится элементов.
    Когда вы создаете коллекцию, то выделяется некоторое количество памяти.
    Как только размер буфера оказывается меньшим, чем размер, необходимый для хранения всех элементов коллекции, происходит выделение памяти для нового буфера, а все элементы старого копируются в новый буфер. При этом размер нового буфера будет в два раза большим, чем размер буфера, выде- ленного перед этим – такая стратегия позволяет уменьшить количество опе- раций перераспределения памяти, но при этом очень расточительно расхо- дуется память. Причем в некоторых реализациях STL первое выделение па- мяти происходит не в конструкторе, а как ни странно, при добавлении пер- вого элемента коллекции. Фрагмент программы ниже демонстрирует, что размер и вместимость коллекции – две разные сущности: vector vec; cout << "Real size of array in vector: " << vec.capacity () << endl; for (int j = 0; j < 10; j++)
    { vec.push_back (10);
    } cout << "Real size of array in vector: " << vec.capacity () << endl; return 0;

    154
    13.3
    Векторы
    Наиболее часто используемая коллекция – это вектор. Как уже было от- мечено выше, внутренняя реализация этой коллекции представляет из себя массив и счетчик элементов, сохраненных в нем.
    Предположим, нам необходимо написать логику клиент – серверного приложения. Администратор сети посылает сообщения на сервер с опреде- ленным интервалом, где они сохраняются в одном общем массиве common, при этом каждое сообщение имеет поле
    To
    , однозначно идентифицирующее каждого клиента.
    Каждый клиент также подключается к серверу, но с гораздо большим интервалом, чем приход сообщений от администратора, чтобы просмотреть сообщения, адресованные ему. При этом нам также необходимо знать хро- нологию прихода сообщений, адресованных разным пользователям (какое сообщение пришло раньше, а какое позже в любой момент времени). Для того, чтобы получить сообщения, клиент должен подключиться к серверу, просмотреть массив common для того, чтобы выбрать сообщения, адресо- ванные ему, и после отключиться.
    В нашем случае, три клиента подключаются к серверу и каждый про- сматривает общий массив сообщений, при этом мы должны сделать наше приложение поточно – безопасным, поэтому должны использовать код внутри критической секции. Все это рано или поздно приведет к тому, что с увеличением числа клиентов приложение станет очень медленным.
    Для того, чтобы избежать этой ситуации, мы заведем массив сообщений для каждого клиента и вместо того, чтобы просматривать общий массив со- общений три раза, мы будем просматривать его всего лишь один раз с ин- тервалом времени, адекватным периоду подключения одного клиента. При этом скопируем все сообщения в соответствующие массивы. Клиенты же будут просто забирать данные из своих массивов при подключении.
    На самом деле это немного неправильный подход для решения этой за- дачи. Скорее всего, нам надо было бы сохранять сообщения в момент их прихода в оба массива, но наша цель – посмотреть возможности использо- вания коллекции vector
    , поэтому воспользуемся этим подходом и предста- вим упрощенную логику такого приложения:
    #include "stdafx.h"
    #include
    #include
    #include
    #include
    #include

    155 using namespace std; class MyMessage
    { private: string from; string to; string message; int id; public:
    MyMessage(string from, string to, string message)
    { this->from = from; this->to = to; this->message = message;
    } int GetId()
    { return this->id;
    } void SetId(int id)
    { this->id = id;
    } string GetMessage()
    { return this->message;
    } string GetFrom()
    { return this->from;
    } string GetTo()
    { return this->to;
    }
    }; int _tmain (int argc, _TCHAR* argv [])
    { vector common;
    // create pool of messages for 3 users: for (int user = 0; user < 3; user++)
    { for (int i = 0; i < 10; i++)
    { strstream messagex; messagex << "Message " << i; string smessage; smessage.assign(messagex.str(), messagex.pcount()); strstream userx; userx << "User " << user; string suser; suser.assign (userx.str (), userx.pcount ());
    MyMessage message ("Administrator", suser, smessage); message.SetId (user*10 + i); common.push_back (message);
    }
    }
    // create vector for each user:

    156 vector user0; vector user1; vector user2; for (int x = 0; x < (int) common.size (); x++)
    {
    MyMessage message = common [x]; if (message.GetTo () == "User 0")
    { user0.push_back (message);
    } else if (message.GetTo () == "User 1")
    { user1.push_back (message);
    } else if (message.GetTo () == "User 2")
    { user2.push_back (message);
    }
    } cout << "Messages for user 2: " << endl; for (int i = 0; i < (int) user2.size (); i++)
    {
    MyMessage message = user2[i]; cout << message.GetTo () << endl;
    } cout << "Messages for user 1: " << endl; for (int i = 0; i < (int) user1.size (); i++)
    {
    MyMessage message = user1[i]; cout << message.GetTo () << endl;
    } cout << "Messages for user 0: " << endl; for (int i = 0; i < (int) user0.size (); i++)
    {
    MyMessage message = user0[i]; cout << message.GetTo () << endl;
    } cout << "Size of common vector: " << (int) common.size () << endl; return 0;
    }
    13.4
    Итераторы
    При перечислении основных методов коллекций упоминались итера- торы, при этом не было дано определение этой сущности. Итератор – это абстракция, которая ведет себя, как указатель с некоторыми ограничениями или без них, то есть, сохраняет все свойства своего прародителя. Указатель
    – это тоже итератор. В действительности, итераторы, в большинстве слу- чаев, это объектные обертки указателей. Вот как примерно может выглядеть внутреннее устройство итератора: class Iterator
    {
    T* pointer;

    157 public:
    T* GetPointer ()
    { return this->pointer;
    } void SetPointer (T* pointer)
    { this->pointer = pointer;
    }
    };
    Но итератор представляет собой более высокий уровень абстракции, чем указатель, поэтому утверждение, что итератор – это указатель в некоторых случаях может быть неверно. А вот обратное будет верно всегда.
    Итераторы обеспечивают доступ к элементам в коллекции.
    Итераторы для конкретного класса коллекции определяются внутри класса этой коллекции. В STL существует три типа итераторов: iterator, re- verse_iterator, и random access iterator. Для обхода коллекции от меньшего индекса к большему, используются обычные или forward итераторы. Для обхода коллекции в обратном направлении используются reverse итераторы.
    Random access iterator являются итераторами, которые могут обходить кол- лекцию как вперед, так и назад. Ниже приведен пример использования ите- раторов для удаления половины элементов вектора:
    #include "stdafx.h"
    #include
    #include
    #include using namespace std; void printInt (int number); int _tmain (int argc, _TCHAR* argv [])
    { vector myVec; vector::iterator first, last; for (long i=0; i<10; i++)
    { myVec.push_back (i);
    } first = myVec.begin (); last = myVec.begin () + 5; if (last >= myVec.end ())
    { return -1;
    } myVec.erase (first, last); for_each (myVec.begin (), myVec.end (), printInt); return 0;
    } void printInt (int number)
    { cout << number << endl;
    }

    158
    Важно помнить, что когда вы получаете итератор к коллекции, а после этого модифицируете коллекцию, то этот итератор становится уже непри- годным к использованию. Естественно, не все изменения приводят к непри- годности итератора для дальнейшего использования, а только изменения структуры коллекции. В случае же, если вы просто измените значения, со- храненные в коллекции, то ничего страшного не произойдет и итератор не испортится.
    Итерация по коллекции вперед происходит так: for (iterator element = begin (); element < end (); element++)
    { t = (*element);
    }
    // Итерация по коллекции назад происходит так: for (reverse_iterator element = rbegin(); element < rend(); element++)
    { t = (*element);
    }
    При работе и с random access iterator итератором синтаксис конструкции может быть, например, таким: for (iterator element = begin(); element < end(); element += 2)
    { t = (*element);
    }
    Для более эффективного использования контейнеров используйте typedef или наследуйте свой класс от класса коллекции.
    Сделать это можно так: typedef vector myVector typedef map myMap typedef deque myQue
    // Или вот такая техника в случае наследования: class myVector: public vector {};
    // В случае с итератором применима предыдущая техника: typedef myVector::iterator vectorIterator typedef myVector::reverse_iterator revVectorIterator
    13.5
    Алгоритмы
    До этого мы посмотрели основные приемы использования STL коллек- ций на примере использования вектора. Это основа STL, но для того, чтобы по-настоящему использовать всю мощь этой библиотеки, придется расши- рить наши знания. С использованием алгоритмов возможно создание очень мощных и эффективных программ. По компактности такой код превосходит

    159 код, написанный на таких современных языках, как Java и С#, и в значитель- ной степени эффективнее последнего.
    STL-алгоритмы представляют набор готовых функций, которые могут быть применены к STL коллекциям и могут быть подразделены на три ос- новных группы:

    функции для перебора всех членов коллекции и выполнения опреде- ленных действий над каждым из них;

    функции для сортировки членов коллекции;

    функции для выполнения определенных арифметических действий над членами коллекции.
    К первой группе функций относятся: count
    ,
    find
    ,
    for_each
    ,
    search
    ,
    copy
    ,
    swap
    ,
    replace
    ,
    transform
    ,
    remove
    ,
    unique
    ,
    reverse
    ,
    random_shuffle
    ,
    partition и др.
    Интерфейсы функций for_each и accumulate
    : for_each (iterator1, iterator2, function); list L(...) int sum = accumulate (L.begin(), L.end(), 0, [plus()]);
    Пример использования функции transform
    :
    // transform algorithm example
    #include
    #include
    #include using namespace std; int op_increase(int i) { return ++i; } int op_sum(int i, int j) { return i + j; } int main()
    { vector first; vector second; vector::iterator it;
    // set some values: for (int i = 1; i < 6; i++) first.push_back(i*10);
    // first: 10 20 30 40 50
    // allocate space second.resize(first.size()); transform(first.begin(), first.end(), second.begin(), op_increase);
    // second: 11 21 31 41 51 transform(first.begin(), first.end(), second.begin(), first.begin(), op_sum);
    // first: 21 41 61 81 101 return 0;
    }

    160
    Интерфейсы функций заполнения коллекций:
    // fill заполняет последовательность элементов от iterator1 до iterator2 fill (iterator1, iterator2, value); // значением value
    // fill_n заполняет n элементов последовательности, начиная с указанного fill_n (iterator1, N, value);
    // generate работает, как fill, но для генерации используется функция, generate (iterator1, iterator2, func); // которая не принимает аргументов generate_n (iterator1, N, function);
    Пример использования функции generate
    :
    // function generator: int RandomNumber () { return (std::rand()%100); }
    // class generator: struct c_unique { int current; c_unique() {current=0;} int operator()() {return ++current;}
    } UniqueNumber; int main ()
    { std::srand ( unsigned ( std::time(0) ) ); std::vector myvector (8); generate (myvector.begin(), myvector.end(), RandomNumber); std::cout << "myvector contains:"; for (std::vector::iterator it = myvector.begin(); it != myvector.end(); ++it) std::cout << ' ' << *it; std::cout << '\n'; std::generate (myvector.begin(), myvector.end(), UniqueNumber); std::cout << "myvector contains:"; for (std::vector::iterator it = myvector.begin(); it != myvector.end(); ++it) std::cout << ' ' << *it; std::cout << '\n'; return 0;
    }
    Интерфейсы функций обмена:
    // swap осуществляет обмен двух элементов swap (element1, element2);
    // iter_swap осуществляет обмен элементов, на которые указывают итераторы iter_swap (iterator1, iterator2);

    161
    // swap_ranges – обмен элементами от iter1 до iter2 с элементами, swap_ranges (iter1, iter2, iter3); // начинающимися с iter3
    Вторая группа функций включает: sort
    ,
    stable_sort
    ,
    nth_element
    ,
    binary_search
    ,
    lower_bound
    ,
    up- per_bound
    ,
    equal_range
    ,
    merge
    ,
    includes
    ,
    min
    ,
    max
    ,
    min_element, max_element
    ,
    lexographical_compare и др.
    Интерфейсы алгоритмов сортировки коллекций: sort (begin, end);
    // partial_sort выдает первые N элементов в отсортированном порядке, а partial_sort (begin, begin + N, end) // остальные – как попало.
    // nth_element выдает элемент на корректной N-й позиции, в случае, если бы nth_element (begin, begin + N, end) // коллекция была отсортирована
    // partition разделяет коллекцию на 2 части, согласно function partition (begin, end, function)
    Интерфейсы функций сравнения коллекций:
    // equal возвращает true, если последовательности равны (==) equal(first1, last1, first2);
    // mismatch возвращает указатель на первый элемент, который не равен mismatch(first1, last1, first2); // соответствующему в последовательности
    // lexicographical_compare возвращает true, если первая последовательность lexicographical_compare(first1, last1, first2, last2); // меньше второй
    К третьей группе функций относятся: accumulate
    , inner_product
    , partial_sum
    , adjacent_difference.
    Ранее мы уже использовали один из алгоритмов: for_each()
    для того, чтобы распечатать все значения из вектора. Важно отметить, что, кроме ука- зателя на функцию в этом случае мы могли бы передать функтор – специ- альный класс с перегруженным оператором operator()
    #include "stdafx.h"
    #include
    #include
    #include
    #include
    #include using namespace std; class MyFunctor

    162
    { string comment; public:
    MyFunctor ()
    { comment = "My comment";
    }
    MyFunctor (string comment)
    { this->comment = comment;
    } void operator ()(int test)
    { cout << test << comment << endl;
    }
    }; int _tmain (int argc, _TCHAR* argv [])
    { vector test;
    // fill vector: for (int i = 0; i < 5; i++)
    { test.push_back (i);
    }
    // now use our functor:
    MyFunctor functor ("Test comment"); for_each (test.begin (), test.end (), functor); return 0;
    }
    Преимущество такого подхода заключается в том, что если нам необхо- димо передать какие – либо параметры для того, чтобы произвести обра- ботку каждого члена коллекции, то мы имеем возможность сделать это в конструкторе функтора или определить дополнительные функции в классе
    – функторе. Это позволит нам сократить количество переменных в области видимости функции – обработчика членов коллекции для хранения значе- ний, которые впоследствии будут использованы внутри тела этой функции.
    Если же для работы над членами коллекции нам не нужно передавать пара- метры, то целесообразнее определить просто функцию.
    Еще один небольшой пример использования алгоритмов приведен ниже, мы создаем две коллекции: женскую и мужскую, после чего заполняем каж- дую из них соответствующими именами мужчин и женщин. Если мы захо- тим поменять местонахождение членов обоих коллекций – то есть, женщин поместить в мужскую коллекцию и наоборот, то сделать это с использова- нием алгоритмов очень просто:
    #include "stdafx.h"
    #include
    #include
    #include
    #include
    #include

    163 using namespace std; void printMan (string user); int _tmain (int argc, _TCHAR* argv [])
    { vector maleRoom; vector fimaleRoom; maleRoom.push_back ("Vasya"); maleRoom.push_back ("Petya"); maleRoom.push_back ("Sasha"); fimaleRoom.push_back ("Nastya"); fimaleRoom.push_back ("Alena"); fimaleRoom.push_back ("Sveta"); for_each (maleRoom.begin (), maleRoom.end (), printMan); reverse (maleRoom.begin (), maleRoom.end ()); cout << "Males in reverse order " << endl; for_each (maleRoom.begin (), maleRoom.end (), printMan); maleRoom.swap (fimaleRoom); cout << "Now in male room are fimales: " << endl; for_each (maleRoom.begin (), maleRoom.end (), printMan); return 0;
    } void printMan (string man)
    { cout << man << endl;
    }

    164
    1   ...   7   8   9   10   11   12   13   14   15


    написать администратору сайта