Материалы к лекциям (1119465), страница 2
Текст из файла (страница 2)
Это означает,// что конструктор может вызываться только явно.// (vector<int>v = 10 - ошибка, попытка неявного преобразования 10 в vector<T>)explicit vector (const A& = A ());// требуется явный вызов конструктора: vector<T> x(10);//неявный вызов: vector<T> y = 10 (неправильно);explicit vector (size_type size, const T& value = T (),const A& a = A ()); // заводятся сразу несколько элементов со// значениями, которые даются их конструкторами по умолчанию.// Если второй параметр отсутствует, конструктор умолчания в Т// обязателен.
Есть и другие виды конструкторов.// Имеются также методы, связанные с итераторами:// iterator begin (); const_iterator begin () const;// iteratorend (); const_iteratorend () const;v.capacity()v.size()vector vpast-the-end-elementэлементыдополнительное пространствоv.rend()v.begin()v.rbegin() v.end()iterator insert (iterator i, const T& value) {...}// вставка перед элементомi……valueres (на вставленный элемент)iterator insert (iterator i, size_type number, const T & value){...}// вставка нескольких одинаковых элементов перед элементомiterator erase (iterator i) { ... return (i); }// уничтожение заданного элемента и// выдача итератора элемента, следующего за удалённымi…res…iterator erase (iterator start, iterator finish)// уничтожение диапазона{ ...
return (finish);}//[start,finish) и выдача следующего за последним удалённымstart…finish = res…bool empty() const {...}//истина, если контейнер пустsize_type size() const {...}//выдача текущего размераvoid clear() {erase (begin(), end());}//уничтожение всех элементов, при// этом память не освобождается, так как деструктор самого вектора не вызываетсяvoid push_back (const T&value) {insert(end(),value);} //вставка в конец контейнераvoid pop_back() {erase (end() - 1);}//уничтожение последнего элементаreference operator [](size_type i) { return * (begin () + i); }// reference – аналог & в Си++reference front () { return * begin (); }// содержимое первого элементаreference back () { return *(end () – 1); } // содержимое последнего элементаreference at (size_type i) { ...
}// содержимое элемента с номером iПри работе с функцией at()используется перехватчик исключительной ситуации:try{ ... v.at (i}; ... }catch (out_of_range) {...}Обход вектора прямым и обратным итератором:int main (){ vector<int> v (100, 5); // 100 элементов, инициированных значением 5vector<int>::const_iterator p = v.begin ();vector<int>::const_reverse_iterator q = v.rbegin ();...while (p != v.end ()){ cout << * p << ‘ ’; ++ p; } ...while (q != v.rend ()){ cout << * q << ‘ ’; ++ q; } ...return 0;}Учебная программа, иллюстрирующая особенности работы с векторами#include <vector>using namespace std;typedef vector<int> Container;typedef Container::size_type Cst;void f (Container& v, int i1, int i2) {try { for (Cst i = 0; i < 10; i++){ // здесь значение индекса i проверять не надо: вектор создаётся зановоv.push_back (i);// Элементы: 0, 1, 2, ..., 9.}v.at (i1) = v.at (i2);// проверка правильности индексов i1 и i2// выполняется внутри функции at ()cout << v.size ();// Размер контейнера для данной точкиContainer::iterator p = v.begin ();p += 2;// Для векторов это можно, для других – advance (p, 2)v.insert (p, 100); // Элементы: 0, 1, 100, 2, ..., 9.p теряет значениеsort (v.begin (), v.end ());// Сортировка диапазонаfor (Cst i = 0; i < v.size (); i++){ // здесь значение индекса i уже проверено, можно пользоваться// непосредственно индексацией v [i], даже если число элементов в цикле меняетсяcout << v[i];}}catch (out_of_range) { ...
} // реакция на ошибочный индекс}int main () { Container v; f (v, 5, 12); }Списки, строящиеся на основе стандартного контейнера list, (уровень разрешённогоитератора – двунаправленный):// определено для всех контейнеров STL (vector, list, ...)// все стандартные контейнеры определены в стандартном// пространстве именования (std)template<class T, class A = allocator<T>> class list;list& operator = (const list <T, A> & obj);list (const list <T, A> & obj); // конструктор копирования// инициализация списка копированием элементов из [first, last)// It - итератор для чтенияlist (It first, It last, const A& = A());// Конструкторы, которые могут вызываться с одним параметром, во избежание// случайного преобразования объявлены как явные (explicit).
Это означает,// что конструктор может вызываться только явно.// (list<int>l = 10 - ошибка, попытка неявного преобразования 10 в list<int>)explicit list (const A& = A ()); // явный вызов конструктора: list<T> x(10);explicit list (size_type size, const T& value = T (),const A& a = A ()); // заводятся сразу несколько элементов со// значениями, которые даются их конструкторами по умолчанию.// Если второй параметр отсутствует, конструктор умолчания в Т// обязателен. Есть и другие виды конструкторов.// Имеются также методы, связанные с итераторами:// iterator begin (), end (); const_iterator begin () const, end () const;#include <list>using namespace std;l.size()past-the-end-elementlist lэлементэлементэлементэлементl.rend()l.begin()l.rbegin()l.end()void push_front(const T& value){ insert (begin (), value); } // вставка в началоvoid pop_front(){ erase (begin ());}//уничтожение первого элементаКонтейнеры в библиотеке STL построены таким образом, что фрагмент учебнойпрограммы для работы с векторами, показанный ранее, может легко быть приспособлен дляработы со списками.
Для этого надо всюду заменить слово vector словом list, а такжевнимательно переработать те операторы, в которых существенно используются свойстваитераторов произвольного доступа, использованные в программе (были выделены шрифтом сподчеркиванием). Например, выдача данных в поток записывается не так, как для векторов (спомощью операции индексации), а иначе:for (int i = 0; i < v.size (); i++)cout << v[i]; // итерация по//не годится для работы соfor (p = v.begin (); p != v.end (); ++p) cout << * p; // итерация по//работоспособно также и длявекторуспискомспискувектораСхема классической системы программированияСистематекстовогоредактированияСистемаграфическогоредактированияИсходнаяпрограммаМакрогенераторКомпиляторАссемблерКомпоновщик(редакторсвязей)БиблиотекиДинамическаязагрузкаОбъектнаяпрограммаГотоваяпрограмма…Загрузчик(в составе ОС)ОтладчикВыполнениеСхема работы компилятора языка программирования(сплошные стрелки указывают порядок работы составных частей компилятора,пунктирные линии отображают потоки информации).Компиляторязыка программированияТаблицыкомпилятораНачальные установкиФазы анализа программИсходнаяпрограммаТекстСканер(лексический анализ)ЛексемыСинтаксический исемантический анализ(контроль контекстныхусловий)Анализ и локализацияобнаруженных ошибокТаблицыслужебныхидентификаторовВнутреннеепредставлениеТаблицаконстантТаблица имёнФазы оптимизации программВнутреннеепредставлениеФазы синтеза программТаблица процедурТаблица блоковРаспределение памятиСообщенияоб ошибкахВнутреннее представлениеТаблица цикловРаспределение регистровВнутреннее представлениеОбъектнаяпрограммаТекст или кодГенерация команд имашинно-зависимаяоптимизацияМножестводругихтаблицСхема работы однопроходного компилятораязыка программированияНачальные установкиИсходнаяпрограммаТекстСканерОбращение залексемойСинтаксическийанализаторЛексемаВозвратуправленияЗавершениеформированияпрограммыСинтаксическая конструкцияСемантический анализатор,распределитель памяти,генератор командТекст или кодОбъектная программаОписание модельного языка.
Правила грамматики:PD1DBS→→→→→EE1TFLINCR→→→→→→→→→program D1;B⊥var D {,D}I {,I}: [ int | bool ]begin S {;S} endI:=E | if E then S else S |while E do S | B | read (I) | write (E)Ε1 | E1 [ = | < | > | <= | >= |!= ] E1T {[ + | - | or ] T}F {[ * | / | and ] F}I | N | L | not F | (E)true | falseC | IC | IRR | NRa | b | ... | z | A | B | ... | Z0 | 1 | 2 | ... | 9Замечания:a) запись вида {α} означает итерацию цепочки α (повторение ее 0 или более раз), тоесть в порождаемой цепочке в этом месте может находиться либо ε, либо α, либоαα, либо ααα и т.д.b) запись вида [α | β] означает, что в порождаемой цепочке в этом месте можетнаходиться либо α, либо β.c) P – цель грамматики; символ ⊥ – маркер конца текста программы.Контекстные условия:1.
Любое имя, используемое в программе, должно быть описано и только один раз.2. В операторе присваивания типы переменной и выражения должны совпадать.3. В условном операторе и в операторе цикла в качестве условия возможно толькологическое выражение.4. Операнды операций отношения должны быть целочисленными.5. Тип выражения и совместимость типов операндов в выражении определяются пообычным правилам; старшинство операций задано синтаксисом.В любом месте программы, кроме идентификаторов, служебных слов и чисел, можетнаходиться произвольное число пробелов и комментариев вида {< любые символы, кроме } и⊥ >}. Вложенные комментарии запрещены.Идентификаторы true, false, read, write и другие, упомянутые среди правилграмматики, – служебные слова (их нельзя переопределять, как стандартные идентификаторыПаскаля).
Эти идентификаторы не имеют никакого отношения к буквам, из которых онисоставлены.Сохраняется правило языка Паскаль о разделителях между идентификаторами, числамии служебными словами.Действия, выполняемые лексическим анализатором (сканером):1.2.3.4.GetSclearaddget_token5.6.7.8.get_objectnew Identnew Numberput_object9. new Token– ввод очередного символа исходной программы.– инициализация буфера ввода символов лексемы.– добавление очередного символа к лексеме в буфере.– поиск лексем в таблицах служебных слов (TW), ограничителей изнаков операций (TD).– поиск объектов в таблице имён TI, либо в таблице констант TC.– создание нового объекта "Идентификатор".– создание нового объекта "Константа".– занесение информации о вновь созданных объектах (константахили идентификаторах) в таблицу констант TC, либо в таблицу имёнTI.– создание новой лексемы при вводе константы или идентификатора(указатель на объект в этой лексеме может быть новым, а можетизвлекаться из соответствующей таблицы)Состояния лексического анализатора:1.2.3.4.5.6.7.8.HCommentNOperatorOperatorLOperatorIdentifierLiteralError––––––––начальное состояниеввод комментария (примечания)ввод знака операции отрицанияввод односимвольного знака операцииввод двухсимвольного знака операцииввод идентификатораввод целочисленной константыошибка' 'GetSНGetS}{GetSCommentGetS'⊥', '{'Error!clear,add,GetSNOperator=add,GetS,get_token+,-,*,/,;,,,(,),=get_token,{GetS/Error}Operatorclear,add⊥(State = Error)clear,add=:,<,>clear,add,GetSadd,GetS,get_tokenLOperatorget_tokenбуква, цифраadd,GetSбукваclear,add,GetSцифраclear,add,GetSIdentifierцифраadd,GetSLiteralget_token,{get_object/}{put_object}get_object/{put_object}Диаграмма состояний лексического анализатора (сканера) модельного языка.Все выходные стрелки предполагают последующий переход в начальное состояние (Н).После чтения конца файла осуществляется переход в состояние Error без выдачи сообщенияоб ошибке (ошибка выдается лишь при повторной попытке чтения).Непомеченные дуги соответствуют переходам по символам, не надписанным ни над однойдугой, исходящей из этой же вершины.Действия, выполняемые при семантическом контроле контекстных условий:1.2.3.4.5.6.7.8.9.resetpushpopdeclcheck_opcheck_notcheck_ideq_typecheck_id_in_read–––––––––очистка стеказанесение нового элемента в стек имен или типовчтение текущего элемента из стеказанесение в таблицу информации о новом идентификаторепроверка совпадения типов двух операндов бинарной операциипроверка типа операнда унарной операции отрицанияконтроль наличия описания идентификаторасравнение типов двух операндов из стекаконтроль наличия описания идентификатора в операторе чтенияГрамматика модельного языка с семантическими действиями:PD1D→→→BS→→EE1TF→→→→LINCR→→→→→program D1;B⊥var D {,D}< reset () > I < push (name) > {, I < push (name) >}:[ int < decl ("int") > | bool < decl ("bool") > ]begin S {;S} endI < check_id () > := E < eq_type () >if E < eq_type ("bool") > then S else S |while E < eq_type ("bool") > do S |B|read (I <check_id_in_read ()>) |write (E)E1 | E1 [ = | < | > | <= | >= | !=] < push (type) > E1 < check_op () >T {[ + | - | or] < push (type) > T < check_op () >}F {[ * | / | and] < push (type) > F <check_op () >}I < check_id () > | N < push (type) > | L < push (type) > |not F < check_not () > | (E)true | falseC | IC | IRR | NRa | b | ...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
