Стандартные типы данных — различия между версиями

Текущая версия на 15:18, 13 июля 2013

В этой главе будут рассмотрены базовые типы данных, применяющиеся в языке К++. Большинство из них объявлены в стандартной библиотеке Gide, однако некоторые, например интервалы, описываются в системной библиотеке самого языка К++. Еще раз напомним Читателю, что в языке К++, стандартные типы данных не являются встроенными. Конечно, компилятор опирается на них при генерации кода, но это совершенно не означает, что их нужно воспринимать как что-то единожды определенное и неизменное. Как уже было показано в книге, как с точки зрения компилятора так и самой виртуальной машины, эти классы ничем не отличаются от обычных, пользовательских классов, когда дело касается их использования на высоком уровне. Если забежать вперед, то можно отметить, что на низком уровне они реализованы на языке C++ (из соображений производительности) и их интерфейсы представлены в стандартной библиотеке. Тем не менее, существует возможность их дополнения программистом-пользователем, что и было проделано в главах, посвященных расширениям. Разумеется, от этих классов возможно наследовать собственные классы, точно так же, как и от любых других. В этой главе мы рассмотрим стандартные типы данных с точки зрения их применения и укажем некоторые свойства которые не были упомянуты в ходе повествования.

[править] Целые числа

Основой всей арифметики являются числа. Для представления чисел в программах применяются классы, объекты которых выступают как хранилища значений. Существует несколько классов целых чисел, различающихся по длине охватываемого ими диапазона и по возможности указания знака:

Для педставления целых чисел применяется класс int, умеющий хранить числа в диапазоне от -9223372036854775808 до 9223372036854775807.

Класс поддерживает все возможные арифметические операции, а так же имеет операторы преобразования в строку и из строки. Однако, следует быть осторожным и не полагаться полностью на автоматическое приведение типов. В некоторых случаях, можно получить не те результаты, что ожидает программист. Например: <source lang=kpp> var i = 1; var j = "2"; puts(i + j); puts(j + i); </source>

В приведенном выше примере, объявлены две переменных: целочисленная i и переменная j, содержащая строку "2". При вычислении первой суммы происходит следующее: компилятор "видит", что необходимо посчитать сумму переменных i и j, которые для нас являются представлениями чисел 1 и 2. Но с точки зрения компилятора, это всего лишь две инстанции классов int и string соответственно.

Разбор выражения производится слева-направо, так же как его считает человек. Компилятор пытается найти в классе int оператор + с типом второго операнда, то есть string. Такого оператора в классе нет. Тогда компилятор смотрит, существует ли в классе string оператор приведения к типу int, либо к другому типу, для которого в классе int объявлен оператор +. Такой оператор находится, соответственно компилятор генерирует вызов оператора приведения для переменной j, а затем уже выполняется сам оператор +. Поэтому, сложение происходит численно, так как и ожидалось. Результат суммы будет соответствовать числу 3: <source lang=kpp> i + j = 1 + ("2" as int) = 1 + 2 = 3 </source>

Во втором случае, все происходит с точностью наоборот: первым операндом является строка, то есть инстанция класса string. В этом классе так же объявлен оператор +, но принимающий в качестве второго операнда строку. Этот оператор используется для конкатенации двух строк, при которой вторая строка дописывается в конец первой, то есть: <source lang=kpp> var s1 = "hello"; var s2 = "world"; puts(s1 + s2); //результат: "hello" + "world" = "helloworld" </source>

В нашей сумме, вторым операндом является инстанция класса int, которая по вышеописанным правилам, будет приведена к типу string. Таким образом, операция суммы будет приведена к операции конкатенации строк "2" и "1", то есть результат выражения будет "21": <source lang=kpp> j + i = "2" + (1 as string) = "2" + "1" = "21" </source>

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

[править] Числа с плавающей точкой

Для проведения сложных математических рассчетов, одних целых чисел недостаточно. Для представления действительных чисел, или чисел с плавающей точкой (запятой), как их называют в информатике, в стандартной библиотеке создан класс real, который на низком уровне представлен типом двойной точности (double).

В отличие от класса string, класс real корректно обрабатывается в сочетании с целочисленными классами. Например, следующие выражения дадут одинаковые результаты: <source lang=kpp> var i = 3 + 0.1415 var j = 0.1415 + 3 </source>

В результате, обе переменных будут иметь тип real и значение 3,1415. Это достигается тем, что в классе int есть специальные версии арифметических операторов, которые принимают в качестве параметра объекты класса real.

[править] Логический тип

В некоторых случаях в программе бывает необходимо сохранять логическое значение. Это может потребоваться в алгоритмах, где такое значение используется в качестве флага, либо в свойствах объектов, которые подразумевают наличие или отсутствие некоторого признака. Это осуществляется с помощью булевых переменных и псевдотипа bool. Переменные булевого типа могут иметь только два значения: true, соответствующее истине и false, соответствующее лжи.

К переменным булевого типа могут приводиться значения более сложных выражений, например когда такое выражение находится в условии цикла. Правила преобразования значений выражений были описаны при рассмотрении условного оператора if.

Примечание: псевдотипом bool назван потому, что он не является классом в полной мере. Это абстракция, которая была введена в язык К++ для преодоления некоторых сложностей при проектировании языка. Переменные такого класса обрабатываются на уровне самого К++; с точки зрения Gide такого класса не существует (вернее, существуют специальные объекты @true и @false, но это тема, требующая отдельного обсуждения).

