А.В. Столяров - Введение в язык Си++ (1114949), страница 14

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 14)

е. чуть больше четырёх миллиардов.62нится, поскольку равен нулю? Одно из возможных решений — завести впамяти соответствующий элемент, пусть даже и с нулевым значением, ивернуть соответствующую ссылку. Это позволит, безусловно, выполнятьприсваивания, однако приведёт к тому, что при каждом обращении кнулевым элементам (в том числе на чтение, а не на запись) соответству­ющие элементы будут заводиться в памяти и, таким образом, окажется,что изрядное количество памяти занято теми самыми нулевыми значе­ниями, хранения которых можно избежать.Схему можно несколько усовершенствовать, если каждый раз при вы­зове операции индексирования сохранять в приватной части объекта зна­чение индекса или даже адрес заводимого звена списка.

Это позволит приследующем вызове проверить, хранит ли запись, заведённая на предыду­щем вызове, число, отличное от нуля, и если нет, то удалить её, освободивпамять. У такого варианта реализации есть, однако, свой недостаток: назаведение и удаление элементов будет тратиться изрядное количествовремени.Очевидно, было бы великолепно иметь возможность вызывать разныефункции-методы для случаев, когда происходит обращение к элементумассива на чтение и когда индексирование используется для присваива­ния элементу нового значения.

В первом случае можно было бы тогдавозвращать просто значение элемента или ноль, если соответствущегоэлемента в памяти нет; во втором случае можно было бы без особыхпроблем создавать новый элемент и возвращать ссылку на поле, храня­щее значение; это, впрочем, не исключает необходимости проверки наследующем вызове, не оказался ли в соответствующем элементе ноль.К сожалению, такой возможности в Си-|—Ь нет, как нет и возможно­сти определить из тела операции индексирования, вызвана она из левойчасти присваивания или нет10. Соответствующую возможность, однако,можно смоделировать. Никто не мешает нам описать небольшой вспо­могательный класс, объекты которого как раз и будет возвращать нашаоперация индексирования.

Такой вспомогательный объект будет простохранить всю имеющую отношение к делу информацию, а в нашем слу­чае такой информации немного: адрес главного объекта (то есть самогоразреженного массива), с которым нужно работать, и значение индекса,переданное в качестве параметра операции индексирования.Имея эту информацию и соответствующий доступ к объекту массива,наш вспомогательный объект в зависимости от ситуации может произве­сти любые действия, которые в этой ситуации могут потребоваться. Чтоже касается определения, какая из возможных ситуаций имеет место, тоу вспомогательного объекта для этого есть существенно больше возмож­ностей, чем было в теле операции индексирования: ведь все операции,"'Это вполне можно считать недостатком СиН— .

однако критика имеющегося языкавыходит за рамки данного пособия.63применяемые к результату операции индексирования, как раз и будут насамом деле применены к этому объекту. Таким образом, достаточно, на­пример, определить для нашего вспомогательного класса операции пре­образования к типу in t и присваивания, чтобы сделать возможным икорректным следующий код:SparseArrayIntin t x;//...x = a r r [500];a r r [300] = 5 0 ;a r r [200] = 0 ;arr;/ / чтение/ / запись (возможно создание элемента)/ / удаление элемента, если таковой естьК сожалению, у такой реализации есть и недостаток. Дело в том, чтообычное присваивание — это далеко не единственная операция, способ­ная изменить значение целочисленной переменной. Пользователь вполнеможет попытаться использовать, например, такие выражения:a r r [15] += 100;х = a r r [200]++;у = - - a r r [200];Чтобы все подобные операции работали, нам придётся для нашего вспо­могательного объекта определить их все явным образом, что потребуетизрядного объёма работы: языки Си и С и + + поддерживают десять опе­раций присваивания, совмещённых с арифметическими действиями (+=,-=, <<= и т.

