Объектноориентированное программирование
 Скачать 1.73 Mb.
|
|
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 { 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.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 // 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 { 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 { vector { 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 // Или вот такая техника в случае наследования: 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 Пример использования функции transform : // transform algorithm example #include #include #include { vector // 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 } Интерфейсы функций обмена: // 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 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 // 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 } void printMan (string man) { cout << man << endl; } |