Существует несколько ограничений, которые важно понимать. Первое ограничение заключается в том, что от этого типа нельзя наследовать собственные классы. Второе ограничение проявляется в том, что переменные типа bool обрабрабатываются особым образом. Если в выражении присутствует переменная булевого типа, то операторы отношения работают немного по другому. Например, следующее выражение будет трактовано как истина: <source lang=kpp> if (0 == true)

  //...

</source>

Условие сработает потому что 0 представляет собой действительный, существующий объект, стало быть он истинен (об этом уже было написано). Вот другой пример, иллюстрирующий ту же проблему: <source lang=kpp> var MyClass c = new MyClass; if (c == true)

  //...

</source>

Подобное условие так же сработает (будет считаться истинным), поскольку оператор == в данном случае обрабаытвается самим компилятором. Конечно, приведенные примеры являются довольно странными с точки зрения обычного кода, но их все же следует иметь в виду при написании программ.

[править] Строки

Для хранения и обработки строковых данных используется класс string. Он объявлен в стандартной библиотеке Gide и дополнен с помощью расширений в системной библиотеке К++.

В языке К++ предусмотрены целых три синтаксиса для объявления строковых констант, которые в конечном счете представляются одним и тем же классом string.

Строки, заключенные в двойные кавычки обрабатывают все escape последовательности, а так же позволяют использовать т. н. вставки, или подстановки — кусочки кода, которые вставляются непосредственно в тело строки и при работе программы заменяются на значение, возвращаемое этим кодом (см. ниже). Обрабатываются следующие последовательности:

Последовательность	Значение
\n	перенос строки
\r	возврат каретки
\t	символ табуляции
\"	символ двойной кавычки
\\	символ обратного слеша
#{ }	подстановка выражения

При этом, при обработке строки, найденные последовательности заменяются на соответствующий им управляющий символ. Например, последовательность \n будет заменена на один символ перевода строки (ASCII код 13).

Подстановки это очень удобный способ совмещать в одном выражении строку которую необходимо вывести и выражения, значение которых необходимо добавить к выводу. Получается что подстановки это что-то среднее между простой строкой и строкой для форматируемого вывода. Подстановка начинается с пары символов #{, которые должны идти друг за другом, без пробелов. То что идет дальше, воспринимается компилятором как выражение, как если бы оно было записано просто в коде, вне строки. Завершает подстановку соответствующая ей закрывающая фигурная скобка.

Приведем пример использования подстановок: <source lang=kpp> var s1 = "сумма чисел 2 и 3 равна #{2 + 3}."; print("s1 = #{s1}\n"); </source>

При разборе выражения компилятор преобразовывает данное выражение в сумму, представляющую из себя последовательность строковых констант и выражений: <source lang=kpp> var s1 = "сумма чисел 2 и 3 равна " + (2 + 3) + "."; print("s1 = " + (s1) + "\n"); </source>

В результате выполнения этого кода, в выводе появится текст (курсор будет переведен на следующую строку):

s1 = сумма чисел 2 и 3 равна 5.

Подстановки даже можно делать вложенными, например так:

var x = [ 1, 2, 3, 4, 5 ];
var s = "some weird stuff: #{ x.join(', ') { |idx,elem| "#{idx} = #{elem}"; } }\n";

Если требуется работать со строкой, которая содержит escape последовательности (или подстановки), которые не требуется обрабатывать то следует применять строки, заключенные в одинарные кавычки: <source lang=kpp> var s1 = 'в таких строках \n \r \t и #{подстановки} не обрабатываются'; </source> Исключением из правила являются последовательности \' и \\.

Третьим способом объявить строку является применение синтаксиса кратких, "однословных" строк. Такие строки начинаются со знака двоеточия, следом за которым могут идти те же символы, что возможны при написании идентификаторов, то есть: латинские буквы, цифры и знак подчеркивания, притом что первой после двоиточия обязательно идет либо буква, либо подчеркивание. Такие строки могут быть особенно полезны при записи ключей хеша (как будет показано ниже), либо просто в тех местах где в качестве строки передается одно слово:

<source lang=kpp> var h = { :sunday = 1, :monday = 2, :tuesday = 3 }; var x = my_function(:hello); </source>

Так же, класс string предоставляет пользователю широкий спектр различных методов, которые могут использоваться для работы со строками.

[править] Длина строки

Для определения длины строки используется метод length(), который возвращает число символов в строке. Так же, существует метод empty() который возвращает истину если строка пуста и ложь в противном случае.

[править] Выделение подстрок

Для выделения из исходной строки подстрок, разделенных символом или несколькими символвами разделителями, используется метод split(). В качестве параметра, этот метод принимает строку, либо регулярное выражение, соответствующие разделителю. Возвращает метод уже массив из полученных подстрок.

В качестве примера приведем два способа обработки URL строки и выделения из нее отдельных частей: <source lang=kpp> var url = "http://example.com?key1=value1&key2=value2&key3=value3"; var qm = url.find("?"); var args = url.substr(qm, url.length()); var pairs = args.split('&'); var options = new hash; pairs.each() { |pair|

   var kv = pair.split('='); 
   options[kv[0]] = kv[1]; 

}; </source>