п.), плюс к тому четыре операции инкремента/декремента(++ и -- в префиксной и постфиксной форме). В нашем примере мыограничимся описанием операции += и двух форм операции ++. Осталь­ные подобные операции читатель без труда опишет самостоятельно поаналогии.Прежде чем продемонстрировать заголовок класса Spar seArray Int,отметим, что для удобства реализации всех модифицирующих операцийцелесообразно в классе вспомогательного объекта ввести две внутренниефункции. Функция Provide будет отыскивать в списке элемент, соответ­ствующий заданному индексу, и возвращать ссылку на поле, содержащеезначение; если соответствующего элемента в списке нет, функция будетего создавать.

Вторая функция, Remove, будет удалять из списка элементс заданным индексом, если таковой в списке присутствует. Вспомогатель­ный класс назовём Interm от английского intermediate. С учётом этогозаголовок класса будет выглядеть так:class SparseArraylnt {struct Item {int index;64in t v a lu e ;Item *n e x t;};Item * f i r s t ;p u b l ic :S p a rse A rra y ln t() : f i r s t ( O ) { }"S p a r se A r r a y ln t( ) ;c l a s s Interm {fr ie n d c l a s s S p a rse A rra y ln t;S p a rseA rray ln t *m a s te r ;in t in d e x ;In term (Sp arseA rray ln t *a _ m a ste r, in t ind): m a ste r(a _ m a ste r), in d ex (in d ) { }int& P ro v id e (in t i d x ) ;vo id Rem ove(int id x ) ;p u b l ic :o p e rato r i n t ( ) ;in t o p e r a to r = (in t x ) ;in t o p e r a to r + = (in t x ) ;in t o p e r a t o r + + ( ) ;in t o p e r a t o r + + ( in t ) ;};fr ie n d c l a s s Interm ;Interm o p e r a t o r [ ] ( in t id x ){ re tu rn In te r m (th is, id x ) ; }p r iv a te :S p a rse A rra y ln t(c o n st SparseA rrayInt& ) { }vo id o p e ra to r= (c o n st SparseA rrayInt& ) { }В самом классе SparseA rraylnt, как можно заметить, оказывается нетак много функций: основная функциональность оказывается вытесне­на в методы вспомогательного класса.

Единственным методом основногокласса, тело которого в силу размеров не включено в заголовок класса,является его деструктор. Его задача — освободить память от элементовсписка. Деструктор описывается так:Sp arseA rray ln t: : "Sp arseA rrayln t() {w h ile ( fir s t) {Item *tmp = f i r s t ;f i r s t = f ir s t- > n e x t;d elete tmp;}}65Опишем теперь методы класса SparseA rray: : Interm, в которых и за­ключается основная функциональность нашего разреженного массива:in t S p a rse A rra y In t: : In te r m :: o p e r a to r = (in t x){i f ( x == 0) {Rem ove(index);} e lse {P ro v id e(in d ex ) = x ;}re tu rn x ;}in t S p a rse A rra y In t: : In te r m :: o p e r a to r + = (in t x){int& lo c a tio n = P r o v id e (in d e x );lo c a tio n += x;in t r e s = lo c a tio n ;i f ( r e s == 0) Rem ove(index);re tu rn r e s ;}in t S p a rse A rra y In t: : In te rm ::o p e ra to r+ + (){int& lo c a tio n = P r o v id e (in d e x );in t r e s = + + lo c a tio n ;i f ( l o c a t i o n == 0) Rem ove(index);re tu rn r e s ;}in t S p a rse A rra y In t: : In te r m :: o p e ra to r+ + (in t){int& lo c a tio n = P r o v id e (in d e x );in t r e s = lo c a tio n + + ;i f ( l o c a t i o n == 0) Rem ove(index);re tu rn r e s ;}S p a rse A rra y In t: : In te rm :: o p e rato r in t ( ){Item * tmp;for(tm p = m a s t e r - > f i r s t ; tmp; tmp = tm p->next) {if(tm p -> in d e x == in dex) {re tu rn tm p->value;}}re tu rn 0;}Наконец, опишем вспомогательные функции Provide и Remove:int& S p a rse A rra y In t: : In te rm :: P ro v id e (in t id x )66{Item * tmp;for(tm p = m a s t e r - > f i r s t ; tmp; tmp = tm p->next) {if(tm p -> in d e x == index)re tu rn tm p->value;}tmp = пей Item ;tm p->index = in dex;tm p->next = m a s t e r - > f ir s t ;m a s t e r - > f ir s t = tmp;re tu rn tm p->value;}vo id S p a rse A rra y ln t: : In te r m ::Rem ove(int id x ){Ite m ** tmp;for(tm p = & ( m a s t e r - > f i r s t ) ; *tm p; tmp = & (*tm p)->n ext){i f ( (*tm p )->in d ex == in dex) {Item *to _ d e le te = *tm p;*tmp = (*tm p )-> n ex t;d e le t e to _ d e le te ;re tu rn ;}}§2.21.

С тати чески е п о л я и м етодыИногда бывает полезно иметь переменные и методы, которые, с од­ной стороны, доступны только из класса и/ или воспринимаются как егочасть, но, с другой стороны, не привязаны ни к какому из объектов и мо­гут использоваться даже тогда, когда ни одного объекта данного классане существует. В языке С и + + такие члены класса называются с т а т и ­ческими и обозначаются ключевым словом s t a t i c 11.§2.21.1. Статические поля и особенности ихопределенияС т а т и ч е с к о е поле класса представляет собой, в сущности, обыч­ную переменную, время жизни которой совпадает с временем выполне-111 Не путайте их с локальными переменными и функциями модулей, а также с ло­кальными переменными функций, которые сохраняют своё значение при повторномвходе в функцию; как и в языке Си, в СиН—Ь эти сущности тоже обозначаются словомs ta t ic , но практически ничего общего не имеют со статическими членами класса.67ния программы; точно таким же свойством обладают, например, глобаль­ные переменные.

С другой стороны, правила видимости для статическогополя класса точно такие же, как и для обычных полей: статическое полевходит в область видимости класса, так что при упоминании статическо­го поля вне методов класса необходимо использование символа раскры­тия области видимости : : 12; наконец, на статическое поле распростра­няются механизмы защиты, так что, если его расположить в приватнойчасти класса, доступ к такому полю будет возможен только из методовкласса и друзей класса.Сущность статических полей класса можно пояснить и иначе: стати­ческое поле — это такое «хитрое» поле, которое существует в одном эк­земпляре для всего класса, вне зависимости от количества объектов этогокласса; даже если ни одного объекта нет, статическое поле всё равно су­ществует, коль скоро оно описано в классе.

Получается, что статическоеполе, в отличие от обычного, не является составной частью о б ъ е к т а ипринадлежит классу как единому целому.С т а т и ч е с к о е поле описывается в классе точно так же, как и обыч­ное поле класса, только с добавлением спереди слова s t a t ic :c la s s C ls {и ...s t a t i c in t th e _ s ta tic _ fie ld ;П ...>;Имеется, однако, очень важное отличие: если описание обычного полясамо по себе уже означает, что в объекте под это поле будет выделеноместо, то описание статического поля означает лишь, что м е с т о под э т ополе б у д е т выделено г д е -т о в одном из модулей програм м ы .Читатель, хорошо знакомый с языком Си, может заметить здесь прямую ана­логию с объявлениями глобальных переменных с директивой extern. Чтобы по­нять, почему описание статического поля в классе считается именно декларацией,а не определением, подумайте, что будет, если заголовок класса будет вынесен взаголовочный файл, а сам этот файл — включён из нескольких модулей.Итак, чтобы завершить создание статического поля, необходимо внек л асса поместить его определение:in t A ::th e _ s ta tic _ fie ld = 0;Обычно определения статических полей снабжают инициализацией, какэто сделано и в нашем примере, хотя это и не обязательно.Обратите внимание, что, если ваше описание класса вынесено в заго­ловочный файл, то определения статических полей следует о бязател ь­но пом естить в ф ай л реализации одного из модулей, ни в коемслучае не в заголовочный файл!12Мы уже встречались с символом раскрытия области видимости в § 2.15 на стр.

Характеристики

Список файлов книги