С помощью метода find() мы находим позицию символа вопроса в исходной строке, который разделяет адрес на собственно адрес ресурса и на строку параметров запроса. Строка параметров состоит из множества пар значение=результат, отделенных друг от друга символом амперсанда. Выделив подстроку запроса, мы разделяем ее на подстроки с помощью метода split(), указывая амперсанд в качестве разделителя. Полученный массив подстрок мы сохраняем в переменной pairs. Теперь, мы заводим хеш options в который будем записывать параметры запроса, по мере его обработки. Выполняя перебор по всем парам, мы опять разделяем их на две части, на этот раз по символу равенства. Последним действием, полученная пара значение-результат сохраняется в хеше.

Несмотря на то, что вышеприведенный код работает, он является не очень эффективным. В процессе его работы создается много промежуточных переменных и может задействоваться большое количество памяти (при длинных строках запросов). При задачах обработки строк выгодно использовать регулярные выражения. Они позволяют относительно легко производить обработку строк; выполнять поиск и замену по некоторому шаблону. Приведем другой, более элегантный способ решения той же самой задачи, но уже с использованием регулярных выражений: <source lang=kpp> var options = new hash; if (url =~ `\?(.*)$`) {

   //разделяем строку на пары значение=результат
   var pairs = $[1].value.split('&');
   //обрабатываем пары по очереди
   pairs.each() { |pair|
       if (pair =~ `^([\w\d]+)=([\w\d]+)$`)
           options[$[1].value] = $[2].value;
   };

} </source>

Оператор =~ служит для связи исходной строки с регулярным выражением. В результате, в специальный массив $[] будут помещены все совпадения. Элемент с индексом 0 будет соответствовать всей совпавшей подстроке, в остальных элементах будут находиться совпадения, соответствующие подвыражениям в скобках.

Примечание 1: элементы спецмассива $[] представляют собой не сами подстроки, а объекты-совпадения, класса regexp_match. В этих объектах содержится дополнительная информация о совпадении, например:

• индексы левой и правой границы (свойства left и right)
• длина подстроки (свойство length)
• и, естественно, сама подстрока (свойство value)

Получить доступ к подстроке так же можно, выполнив явное приведение объекта совпадения к типу string. Таким образом, следующие строки функционально эквивалентны: <source lang=kpp> var substr1 = $[1].value; var substr2 = $[1] as string; </source>

Примечание 2: в принципе, можно было и не объявлять отдельную переменную pairs. В книге это было сделано для большей читаемости кода, однако на практике может применяться и более лаконичная форма, которая, тем не менее, остается довольно удобной к восприятию: <source lang=kpp> if (url =~ `\?(.*)$`) {

   $[1].value.split('&').each() { |pair|
       if (pair =~ `^([\w\d]+)=([\w\d]+)$`)
           options[$[1].value] = $[2].value;
   };

} </source>

При желании, можно еще больше упростить код, используя версию оператора [], принимающую регулярное выражение в качестве параметра и возвращающее соответствующую ему подстроку: <source lang=kpp> url[`\?(.*)$`].value.split('&').each() { |pair|

   if (pair =~ `^([\w\d]+)=([\w\d]+)$`)
       options[$[1].value] = $[2].value;

}; </source>

Однако, в этом случае, при отсутствии требуемой подстроки в исходной переменной url, будет сгенерировано исключение и это следует корректно обрабатывать.

[править] Объединение строк (конкатенация)

Конкатенация строк осуществляется с помощью обычных арифметических операторов (при этом, приоритеты операций остаются теми же). В зависимости от оператора, действие будет производиться над самим объектом или над его копией: <source lang=kpp> var s1 = "hello"; var s2 = "world"; var s3 = s1 + ' ' + s2; // s3 = "hello world", s1 и s2 те же s1 = (s3 += "!"); // s1 = s3 = "hello world!" s2 *= 2; // s2 = worldworld s3 = s1 + '!' * 2; // s3 = "hello world!!!" </source>

Обратите внимание на две последние строки. Оператор *, выполняемый над строкой действительно "умножает" ее, повторяя заданное количество раз.

[править] Операторы индексного доступа

Для доступа к отдельным символам строки может использоваться оператор индексного доступа []. При этом, строка представляется как массив, где каждый элемент соответствует номеру символа в unicode: <source lang=kpp> var str = "hello world"; var ord = str[0]; // ord = 104 </source>

Можно совершать и обратную операцию, а именно присваивать по некоторому индексу числовое значение. Тогда в строке будет стоять символ, соответствующий указанному числу: <source lang=kpp> str[0] = 72; // str = "Hello world" str[6] = 'W'[0]; // str = "Hello World" </source>

Существует дополнительный синтаксис, специально предназначенный для получения номера некоторого символа. Он осуществляется записью символа диез ("решетка"), с последующим добавлением исследуемого символа. Таким образом, вторую строку из предыдущего примера можно записать так: <source lang=kpp> str[6] = #W; // str = "Hello World" </source>

Этот синтаксис можно применять даже для управляющих символов вроде \n и даже для любого символа Unicode: <source lang=kpp> var n = #\n; // n будет содержать число 13 var f = #Ф; // код, соответствующий русской заглавной букве Ф </source>

Если же требуется получить подстроку исходной строки на основании индексов символов, нужно применять интервалы: <source lang=kpp> var s2 = str[0 .. 4]; // s2 = "Hello" </source>

Возможно так же использовать оператор индексного доступа для присвоения значения отдельным подстрокам. Это осуществляется с помощью оператора []=: <source lang=kpp> var greeting = "Welcome to the real world, Neo."; greeting['real world'] = 'matrix'; // Welcome to the matrix, Neo. greeting[15 .. 20] = 'Deeptown'; // Welcome to the Deeptown, Neo. greeting[-1] = #!; // Welcome to the Deeptown, Neo! greeting[`\sNeo.$`] = 'Leonid!'; // Welcome to the Deeptown, Leonid! </source>

В примере выше, применены четыре способа индексного доступа для изменения строки, соответствующие четырем различным операторам (точнее, четырем версиям перегруженного оператора). В первом случае используется доступ по подстроке. При этом подстрока будет "вырезана" из строки, а на ее место будет вставлена присваиваемая строка. Таким образом, эта операция не зависит от размера искомой и заменяемой подстрок (если заменяемая строка длиннее, исходная строка будет "раздвинута").

Во втором случае осуществляется доступ по интервалу. Символы с индексами в диапазоне 15-20 соответствуют слову "matrix". Замена опять же производится по правилу "вырезания" подстроки с последующим "склеиванием".

В третьем случае, используются отрицательные индексы, для указания того, что отсчитывать символы нужно с конца строки. Так, -1 соответствует последнему символу, -2 второму с конца и т. д.

Наконец, в последней замене применяется регулярное выражение, для поиска подстроки.

Примечание: Методы замены через оператор []= на деле являются обертками к соответствующим реализациям метода replace_all(). При этом, будут производиться замены всех включений подстроки в исходную строку (разумеется, кроме случаев ин тервала и одиночного индекса). Если вы хотите заменить только одно включение, — используйте методы replace().

[править] Интервалы

В некоторых случаях бывает необходимо передать в качестве параметра не отдельное значение а диапазон. Для указания диапазона обычно достаточно указать только его границы. Это может осуществляться с помощью класса interval. К++ предоставляет специальный синтаксис для указания интервалов с помощью оператора ".."; как уже было показано выше, это может применяться для выборки подстрок, соответствующих заданному диапазону индексов, либо подмассивов по тому же принципу: <source lang=kpp> var s = "abcdef"[0..2]; // "abc" var a = [1, 2, 3, 4][1..-1]; // [2, 3, 4] </source>

Вообще, интервалы могут быть не только численными. В качестве объектов, формирующих интервал, могут выступать любые два объекта, имеющие одинаковые типы: <source lang=kpp> var left = MyClass.Create(5), right = MyClass.Create(10); var i = interval.create(left, right); var alpahbet = 'a' .. 'z'; </source>

Интервалы могут использоваться как виртуальные массивы, то есть к ним можно обращаться как к массиву, запрашивая некоторый элемент по индексу. И он будет возвращен, как будто действительно хранится в массиве (на сама деле, он создается в момент обращения по некоторому известному закону): <source lang=kpp> var numbers = 1 .. 100; var alpahbet = 'a' .. 'z'; var x = numbers[50]; // x = 1 + (50-1) = 50. var y = alphabet[10]; // y = (#a + (10-1)).char = 'k' </source>

Преимуществом такого подхода является то, что не нужно хранить весь массив в памяти. Зная закон изменения элементов, можно получить любой элемент, зная базу (одну из границ) и индекс элемента.

Подобно массивам, интервалы так же обладают методом each(), позволяющем проходить по всему массиву, выполняя некоторый блок с параметром текущего элемента массива: <source lang=kpp> var s = 0; //здесь будет сумма var numbers = 1 .. 100; numbers.each() { |x| s += x; }; </source>

Для выяснения принадлежности некоторого объекта к интервалу могут применяться метод contains() или соответствующий ему оператор in: <source lang=kpp> var numbers = 1 .. 100; var lowercase = 'a' .. 'z'; var x = numbers.contains(75) ? "yes" : "no"; //x = "yes" var y = 'X' in lowercase ? "yes" : "no"; //y = "no" </source>

Для создания интервалов на базе собственных классов необходимо перегрузить конструктор, а так же соответствующие методы, своими реализациями.

[править] Массивы и списки

Для хранения наборов объектов применяются массивы и списки. И те и другие являются контейнерами, то есть, их объекты способны хранить в себе другие объекты и обладают соответствующими методами для добавления в них элементов и их извлечения. Разница между массивом и списком заключается в том, что массив хранит элементы в одной цельной области памяти, в то время как список организует их в виде цепочки связанных друг с другом элементов:

У каждого из этих контейнеров есть свои преимущества и недостатки. Постараемся рассмотреть основные операции, осуществляемые с контейнерами и выяснить, в каких случаях предпочтительнее использовать массив, а в каких список.

[править] Доступ к данным

Массивы обладают высокой скоростью доступа к информации, поскольку все данные находятся в одном месте и структурированы. То есть, доступ есть сразу ко всем элементам, поэтому не приходится двигаться вдоль массива для поиска нужного элемента. Списки работают несколко по другому. Для того, чтобы обратиться к некоторому элементу списка, необходимо пройти всю цепочку от начала до требуемого элемента (см. рисунок выше). Поэтому, списки значительно уступают по скорости доступа массивам. В случаях, когда содержимое контейнера меняется относительно редко, но присутствует большое количество обращений к данным, следует применять массивы.

[править] Добавление элементов

Рассмотрим операцию добавления элементов в список. Предположим, что нам надо добавить элемент N в список, между вторым и третьим его элементами. Для выполнения этой операции, нам необходимо всего лишь "разорвать" цепочку в нужном месте и изменить указатель у предыдущего элемента X₂ так, чтобы он указывал на новый элемент N. Для того, чтобы продолжить цепочку, элемент N должен указывать на следующий элемент списка, то есть на X₃:

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

В случае массивов все усложняется. Как уже было сказано выше, массивы хранят элементы в монолитных областях памяти, следовательно, чтобы добавить или удалить элемент, приходится задействовать весь массив. Если места в текущей области памяти, занятой массивом недостаточно, чтобы вместить еще один элемент, то произойдет выделение нового блока памяти, с последующим копированием всех существующих элементов массисва в новый блок.

Операция выделения производится "с запасом", то есть, размер нового блока будет больше, чем размер занимаемый всеми элементами, причем зависимость тут экспоненциальная: чем больеше будет добавляться элементов в массив, тем больше будет размер выделяемого блока памяти. Это делается для того, чтобы минимизировать риск полного копирования. Тем не менее, такое может случиться (а при операции вставки — случается обязательно), что в итоге может привести к значительной задержке.

Рассмотрим тот же случай, что и в случае со списком, а именно, операцию вставки нового элемента, между вторым и третьим элементами массива. Для выполнения этой операции создается новый массив, с размером, достаточным для помещения всех предыдущих элементов, а так же нового элемента. Далее, происходит копирование всех элементов на соответствующие места:

Это случай неудачного стечения обстоятельств, при котором происходит копирование большого количества информации, что естественным образом сказывается на призводительности всей операции. Из этого можно сделать вывод, что массивы следует применять тогда, когда операции вставки или добавления элементов происходят редко. В случаях, когда необходимо организовывать стеки или очереди, где обращение по номеру элемента не требуется, наилучшим решением будет использование списков.

[править] Применение

Разобравшись с философией работы массивов и списков, поняв разницу между ними и определившись с областями применения тех и других, мы переходим непосредственно к практике. Массивы и списки в языке К++ представляются классами array и list соответственно. Оба класса имеют очень похожие наборы методов, так что дважды изучать одно и то же не придется.

Объявление массива реализуется с помощью специального синтаксиса, встроенного в язык К++. Это может осуществляться как в инициализаторе переменной, так и в любом другом выражении, вплоть до фактического параметра в коде вызова функции, или даже для указания значения по умолчанию для него.

Для того, чтобы объявить массив, необходимо перечислить его элементы, заключив их в квадратные скобки и отделив друг от друга запятой: <source lang=kpp> var my_array = [1, 2, 3]; </source>

В качестве элементов массива могут быть указаны любые объекты: числа, строки, экземпляры классов, блоки и даже вложенные массивы с хешами — массиву все равно что хранить, поскольку все что он делает, это хранит ссылки на объекты: <source lang=kpp> var myobject = new MyClass; var object_dump = [1, 3.14, 'hello', myobject, {|x| return x + 1;},

   {:a => 1, :b => 2 }, [1,2,3], true, 10 .. 20];

</source>

Можно сказать, что массив представляет собой реализацию абстрактного упорядоченного хранилища данных с возможностью произвольного доступа.

Специального синтаксиса для создания списков нет, поскольку большинство задач которые решают списки не предполагают инициализации значениями. Если же это все таки потребовалось, на помощь придут массивы. Вот небольшой пример того как можно занести в список значения из массива, создаваемого компилятором автоматически: <source lang=kpp> var my_list = new list; [1, 2, 3].each() { |x| my_list.push(x); }; </source>

В этом примере показываются сразу два важных приема, которые являются одними из самых частых по использованию (если вы внимательно читали книгу, то наверняка это заметили). Метод each() используется для перебора всего содержимого коллекции (массива, списка или интервала) и вызова некоторого блока, передавая ему на каждой итерации значение текущего элемента. Таким образом, в случае нашего массива, блок будет вызыван три раза, с параметрами, соответственно, 1, 2 и 3. Метод push() присутствует как в массивах, так и в списках, и служит для добавления элемента в конец коллекции. Здесь он применяется для добавления текущего элемента массива в список. Получается, что по выполнении этой процедуры, список будет содержать в себе все элементы, присутствующие в массиве (в том же порядке).

Существуют еще несколько методов, похожих на метод each(), но отличающихся передаваемыми в блок параметрами. Например each_index() вызывает блок, передавая ему текущий индекс, а метод each_pair() передает ему текущий индекс и элемент. За неимением индекса, списки два последних метода не реализуют. Переделаем немного предыдущий пример и покажем использование этих методов: <source lang=kpp> var my_array = [1, 2, 3]; var my_list = new list; my_array.each() { |x| my_list.push(x); };

my_list.each() { |x| print("#{x}\n"); }; my_array.each_pair() { |i, e| print("my_array[#{i}] = #{e}\n"); }; </source>

Иногда бывает необходимо поместить элементы массива или списка в строку. Например, чтобы вывести их пользователю или, возможно, записать в файл некоторые настройки, подразумевающие список значений. Это может быть сделано с помощью метода join() который возвращает строку с элементами, перемежая их некоторой строкой-разделителем. Разделитель может быть передан в качестве параметра; по умолчанию это строка ", " (запятая с пробелом):

<source lang=kpp> var my_array = [1, 2, 3]; var my_list = new list; my_array.each() { |x| my_list.push(x); };

var s_list = '[' + my_list.join() + ']'; // slist = "[1, 2, 3]" //дальнейшая работа с s_list (например, вывод на экран) </source>

Это простой пример использования метода join, при котором он используется для создания текстового представления содержимого списка. Для удобства и указания границ, добавляются квадратные скобки. Вот другой пример использования метода, на этот раз, для сохранения некоторого списка ресурсов которые используются приложением:

<source lang=kpp> //подготавливаем список опций var search_dirs = new list; search_dirs.push('http://example.com/db/'); search_dirs.push('ftp://example.org/db/'); search_dirs.push('diss:/media/storage/~user1/');

//открываем поток файла настроек var config = stream.open('diss:/etc/sample.conf', stream.create | stream.write); config.write('dbpath=' + search_dirs.join(';')); //записываем строку конфигурации </source>

Как мы видим, сначала происходит заполнение списка значениями URL ресурсов, а затем полученный список записывается в поток. Класс потока это абстракция, предоставляемая ядром Диптауна для доступа к различным ресурсам. Все что необходимо сделать чтобы использовать потоки, это создать инстанцию класса stream с момощью конструктора create(), указав требуемый URL потока и задать режим доступа к ресурсу (с помощью констант класса). При этом, на пользовательском уровне, требуется только писать в поток и читать из него; пользователь не должен беспокоиться, каким образом будет происходить реальная работа с данными на низком уровне — этим занимается ядро. Если же ядро не поддерживает конкретный тип потока — будет сгенерировано исключение.

Для последуюезго разбора полученной строки, можно применять уже известный нам метод split() и регулярные выражения.

В заключение, приведем две реализации кода, вычисляющего первую сотню простых чисел. Одну реализацию мы напишем с использованием списков, а другую с помощью массивов. В нижеприведенном коде активно применяются циклы, так что, для лучшего понимания материала, Читателю предлагается забежать вперед и ознакомиться с ними. Итак, первая реализация: <source lang=kpp line=1> function GetPrimes() {

   var primes = new list;
   var x = 1;
   while (primes.size() < 100) {
       x++; //текущий кандидат
       var is_prime = true;
       for (var p = primes.begin(); p != primes.end(); ++p)
           if (x % p.object == 0) {
               is_prime = false;
               break;
           }
       if (is_prime) {
           primes.push(x); //помещаем число в список
           print("the #{primes.size()} prime number is #{x}\n");
       }
   }

} </source>

Алгоритм поиска такой: берем число и начинаем вычислять остаток от его деления на все элементы нашего списка, то есть, выполняем попытку разложения числа на простые сомножители. Если число делится без остатка хотя бы на один из сомножителей (условие в строке 9), то число не является простым. Следовательно проверять его дальше не имеет смысла. Мы прекращаем цикл с помощью оператора break и сбрасываем флаг is_prime. Если после перебора всех множителей, флаг остался установленным, то это значит, что текущее число (переменная x) является и вправду простым: его мы помещаем в конец списка. Так продолжается до тех пор, пока в списке не окажится 100 элементов. Для проверки размера списка (условие цикла while в строке 4) применяется метод size().

Обратите внимание на то, каким образом реализуется перебор значений списка. Для этой операции применяется итератор. Итератор — это специальный класс, объекты которого используются в качестве указателей на элементы контейнеров. Как правило, итераторы имеют методы для перемещения по контейнеру (операторы ++ и --) и некоторое свойство, позволяющее обратиться к текущему элементу, на который указывает итератор. В случае класса list_iterator, это свойство object.

Для перебора списка применяется цикл for. В инициализаторе цикла была создана управляющая переменная p, которая и является инстанцией итератора (класса list_iterator). Список имеет специальный метод begin(), который создает инстанцию итератора и устанавливает ее на свое начало.

Метод end() возвращает значение специального итератора, который всегда указывает на конец списка. Его нельзя двигать, и служит он только для одной цели — для проверки граничных условий. Важно понимать, что под концом списка понимается не последний его элемент, а именно конец — нечто, следующее за конечным элементом. Таким образом, условие в цикле for проверяет, есть ли еще элементы "справа" от итератора p. Если условие истинно, значит итератор находится где то в середине списка и можно продолжать итерации; если ложно — значит предыдущий элемент был последним и больше элементов в списке нет.

Вот второй способ реализации того же участка кода, но как уже говорилось выше, с помощью массива: <source lang=kpp line=1> function GetPrimes() {

   var primes = new array;
   primes.resize(100); //задаем размер массива
   var x = 1;
   var count = 0; //текущее число найденных простых
   while (count < 100) {
       x++; //текущий кандидат
       var is_prime = true;
       for (var i = 0; i < count; ++i)
           if (x % primes[i] == 0) {
               is_prime = false;
               break;
           }
       if (is_prime) {
           primes[count++] = x; //помещаем число в массив
           print("the #{count} prime number is #{x}\n");
       }
   }

} </source>

Поскольку мы заранее знаем размер массива, который нам может потребоваться (100 элементов), мы можем выделить всю необходимую память одним махом. Это будет намного быстрее, чем выделять память по мере итераций, ведь копирование элементов массива в новое место будет произведено всего один раз. Для изменения размера массива применяется метод resize(). В качестве аргумента метод принимает число — размер массива, который мы желаем получить. Если желаемый размер меньше текущего, то массив будет урезан до нового размера (элементы, оказавшиеся "за бортом", будут выброшены). Если больше — массив будет расширен, причем все старые элементы останутся невредимыми на своих местах, а новые примут значение null.

Ввиду того, что размер массива был задан заранее, проверять конечное условие по количеству элементов нельзя (оно уже равно 100). Поэтому, была введена новая переменная count, в которой мы будем хранить текущее количество найденных простых чисел, а поскольку размещаем мы их строго последовательно, то и индекс последнего найденного простого числа всегда будет известен (какой?).

При работе с массивами никакие итераторы нам не нужны — у нас есть индексы. Для доступа к некоторому элементу массива нам надо знать его индекс. Сама операция получения значения элемента, осуществляется через оператор индексного доступа []. То есть, в нашем случае, primes[0] будет соответствовать первому элементу массива, primes[1] — второму, и т. д. (не забывайте, что индексация производится с нуля).

Сам алгоритм поиска чисел, практически один-в-один повторяет алгоритм, описанный в предыдущем примере, так что подробно мы его описывать не будем. В качестве упраждения на внимательность, вы можете попытаться найти все отличия.

Давайте лучше попробуем проанализировать оба решения и выяснить, какое из решений более оптимально для поставленной задачи. Для того, чтобы ответить на этот вопрос, необходимо прикинуть общее количество операций добавления элементов в массив и сравнить с количеством операций доступа к массиву, или операций выборки.

В нашем алгоритме, мы видим следующее: на каждое число-кандидат, мы вынуждены пробегать все элементы коллекции и выполнять над ними некоторые действия. Поскольку, выборка элементов происходит строго последовательно, особой разницы между массивом и списком тут нет. Операция добавления элементов также происходит строго в конец коллекции и довольно редко. В целом, учитывая произведенные оптимизации (вроде предустановки размера массива), можно заключить что сложности алгоритмов примерно равны.

Не забывайте, что это связано с жестко заданными условиями работы алгоритма! Представьте, если бы нам требовалось реализовать алгоритм, выбирающий элементы из коллекции не последовательно, а некоторым случайным, или почти случайным образом. В случае списка, итераторы нам уже не помогли бы. Пришлось бы опять прибегать к операции последовательного прохождения цепочки для отыскания нужного элемента. В таких условиях, по скорости массив был бы далеко впереди списка. Чуть изменим условия — и все может перевернуться вверх дном. Предположим, что реализуется алгоритм, при котором элементы добавляются не в конец, а в середину коллекции, да еще заранее не известно, какой может быть размер коллекции (так что невыгодно применять resize()). В таких условиях, уже список будет выигрывать у массива.

Получается, что от используемого алгоритма (а так же от четкости поставленных условий), во многом зависит то, насколько эффективен будет тот или иной контейнер. Вот почему при проектировании программ, требуется тщательным образом подходить к вопросу анализа вычислительной сложности алгоритмов и выбирать более подходящие средства для их реализации. Но как всегда, идеальных решений не бывает — выбор будет лежать где то посередине между ресурсоемкостью и производительностью.

[править] Хеши

Хеши являются еще одной формой контейнеров. Подобно массивам и спискам, они могут хранить в себе другие объекты, однако они отличаются и от тех и от других. Для доступа к элементу списка, необходимо использовать итераторы, в то время как для ссылки на элемент массива применяются индексы — числа, которые соответствуют номеру элемента в массиве.

В этом отношении, хеши похожи на массивы, однако, для доступа к элементу используются не индексы, а совершенно произвольные объекты; или если перефразировать наоборот, то: для доступа к некоторому элементу хеша применяются индексы, которые могут быть представлены любым объектом: числом, строкой либо экземпляром пользовательского класса.

Хеши обычно применяются там, где требуется организовать связь нескольких объектов. При этом, первому объекту-индексу, который в хешах называется ключом, ставится в соответствие другой объект — значение. Хеши хранят множество таких пар ключ-значение и, подобно спискам и массивам, предоставляют удобные методы для работы со своим содержимым.

Чаще всего, хеши применяются для связи текстовых строк или для организации ассоциативных массивов, у которых в качестве индекса применяется строка. Приведем несколько примеров применения хешей. Допустим, мы хотим поставить в соответствие названию дня недели его порядковый номер. То есть, строке "понедельник" должно соответствовать число 1, "вторнику" — 2 и так далее. Конечно, эту задачу можно решить и традиционным способом, например с помощью массивов: <source lang=kpp> const weekdays = ['понедельник', 'вторник', 'среда', 'четверг',

                 'пятница', 'суббота', 'воскресенье'];

function int WeekDay2DayNr(const string weekday) {

   var result; //результат (динамическая переменная)
   weekdays.each_pair() { |nr, day| 
       if (day == weekday) { 
           result = nr + 1; 
           break; 
       }
   };
   if (result) //если переменной присвоено значение
       return result; //возвращаем его
   else //иначе, сообщаем об ошибке
       throw e_invalid_call.create('указанная строка не является днем недели');

} </source>

В этом примере, мы заводим массив weekdays, в который помещаем названия всех дней недели.

В функции WeekDay2DayNr() мы перебираем все элементы массива и сравниваем их с контрольной строкой. Если происходит совпадение, то мы сохраняем текущее значение индекса (nr) в динамическую переменную result и прерываем цикл с помощью оператора break.

Далее, с помощью условного оператора проверяется, было ли переменной result присвоено некоторое значение. Если было, то оно возвращается как результат функции; если нет (то есть, оно по прежнему равно null) — генерируется исключение.

Данная функция будет исправно работать, однако в реальных условиях, при большом количестве элементов массива, операция поиска перебором может стать очень медленной. В таком случае, наилучшим решением, будет использование хешей. Перепишем предыдущую функцию так, чтобы она использовала хеш вместо массива: <source lang=kpp> const weekdays = {'понедельник' => 1, 'вторник' => 2, 'среда' => 3,

                 'четверг'     => 4, 'пятница' => 5, 'суббота' => 6, 
                 'воскресенье' => 7};

function int WeekDay2DayNr(const string day) {

   try {
       return weekdays[day];
   } catch (e_range_error e) {
       throw e_invalid_call.create('указанная строка не является днем недели');
   }

} </source>

Посмотрите, насколько проще стал код. А главное, он стал намного быстрее! Хеши позволяют значительно повысить скорость доступа к информации за счет того, что вместо обычного перебора, применяются альтернативные методы. Если говорить кратко, то происходит операция "перемешивания" ключа, которая осуществляется с помощью хеш-функции, в результате которой получается некоторое значение — хеш ключа. Это значение уже используется для выборки искомого объекта. Скорость операции возрастает за счет того, что от медленной операции сравнения ключей, мы переходим к быстрой операции сравнения хешей. Хеши изначально проектируются так, чтобы их было легко сравнивать; в то же время, они должны быть различными для разных значний ключа. Более подробно, про хеши и хеширование, можно почитать на Википедии.

Для объявления хеш-таблицы weekdays применяется специальный синтаксис, встроенный в язык К++: необходимо в фигурных скобрах перечислить пары ключ-значение, отделяя их запятой. Для связи ключа и значения в паре, применяется оператор соответствия (=>). Подобно массивам, объекты хеш-таблиц могут объявляться где угодно в коде, будь то инициализатор переменной, либо фактический параметр в коде вызова функции. В нашем случае, объект создается в инициализаторе константы, которая будет иметь тип hash.

Разумеется, для заполнения хеша можно применять и обычную операцию создания объекта, с последующим вызовом методов insert() для добавления информации в таблицу: <source lang=kpp> var my_config = new hash; my_config.insert('verbosity', 3); my_config.insert('user name', 'nobody'); my_config.insert('password', 'y&5#3Eff_'); //... </source>

Для заполнения хеша можно применять так же оператор индексного доступа: <source lang=kpp> my_config[:path] = 'diss:/etc/myconf'; </source>

Между вызовом метода insert() и использованием оператора []= есть небольшая разница. Она заключается в том, что случае, если в хеше уже присутствует пара значений с тем же ключом, то метод insert() сгенерирует исключение, в то время как оператор []= заменит старое значение на новое. Существует так же метод replace(), который ведет себя подобно вышеозначенному оператору: <source lang=kpp> my_config[:enabled] = 'true'; my_config.replace('enabled', 'true'); </source>

Хеши, подобно массивам и спискам, обладают набором методов для перебора их содержимого, однако смысл некоторых методов немного отличается от своих аналогов в массивах: <source lang=kpp> weekdays.each() { |day, nr| print("key: #{day}, value: #{nr}\n"); }; var keys = weekdays.keys(); keys.each() { |key| println(key); }; weekdays.values().each() { |value| print(value as string + ' '); }; </source>

В этом примере используются три различных метода, которые вызывают блок с парой параметров ключ-значение (метод each()), либо возвращают массивы ключей и значений (методы keys() и values() соответственно). Во второй и третьей строках, показывается способ отображения всех ключей хеша, с помощью метода keys() и промежуточной переменной. В последней строке вызовы методов совмещены в одной конструкции. Для наглядности приведем вывод, каким он должен был бы быть, при выполнении этого кода (подразумевается использование хеша weekdays из предыдущих примеров):

key: понедельник, value: 1
key: вторник, value: 2
key: среда, value: 3
key: четверг, value: 4
key: пятница, value: 5
key: суббота, value: 6
key: воскресенье, value: 7
понедельник
вторник
среда
четверг
пятница
суббота
воскресенье
1 2 3 4 5 6 7

Примечание 1: Здесь мы перечислили выводимые значения по порядку. Однако, на практике такого не случается. За счет операции перемешивания, порядок следования элементов теряется. Поэтому, если требуется сохранить порядок, необходимо либо где-то записывать очредность ключей, либо сортировать их при обработке. Например, код обработки элементов хеша в порядке очередности ключей может выглядеть примерно так: <source lang=kpp> my_hash.keys().sort().each() { |key| print("key: #{key}, value: #{my_hash[key]}\n"); }; </source>

Примечание 2: Как уже было сказано выше, хеши позволяют использовать объекты любого типа как в качестве ключа, так и в качестве значения. Для того, чтобы можно было указывать в качестве ключа объект пользовательского типа, он должен иметь реализацию метода hash(), не принимающего параметров и возвращающего объект класса int. Причем, требуется этот метод требуется экспортировать из модуля, для того чтобы стандартная библиотека смогла его найти. Дополнительно, класс объектов ключа должен предоставлять операторы сравнения и присвоения (== и =). На объекты, содержащиеся в значениях, никаких ограничений не накладывается.

Таким образом, реализация класса ключей должена выглядеть примерно так: <source lang=kpp> class MyClass { public:

   export const function int hash() {
       /* здесь идет код вычисления хеша */
   }

   const operator bool == (const MyClass x) {
       /* код сравнения инстанций */ 
   }
   
   operator MyClass = (const MyClass src) {
       /* код присвоения */ 
       return this;
   }
   /* другие методы */

} </source>

[править] Указатели