Deeptown Manual - Вклад участника [ru]

Функции

2010-02-19T15:50:08Z

Kamillen: /* Экспортирование функций */

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

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

== Объявление ==

Объявление любой функции начинается с указания ключевого слова <tt>'''function'''</tt> следом за которым указывается тип возвращаемого значения, после которого идет [[идентификатор]] имени функции. Указание типа можно опустить, тогда будет подразумеваться, что функция возвращает [[Переменные#Нетипированные (динамические) переменные|переменную динамического типа]]. После указания имени функции идет блок описания ''параметров'', или ''аргументов'' функции. Блок заключается в круглые скобки; сами параметры, в ходе описания отделяются друг от друга запятой. Завершает конструкцию ''тело функции'', которое записывается в фигурных скобках.

Вот примеры объявления функций:
<source lang="kpp">
function MyFunction() { return 5; }
function Compare(x, y) { return x < y; }
</source>

Первая функция не принимает параметров, но возвращает числовую константу 5. Согласитесь, не очень полезный код. Вторая функция немного "поумнее": она принимает два объекта и пытается их сравнить, используя оператор отношения "меньше". Результатом выполнения такой функции будет логическое значение "истина", если ''x'' и вправду меньше чем ''y'', либо ложь в противном случае. Для правильной работы этой функции требуется, чтобы передаваемые параметры допускали возможность сравнения (то есть, были бы определены соответствующие [[Выражения#Операторы|операторы]]). Если этого нет, — будет сгенерировано [[Идеология языка#Понятие исключения|исключение]], то есть ошибка времени исполнения. Поскольку типы параметров никак не указаны, компилятор не имеет возможности контролировать фактические типы передаваемых параметров, а следовательно не может предупредить программиста если по его мнению что-то не так. Тем не менее, это обеспечивает программиста возможностью написания гибких программ и функций, которые не зависят от конкретных типов передаваемых данных.

Несмотря на простоту последней функции, подобный код может с успехом применяться в реальных программах. Пример такого кода будет приведен при описании [[Блоки|блоков]], чуть дальше по ходу книги.

== Аргументы ==

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

=== Типизация аргументов ===

Если функция подразумевает передачу параметров строго определенного типа, то применяется расширенная форма записи аргументов. При этом, идентификатор имени параметра предворяется именем типа, который следует принимать. Например, вышеописанную функцию <tt>Compare()</tt> мы можем переписать так, чтобы она принимала в качестве параметров только объекты, представляющие собой целые числа. При этом, имена переменных ''x'' и ''y'' мы дополняем сведениями о типе:

<source lang="kpp">
function Compare(int x, int y) { return x < y; }
</source>

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

В общем случае, в описании функции можно указывать параметры любых типов, и даже смешивать типированные и нетипированные параметры:

<source lang="kpp">
function MyFunction(int p1, string p2, block p3) { /* тело функции */ }
function OtherFunction(MyClass p1, p2) { /* тело функции */ }
</source>

Как видно из кода, функция <tt>MyFunction()</tt> имеет три параметра: [[Стандартные типы данных#Целые числа|целочисленный]] ''p1'', [[Стандартные типы данных#Строки|строковый]] ''p2'' и [[Блоки|блок]] ''p3''.

Функция <tt>OtherFunction()</tt>, в качестве параметров может принимать экземпляры класса <tt>MyClass</tt> (параметр ''p1''), и объекты любого типа в качестве параметра ''p2''. '''Обратите внимание''', что может показаться, что тип <tt>MyClass </tt> указан для обоих аргументов, но на самом деле это не так. Тип привязывается только к переменной, указанной сразу после него. Более подробно, эта проблема рассмотрена в главе [[Объявление переменных и констант]].

Приведем несколько примеров вызова функции с различными наборами параметров:
<source lang="kpp" line="1">
var myblock = { |x| x += 2; };
MyFunction(10, "hello", myblock); //верно, типы фактических параметров совпадают
MyFunction("20", 10, myblock); //частично верно, выполняется операция приведения
MyFunction([1,2,3], myblock, 5); //неверно. переданы неприводимые типы

var o1 = new MyClass;
var o2 = new OtherClass;
OtherFunction(o1, o2);
OtherFunction(o2, o1);
OtherFunction(o1, o1);
OtherFunction(o2, o2);
</source>

;1: Мы создаем экземпляр переменной-[[Блоки|блока]], который будет передаватсья в качестве параметра функциям. Здесь он не имеет особого значения, так что на него можно практически не обращать внимания (важен только его тип).

;2-4: Производятся вызовы функции <tt>MyFunction()</tt> с различными наборами параметров. В первом вызове типы фактических параметров точно совпадают с типами в описании функции, следовательно никакого приведения не происходит и все работает как есть. Во втором вызове происходит приведение строковой константы "20" к числу, а числа 10 к строке. "Частично" верна эта конструкция потому, что на момент компиляции невозможно определить, сработает ли первая операция приведения (строки к числу) или нет. Если строка содержит нецифровые символы, то в результате операции приведения будет сгенерировано [[Идеология языка#Понятие исключения|исключение]]. Разумеется в данном случае, все будет хорошо. Второе приведение, а именно числа 20 к строке так же выполнится успешно, потому что абсолютно любое число можно представить в виде строки символов, соответствующих цифрам числа.

: Третий вызов функции <tt>MyFunction()</tt> является совершенно неверным, поскольку все фактические параметры переданные в функцию, являются неприводимыми к соответствующим типам формальных параметров.

;6-11: Здесь создаются две инстанции классов <tt>MyClass</tt> и некоторого класса <tt>OtherClass</tt>. Далее выполняется вызов функции <tt>OtherFunction()</tt>, которой в разных комбинациях передаются вышесозданные объекты. В качестве упражнения, Читателю предлагается самому решить, какие из вызовов верные а какие нет.

: Постарайтесь ответить на следующие вопросы:
:* Какие из вызовов приведут к ошибке времени компиляции?
:* Какие из вызовов приведут к [[Идеология языка#Понятие исключения|исключению]] (ошибке времени исполнения)?
:* Что изменится, если реализовать оператор приведения типа <tt>MyClass</tt> к <tt>OtherClass</tt>?
:* Что изменится, если реализовать оператор приведения типа <tt>OtherClass</tt> к <tt>MyClass</tt>?
:* Что изменится, если типы будут взаимноприводимыми?

=== Инициализаторы аргументов (значения по умолчанию) ===

В некоторых случаях может возникнуть необходимость задания параметров функции по умолчанию, либо возможность указания только части параметров. Например, функция может иметь обширный список аргументов, большая часть которых обычно не используется. То есть, они влияют на некоторые очень специфичные свойства объекта, которые редко применяются. Если такую функцию описывать традиционным образом, то получится что программист, использующий ее в своей программе, должен будет каждый раз писать что-то вроде:
<source lang="kpp">
var x = SomeWierdFunction(1, "a", 0, 0, 0, 0, 0, 0);
...
var y = SomeWierdFunction(2, "b", 0, 0, 0, 0, 0, 0);
...
</source>

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

Приведем более приближенный к реальности пример. Допустим, программист решил написать свою реализацию некоторого класса контейнера, служащего для содержания других объектов. Предположим так же, что данный класс подобно [[Стандартные типы данных#Массивы и списки|массиву]] позволяет обратиться к своим элементам через индекс и имеет некоторое свойство, показывающее текущий размер коллекции. Программист желает написать функцию, возвращающую некоторое подмножество данной коллекции, расположенное между верхним и нижним индексами. Логично предположить, что может возникнуть желание указать только один из индексов, в то время как другой должен подставиться как граница коллекции с соответствующей стороны. То есть, в случае нижнего индекса, граничное значение будет равно нулю, в то время как граничное значение для верхнего индекса заранее не определено. Фактически, оно равно количеству размещенных в коллекции элементов минус один (если нумерация ведется с нуля). Разумеется, это число меняется по мере добавления и удаления элементов. Если бы инициализаторов не существовало, программисту приходилось бы каждый раз явно указывать верхнюю границу выборки на основании его представления о текущем количестве элементов в коллекции (еще одно потенциальное место для ошибки). Это по меньшей мере неудобно. По большей — невозможно, ведь не всегда заранее известно, какое количество элементов содержится в коллекции в данный момент. В общем, с учетом существования инициализаторов, интерфейс класса коллекции мог бы выглядеть примерно так:

<source lang="kpp">
class MyCollection {
public function int Add(...); //добавление элемента
private function GetLength(); // размер коллекции
property length read GetLength;
const function MyCollection SubCollection(int from = 0, int to = this.length - 1);
}
</source>

В первой строке объявляется метод добавления элемента в массив. Для удобства применения класса, он оформлен в виде функции с переменным списком аргументов (см. ниже). Если говорить коротко, то это функция, которая может принимать различное (сколь угодно большое) количество параметров в зависимости от вызова. При этом, они не описываются в заголовке функции, а вместо них ставится ''оператор-многоточие'' (<tt>...</tt>). Это необходимо, чтобы отличить такую функцию от обычной функции. При вызове, фактические параметры автоматически добавляются в массив, который можно использовать внутри функции.

Далее следуют аксессор, возвращающий текущее количество элементов в коллекции и свойство, связанное с ним.

Последняя строка как раз представляет для нас интерес. Как видно из описания, метод <tt>SubCollection()</tt> возвращает некоторе подмножество класса, которое само является экземпляром данного класса; границы выборки задаются двумя параметрами: нижним индексом ''from'' и верхним ''to''. Аргументы, соответственно, инициализированы нулем и выражением доступа к свойству <tt>length</tt>, которое будет возвращать значение верхнего индекса. Поскольку в выражении есть ссылка на текущий экземпляр (<tt>'''this'''</tt>), то значение выражения будет зависеть от того, метод какого экземпляра вызывается в каждом конкретном случае.

Вот пример некоторого участка программы, использующей вышеописанный класс:
<source lang="kpp">
var c = new MyCollection;
MyCollection.Add(1, "a", [2], { |x| x + 1; }, { 1 => 'a', 2 => 'b'});
var sub1 = c.SubCollection();
var sub2 = c.SubCollection(3);
var sub3 = c.SubCollection(1, 4);
</source>

=== Модификаторы и копирование ===

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

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

:[[Изображение:DMX.png]] 

Приведем пример функции, реализующей эту формулу:
<source lang="kpp" line="1">
function real AOD(array values, array probs) {
if (values.size != probs.size) //проверка исходных данных
throw "массивы должны иметь одинаковое количество элементов";

var real M; //счетчик и накопитель для величины математического ожидания
for (var i = 0; i < values.size; ++i)
M += values[i] * probs[i];
return M;
}
</source>

;1-2: Для того чтобы значение можно было рассчитать, размеры исходных массивов должны совпадать. Если они не совпадают, то генерируется [[Идеология языка#Понятие исключения|исключение]] с соответствующим сообщением об ошибке.

;4: Здесь мы объявляем переменную счетчик, которая будет использоваться в цикле и переменную, накапливающую сумму, то есть конечную величину математического ожидания.

;5-8: Для рассчета значения применяется цикл <tt>'''for'''</tt>, который перебирает переменную-счетчик ''i'' начиная с нуля и заканчивая последним индексом массивов. Тело цикла представляет собой вышеописанную формулу. Результат возвращается с помощью оператора <tt>'''return'''</tt>.

Теперь, если мы создадим два массива и заполним их некоторыми значениями, то мы сможем вычислить для них значение математического ожидания:
<source lang="kpp">
var v = [-3, -2, -1, 0, 1, 2, 3 ]; //значения
var p = [0.01, 0.05, 0.2, 0.3, 0.35, 0.05, 0.04]; //вероятности
var avg = AOD(v, p);
</source>

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

Таким образом, в вышеприведенном примере при вызове функции <tt>AOD()</tt>, будет произведено копирование двух переданных массивов, а значит и всех их элементов. Естественно, чем больше размеры массивов, тем больший объем данных приходится копировать. На практике, статистические массивы могут иметь тысячи и даже десятки тысяч значений!

Чтобы решить эту проблему, мы должны указать компилятору, что объекты параметров копировать не нужно. Мы, в свою очередь "обещаем" не изменять их значения, так что вызывающий код будет "спокоен", что с переданными объектами ничего не случится. Это осуществляется с помощью ключевого слова-спецификатора <tt>'''const'''</tt>, которое указывается в блоке описания параметров непосредственно перед самим параметром. Оно указывает, что данный параметр не будет изменяться в функции, что позволит компилятору произвести соответствующую оптимизацию. При этом, внутрь функции будет передан сам объект, точнее ссылка на него. Разумеется, компилятор так же следит за тем, чтобы в коде функции не было попыток изменить значение такого параметра, а если это все же случится, — будет сгенерирована ошибка времени компиляции.

Перепишем вышеприведенный пример с использованием спецификаторов <tt>'''const'''</tt>:
<source lang="kpp">
function real AOD(const array values, const array probs) {
if (values.size != probs.size) //проверка исходных данных
throw "массивы должны иметь одинаковое количество элементов";

var real M; //счетчик и накопитель для величины математического ожидания
for (var i = 0; i < values.size; ++i)
M += values[i] * probs[i];
return M;
}
</source>

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

Но что если нам необходимо решить прямо противоположную задачу? А именно, передать в функцию некоторый объект, для его изменения внутри функции. Если просто написать код вида:
<source lang="kpp">
function mutate(int x) {
puts("x = #{x}"); // вывод: x = 5
x = 10;
puts("x = #{x}"); // вывод: x = 10
}
...
var v = 5;
mutate(v);
puts("v = #{v}"); // вывод: v = 5
</source>
...то ничего не получится. Да, переменная ''v'' будет передана внутрь функции <tt>mutate()</tt>. Но при передаче параметра произойдет его копирование. Таким образом, внутри функции будет изменено значение копии, которая будет уничтожена при выходе из функции. Изначальная переменная как была установлена, так и осталась равной пяти.

Чтобы указать компилятору, что в функцию следует передавать сам объект, а не его копию — следует указать ключевое слово-спецификатор <tt>'''var'''</tt> (по аналогии с <tt>'''const'''</tt>). При этом, копироваться аргумент не будет но будет возможно его изменение в теле функции:

<source lang="kpp">
function mutate(var int x) {
puts("x = #{x}"); // вывод: x = 5
x = 10;
puts("x = #{x}"); // вывод: x = 10
}
...
var v = 5;
mutate(v);
puts("v = #{v}"); // вывод: v = 10
</source>

=== Функции с переменным списком аргументов ===

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

Пользователь vpupkin (501) обращался к файлу '~/docs/index.txt' 122 раз(а).

Данная строка содержит как чисто текстовую информацию, так и значения, которые мы должны "внедрить" в текст. "Лобовое" решение проблемы может выглядеть примерно так:

<source lang="kpp">
var myfile = '~/docs/index.txt'; //имя файла
var fstat = File.stat(myfile); //получение информации о файле
var uname = 'vpupkin'; //имя пользователя
var userid = 501; //системный идентификатор пользователя
print("Пользователь " + uname + "(" + userid +
") обращался к файлу '" + myfile + "' " +
fstat.times_accessed(userid) + " раз(а).\n");
</source>

Согласитесь, функция вывода выглядит не очень привлекательно. Она изобилует операторами конкатенации строк и прочей информацией, которая разбросана по всему вызову. Попробуем ее переписать с помощью ''оператора-вставки'' (см. главу [[Стандартные типы данных#Строки|Стандартные типы данных]]):

<source lang="kpp">
print("Пользователь #{uname} (#{userid}) обращался к файлу #{myfile} " +
"#{fstat.times_accessed(userid)} раз(а).\n");
</source>

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

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

Пользователь % (%d) обращался к файлу '%' %d раз(а).\n
User % (%d) accessed file '%' %d times.\n

Каждый символ <tt>%</tt> соответствует одному значению переменной из последующего списка. При разборе (форматировании) такой строки, каждый символ <tt>%</tt> будет замещен на значение соответствующей переменной. Для вывода самого символа % применяется escape последовательность из двух подряд идущих символов <tt>%%</tt>. Пара символов <tt>%d</tt> в случае строки форматирования, означает необходимость выполнения приведения типа числа к строке.

Таким образом, в функцию форматирования необходимо передать как минимуму один параметр — формат. Дальнейшие параметры и их количество будут зависеть уже от самой строки формата. Но как это описать в терминах языка программирования? Одним из решений может быть передача в функцию [[Стандартные типы данных#Массивы и списки|массива]] с параметрами. Тогда, код описания функции форматируемого вывода и ее вызова может выглядеть так:

<source lang="kpp">
function printf(const string format, const array args);
//...
printf("Пользователь % (%d) обращался к файлу '%' %d раз(а).\n",
[uname, userid, myfile, fstat.times_accessed(userid)]);
</source>

Для вывода результирующей строки, ищутся вхождения символов <tt>%</tt> (с возможными спецификаторами, как в случае с <tt>%d</tt>) в строке формата и подставлять значение текущего элемента массива. После подстановки, текущим элементом становится следующий элемент массива.

Более красивое решение заключается в использовании ''оператора-многоточие'' (<tt>...</tt>) в объявлении функции, который указывет, что функция должна принимать переменное количество аргументов:

<source lang="kpp">
function printf(const string format, ...);
//...
printf("Пользователь % (%d) обращался к файлу '%' %d раз(а).\n",
uname, userid, myfile, fstat.times_accessed(userid));
</source>

Теперь, код вызова такой функции ничем не отличается от вызова любой другой функции или метода. Программисту не нужно помнить об особенностях функции — нужно просто записывать параметры один за одним. Обладая всей необходимой информацией, компилятор языка сам сформирует массив передаваемых параметров, который будет передан в функцию. Для разбора аргументов внутри функции используется специальный метод <tt>args()</tt>, возвращающий массив аргументов.

'''Примечание 1:''' на самом деле, приведенная в примерах функция <tt>printf()</tt>, реализована как расширение класса <tt>[[Стандартные типы данных#Строки|string]]</tt> стандартной билбиотеки языка К++. Желающие реализовать форматируемый вывод могут ее использовать. Здесь же она была приведена, как наиболее подходящий пример функции с переменным списком аргументов.

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

Реально из всей этой кучи, могут использоваться 2-3 параметра, в то время как остальные остаются по умолчанию. Проблема заключается в том, что не всегда возможно описать параметры так чтобы необходимые значения возможно было передавать по порядку. Если же требуется задействовать параметр из конца списка, придется указывать и промежуточные параметры, устанавливая их значения в <tt>'''null'''</tt>. Это засоряет код и может привести к ошибкам.

Решением этой ситуации может послужить использование [[Стандартные типы данных#Хеши|хешей]] для передачи только тех параметров, которые необходимы. Тогда наша функция объявляется таким образом:
<source lang="kpp">
function connect(const hash params);
</source>

В теле функции мы работаем с хешем ''params'' доставая из него значения по мере необходимости. При отсутствии некоторой записи в хеше, считается что необходимо использовать значение по умолчанию.

Вызов такого метода может осуществляться либо традиционным образом, когда хеш создается за пределами метода, а последнему передается сама переменная, либо с помощью специального синтаксиса:
<source lang="kpp">
var params = { :address => 'www.deeptown.org',
:port => 1234, :login => 'guest' };
connect(params); //традиционный способ вызова
connect(:address => 'www.deeptown.org', :timeout => 20); //альтернативный
</source>

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

== Возврат значения ==

Для выхода из функции применяется оператор <tt>'''return'''</tt>, после которого указывается выражение, значение которого необходимо вернуть в качестве значения функции. Если функция ничего не возвращает, то есть тип результата определен как <tt>void</tt>, то выражение результата не указывается. Если тип возвоащаемого значения не указан, то подразумевается что функция возвращает [[Переменные#Нетипированные (динамические) переменные|нетипированную переменную]]; если тип указан явно, то при возврате значения, тип результата выражения будет приведен к типу результата. Если типы неприводимы, то будет сгенерирована ошибка времени компиляции.

Приведем примеры объявления функций с различными типами возвращаемых значений и прокомментируем каждый из случаев:
<source lang="kpp">
function F1(int x) {
if (x > 5)
return "hello world";
else
return x;
}
function string F2() { return 10; }
function void F3() { return; }
</source>

Первая функция возвращает переменную [[Переменные#Нетипированные (динамические) переменные|динамического типа]], которая может быть либо строкой, либо числом в зависимости от значения аргумента. Вторая функция возвращает строку, но в качестве выражения в операторе <tt>'''return'''</tt> указана константа типа <tt>[[Стандартные типы данных#Целые числа|int]]</tt>, поэтому будет выполнена операция приведения. Третья функция не возвращает результата, поэтому оператор <tt>'''return'''</tt> записан без выражения.

== Локальные переменные ==

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

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

=== Объявление ===

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

=== Область видимости ===

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

Ниже приведен пример некоторой функции, в которой рассмотрены типовые ситуации, возникающие при работе с локальными переменными. В качестве упражнения, постарайтесь ответить на вопрос, какими будут значения переменных на момент вызова функции <tt>print()</tt> в каждом из случаев. Записывайте ваши ответы по ходу разбора листинга, а затем сравните их с [[Ответы к упражнению (область видимости)|контрольными ответами]].

<source lang="kpp" line="1">
function f(const int p) {
var x = 1, k = 2;
print("x = #{x}, k = #{k}\n"); //(1)

{
x = 5;
var k = 3;
print("x = #{x}, k = #{k}\n"); //(2)
}
print("x = #{x}, k = #{k}\n"); //(3)

if (p > 5) {
print("x = #{x}\n"); //(4)
} else {
var x = 10;
var y = "hello";
print("x = #{x}, #{y}\n"); //(5)
x = 6;
}
print("x = #{x}\n"); //(6)
print("#{y}"); //(7)
}
</source>

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



== Экспортирование функций ==

Изначально, платформа и [[виртуальная машина Gide]] была разработана для свободного взаимодействия любого количества gide-совместимых языков программирования, которые могли бы свободно использоваться при написании программ. Причем, модуль написанный на одном языке программирования может импортировать другие модули, написанные на других языках. Одним из способов обеспечения совместимости языков является введение стандартного [[Gide IDL|языка описания интерфейсов]] модулей, который должны понимать языки, подразумевающие совместную работу в рамках системы.

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

В языке К++ введено специальное ключевое слово <tt>'''export'''</tt>, которое позволяет отменить декорацию имени для отдельно взятой функции. Зная имя функции, ее можно будет вызывать из внешнего кода (имеется в виду внешний по отношению к gide код, например код некоторого плагина).

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

Экспортирование функций применяется при объявлении точек входа в программу. Для программ, такой точкой является функция <tt>main()</tt>:
<source lang="kpp">
export function void main() {
/* тело функции */
}
</source>

После загрузки программы в память, происходит поиск функции с именем "main" которой передается управление.

== Перегрузка функций и операторов ==

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

<source lang="kpp" line="1">
class MyClass {
public operator MyClass + (x) {
switch (x.className) {
case 'std/int': { /* MyClass + int */ }
case 'std/string': { /* MyClass + string */ }
default: { /* MyClass + (x as MyClass) */ }
}
}
}
</source>

;3: Объявляется оператор <tt>+</tt>, принимающий в качестве параметра динамическую переменную.
;4: В коде оператора реализуется множественный выбор на основании класса переданного фактического параметра
;5-7: Определяются возможные случаи для поддерживаемых типов. Первый будет вызываться, если в качестве параметра передана строковая переменная, второй — если это число. Выбор по умолчанию будет соответствовать общему случаю, когда передан неизвестный тип. Здесь можно либо попытаться выполнить операцию явного приведения типа к самому <tt>MyClass</tt>, либо к одному из поддерживаемых; либо сразу бросить исключение.

<hr>

При разработаке интерфейсов классов, часто бывает необходимо предоставить возможность выполнения одних и тех же операций с различными типами исходных данных. Например, класс пользовательского хранилища данных должен обладать методами добавления (импортирования) элементов из стандартных хранилищ, вроде [[Стандартные типы данных#Массивы и списки|массивов и списков]]. Точно так же, он должен предоставлять интерфейс экспортирования данных в стандартные типы. Если интерфейс будет реализован с учетом только одного из типов, то теоретически программа все же сможет работать (поскольку, типы <tt>array</tt> и <tt>list</tt> являются взаимоприводимыми). На практике, эта операция может привести к значительным потерям производительности, связанным в основном с многократным копированием содержимого при операции приведения.

Решение может заключаться в реализации нескольких методов для импортирования и экспортирования данных в определенных форматах:
<source lang="kpp">
class MyCollection {
public:
function Add(const x); //добавление одиночного элемента
function AddArray(const array a); //добавление массива
function AddList(const list l); //добавление списка
function AddCSV(const string s, //добавление строки с разделителем
const string separator = ",");
function Insert(const x, const int pos = 0); //вставка одиночного элемента
function InsertArray(const array a, const int pos = 0); //вставка массива
function InsertList(const list l, const int pos = 0); //вставка списка
function InsertCSV(const string s, //вставка строки с разделителем
const int pos = 0, const string separator = ",");
const function array ExportArray(); //экспортирование в массив
const function list ExportList(); //экспортирование в список
const function string ExportCSV(); //экспортирование в строку
}
</source>

Теперь, при использовании такого класса, программисту придется для каждой операции применять функцию, рассчитанную на данный тип параметров:
<source lang="kpp">
var col = new MyCollection;
col.Add("hello world");
col.AddArray([1, 2, 3]);
var l = new list;
foreach (1 .. 10) { |x| l.push(x); };
col.AddList(l);
col.AddCSV("волк,коза,капуста");
//(код вставки и экспортирования пишется по аналогии)
</source>

С одной стороны, вроде бы код довольно читаем и красив, но с другой, — есть одна маленькая неприятность. Допустим, программист написал некоторую функцию или даже целый класс, которые часто работают с инстанциями контейнера <tt>MyCollection</tt> и со списками, которые импортируются в контейнер. Предположим, что однажды было решено, для повышения быстродействия использовать массивы вместо списков. В коде интерфейсов это изменение может затронуть всего пару строк, в то время как код функции придется переписывать, заменяя все вызовы <tt>AddList()</tt> и <tt>InsertList()</tt> на соответствующие им вызовы: <tt>AddArray()</tt> и <tt>InsertArray()</tt>. Если в коде функции существует только одна сущность представленная списком, то достаточно сделать замену в тексте одной подстроки на другую. Но что если их много? Придется проходить код строка за строкой и проверять каждый вызов — благодатная почва для ошибок. Конечно, кому-то может показаться, что приведенный пример "притянут за уши", однако такая проблема на самом деле имеет место, просто довольно сложно придумать навскидку подходящую ситуацию.

Как вы уже могли догадаться, наиболее рациональное решение заключается в использовании ''перегруженных функций''. Перегруженными, называются функции или методы, которые имеют одинаковые имена, но различные списки параметров. Вот примеры перегруженных функций:
<source lang="kpp">
function Hello(int x); //1
function Hello(int x, real y); //2
function Hello(string x = "the value"); //3
function Hello(array a, list l, hash h); //4
</source>
Все вышеприведенные функции могут быть с успехом объявлены в одной области: либо как глобальные функции, либо в пределах класса — как методы. Как видите, имена всех функций одинаковы, а отличаются они лишь списком параметров. Отличия могут быть как в количестве параметров, так и в их типах.

При вызове такого метода, первым делом проверяется количество фактически передаваемых параметров и их типы. На основании этой информации компилятор решает, какой же из методов необходимо использовать в каждом конкретном случае. Если, к примеру, пользователь вызвал функцию как <tt>Hello(1)</tt>, то очевидно что имелся в виду метод номер 1. Вызов <tt>Hello(1, 2)</tt> будет соответствовать методу номер 2. Несмотря на то что тип второго фактического параметра это <tt>int</tt>, компилятор все равно разберется, поскольку это единственный из методов, принимающий два параметра. Конечно, при генерации вызова будет выполнена операция приведения типа для второго параметра к типу <tt>real</tt>. Наконец, вызов метода <tt>Hello()</tt> без параметров будет соответствовать методу номер 3, поскольку в описании присутствует инициализатор.

Аналогичным образом перегружаются и операторы.

=== Особенности применения ===

При использовании перегрузки функций существует несколько ограничений, которые нужно иметь в виду при написании интерфейсов и программ. Перегружать функции и методы на основании типа их возвращаемого значения нельзя. Это невозможно по нескольким причинам. Во-первых, подобная практика привела бы к написанию плохого кода, который очень трудно отлаживать при возникновении каких либо проблем. Во-вторых, и это самое главное, существуют ситуации, когда компилятор не может решить какую из функций необходимо выбрать, например такое может случиться при использовании [[Переменные#Нетипированные (динамические) переменные|динамических переменных]]:
<source lang="kpp">
function int f() { return 1; }
function string f() { return "hello"; }

function caller() {
var x; //динамическая переменная
x = f(); //какую из функций вызвать?!
}
</source>
В приведенном примере выражение <tt>x = f();</tt> не может быть корректно разобрано, поскольку компилятору не на что равняться при выборе конкретной реализации функции. Даже если бы мы использовали явное приведение типов в выражении (<tt>x = f() as int</tt>), то компиляция все равно была бы неуспешной, поскольку с точки зрения компилятора эта операция должна выполняться уже после самого вызова функции.

Та же проблема возникает и в случае передачи динамической переменной в перегруженную функцию:
<source lang="kpp">
function f(int x) { return x; }
function f(string s) { return x; }

function caller() {
var x; //динамическая переменная
f(x); //какую из функций вызвать?!
}
</source>
Написание подобного кода ведет к ошибке времени компиляции. Однако, такая проблема возникает только при одинаковом количестве неинициализированных параметров в перегруженных функциях.

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

Разрешение вышеописанной ситуации для функций сводится к принудительной типизации переменной:
<source lang="kpp">
function caller() {
var x;
f(x to int);
}
</source>

=== Применение перегрузки в расширениях ===

Еще одним аргументом в пользу перегруженных методов, является возможность их применения в [[Классы и объекты#Расширения|расширениях]]. Например, программист может расширить функциональность некотрого системного класса, добавляя возможность передачи своего класса в качестве аргумента методам. При этом, он добавляет метод, имеющий то же имя (но другой набор параметров), что и метод, существующий в расширяемом классе.

При расширении сторонних классов следует быть особенно внимательным и не забывать, что правила декорирования имен методов в других языках могут быть различными, либо декорирование может не применяться вовсе. К примеру, в случае [[Стандартная библиотека Gide|стандартной библиотеки]], применять расширения можно смело, но нельзя их помечать как <tt>'''export'''</tt>.

Стандартные типы данных

2009-12-15T17:01:42Z

Kamillen: /* Применение */

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

== Целые числа ==

Основой всей арифметики являются числа. Для представления чисел в программах применяются классы, объекты которых выступают как хранилища значений. В стандартной библиотеке, это класс <tt>int</tt>, умеющий хранить числа в диапазоне от -9223372036854775808 до 9223372036854775807 (64 битное целое со знаком).

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

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

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

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

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

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

== Числа с плавающей точкой ==

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

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

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

== Логический тип ==

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

К переменным булевого типа могут приводиться значения более сложных выражений, например когда такое выражение находится в условии цикла. Правила преобразования значений выражений были описаны при рассмотрении [[Основные синтаксические конструкции#Оператор if|условного оператора <tt>'''if'''</tt>]].

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

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

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

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

== Строки ==

Для хранения и обработки строковых данных используется класс <tt>string</tt>. Он объявлен в [[Стандартная библиотека Gide|стандартной библиотеке Gide]] и дополнен с помощью [[Классы и объекты#Расширения|расширений]] в системной библиотеке К++.

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

Строки, заключенные в двойные кавычки обрабатывают все escape последовательности, а так же позволяют использовать т. н. вставки, или подстановки — кусочки кода, которые вставляются непосредственно в тело строки и при работе программы заменяются на значение, возвращаемое этим кодом (см. ниже). Обрабатываются следующие последовательности:
::{|
! Последовательность || Значение
|-
| <tt>'''\n'''</tt> || перенос строки
|-
| <tt>'''\r'''</tt> || возврат каретки
|-
| <tt>'''\t'''</tt> || символ табуляции
|-
| <tt>'''\"'''</tt> || символ двойной кавычки
|-
| <tt>'''\\'''</tt> || символ обратного слеша
|-
| <tt>'''#{ }'''</tt> || подстановка выражения
|}

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

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

Приведем пример использования подстановок:
<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>
Исключением из правила являются последовательности '''<tt><nowiki>\'</nowiki></tt>''' и <tt>'''\\'''</tt>.

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

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

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

=== Длина строки ===

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

=== Выделение подстрок ===

Для выделения из исходной строки подстрок, разделенных символом или несколькими символвами разделителями, используется метод <tt>split()</tt>. В качестве параметра, этот метод принимает строку, либо [[Введение, или краткий обзор#Регулярные выражения|регулярное выражение]], соответствующие разделителю. Возвращает метод уже массив из полученных подстрок.

В качестве примера приведем два способа обработки 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>

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

Несмотря на то, что вышеприведенный код работает, он является не очень эффективным. В процессе его работы создается много промежуточных переменных и может задействоваться большое количество памяти (при длинных строках запросов). При задачах обработки строк выгодно использовать регулярные выражения. Они позволяют относительно легко производить обработку строк; выполнять поиск и замену по некоторому шаблону. Приведем другой, более элегантный способ решения той же самой задачи, но уже с использованием регулярных выражений:
<source lang=kpp>
var options = new hash;
if (url =~ `\?(.*)$`) {
//разделяем строку на пары значение=результат
var pairs = $[0].value.split('&');
//обрабатываем пары по очереди
pairs.each() { |pair|
if (pair =~ `^([\w\d]+)=([\w\d]+)$`)
options[$[1].value] = $[2].value;
};
}
</source>

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

'''Примечание 1:''' элементы спецмассива <tt>$[]</tt> представляют собой не сами подстроки, а объекты-совпадения, класса <tt>regexp_match</tt>. В этих объектах содержится дополнительная информация о совпадении, например:
* индексы левой и правой границы (свойства <tt>left</tt> и <tt>right</tt>)
* длина подстроки (свойство <tt>length</tt>)
* и, естественно, сама подстрока (свойство <tt>value</tt>)

Получить доступ к подстроке так же можно, выполнив явное приведение объекта совпадения к типу <tt>string</tt>. Таким образом, следующие строки функционально эквивалентны:
<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>

При желании, можно еще больше упростить код, используя версию оператора <tt>[]</tt>, принимающую регулярное выражение в качестве параметра и возвращающее соответствующую ему подстроку:
<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>

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

=== Операторы индексного доступа ===

Для доступа к отдельным символам строки может использоваться оператор индексного доступа <tt>[]</tt>. При этом, строка представляется как [[Стандартные типы данных#Массивы и списки|массив]], где каждый элемент соответствует '''номеру символа''' в 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>

Возможно так же использовать оператор индексного доступа для присвоения значения отдельным подстрокам. Это осуществляется с помощью оператора <tt>[]=</tt>:
<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 второму с конца и т. д.

Наконец, в последней замене применяется [[Введение, или краткий обзор#Регулярные выражения|регулярное выражение]], для поиска подстроки.

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

== Интервалы ==

В некоторых случаях бывает необходимо передать в качестве параметра не отдельное значение а диапазон. Для указания диапазона обычно достаточно указать только его границы. Это может осуществляться с помощью класса <tt>interval</tt>. К++ предоставляет специальный синтаксис для указания интервалов с помощью оператора "<tt>..</tt>"; как уже было показано выше, это может применяться для выборки подстрок, соответствующих заданному диапазону индексов, либо подмассивов по тому же принципу:
<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>

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

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

Для выяснения принадлежности некоторого объекта к интервалу могут применяться метод <tt>contains()</tt> или соответствующий ему оператор <tt>'''in'''</tt>:
<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>

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

== Массивы и списки ==

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

[[Изображение:Array_vs_list.png|center]]

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

=== Доступ к данным ===

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

=== Добавление элементов ===

Рассмотрим операцию добавления элементов в список. Предположим, что нам надо добавить элемент N в список, между вторым и третьим его элементами. Для выполнения этой операции, нам необходимо всего лишь "разорвать" цепочку в нужном месте и изменить указатель у предыдущего элемента X2 так, чтобы он указывал на новый элемент N. Для того, чтобы продолжить цепочку, элемент N должен указывать на следующий элемент списка, то есть на X3:
[[Изображение:List insert.png|center]]

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

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

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

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

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

=== Применение ===

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

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

Для того, чтобы объявить массив, необходимо перечислить его элементы, заключив их в квадратные скобки и отделив друг от друга запятой:
<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>

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

Существуют еще несколько методов, похожих на метод <tt>each()</tt>, но отличающихся передаваемыми в блок параметрами. Например <tt>each_index()</tt> вызывает блок, передавая ему текущий индекс, а метод <tt>each_pair()</tt> передает ему текущий индекс и элемент. За неимением индекса, списки два последних метода не реализуют. Переделаем немного предыдущий пример и покажем использование этих методов:
<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>

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

<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() + ']'; // s_list = "[1, 2, 3]"
//дальнейшая работа с s_list (например, вывод на экран)
</source>

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

<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 ресурсов, а затем полученный список записывается в ''поток''. Класс потока это абстракция, предоставляемая ядром Диптауна для доступа к различным ресурсам. Все что необходимо сделать чтобы использовать потоки, это создать инстанцию класса <tt>stream</tt> с момощью конструктора <tt>create()</tt>, указав требуемый URL потока и задать режим доступа к ресурсу (с помощью констант класса). При этом, на пользовательском уровне, требуется только писать в поток и читать из него; пользователь не должен беспокоиться, каким образом будет происходить реальная работа с данными на низком уровне — этим занимается ядро. Если же ядро не поддерживает конкретный тип потока — будет сгенерировано исключение.

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

В заключение, приведем две реализации кода, вычисляющего первую сотню простых чисел. Одну реализацию мы напишем с использованием списков, а другую с помощью массивов. В нижеприведенном коде активно применяются циклы, так что, для лучшего понимания материала, Читателю предлагается забежать вперед и [[Основные синтаксические конструкции#Циклы|ознакомиться]] с ними. Итак, первая реализация:
<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), то число не является простым. Следовательно проверять его дальше не имеет смысла. Мы прекращаем цикл с помощью оператора <tt>'''break'''</tt> и сбрасываем флаг ''is_prime''. Если после перебора всех множителей, флаг остался установленным, то это значит, что текущее число (переменная ''x'') является и вправду простым: его мы помещаем в конец списка. Так продолжается до тех пор, пока в списке не окажится 100 элементов. Для проверки размера списка (условие [[Основные синтаксические конструкции#Цикл while|цикла <tt>'''while'''</tt>]] в строке 4) применяется метод <tt>size()</tt>.

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

Для перебора списка применяется [[Основные синтаксические конструкции#Цикл for|цикл <tt>'''for'''</tt>]]. В инициализаторе цикла была создана управляющая переменная ''p'', которая и является инстанцией итератора (класса <tt>list_iterator</tt>). Список имеет специальный метод <tt>begin()</tt>, который создает инстанцию итератора и устанавливает ее на свое начало.

Метод <tt>end()</tt> возвращает значение специального итератора, который всегда указывает на конец списка. Его нельзя двигать, и служит он только для одной цели — для проверки граничных условий. Важно понимать, что под концом списка понимается не последний его элемент, а именно конец — нечто, следующее за конечным элементом. Таким образом, условие в цикле <tt>'''for'''</tt> проверяет, есть ли еще элементы "справа" от итератора ''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 элементов), мы можем выделить всю необходимую память одним махом. Это будет намного быстрее, чем выделять память по мере итераций, ведь копирование элементов массива в новое место будет произведено всего один раз. Для изменения размера массива применяется метод <tt>resize()</tt>. В качестве аргумента метод принимает число — размер массива, который мы желаем получить. Если желаемый размер меньше текущего, то массив будет урезан до нового размера (элементы, оказавшиеся "за бортом", будут выброшены). Если больше — массив будет расширен, причем все старые элементы останутся невредимыми на своих местах, а новые примут значение <tt>'''null'''</tt>.

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

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

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

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

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

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

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

== Хеши ==

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

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

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

Чаще всего, хеши применяются для связи текстовых строк или для организации ''ассоциативных массивов'', у которых в качестве индекса применяется строка. Приведем несколько примеров применения хешей. Допустим, мы хотим поставить в соответствие названию дня недели его порядковый номер. То есть, строке "понедельник" должно соответствовать число 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 EInvalidCall.create('указанная строка не является днем недели');
}
</source>

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

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

Далее, с помощью условного оператора проверяется, было ли переменной ''result'' присвоено некоторое значение. Если было, то оно возвращается как результат функции; если нет (то есть, оно по прежнему равно <tt>'''null'''</tt>) — генерируется [[Идеология языка#Понятие исключения|исключение]].

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

function int WeekDay2DayNr(const string day) {
try {
return weekdays[day];
} catch (ERangeError e) {
throw EInvalidCall.create('указанная строка не является днем недели');
}
}
</source>

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

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

Разумеется, для заполнения хеша можно применять и обычную операцию создания объекта, с последующим вызовом методов <tt>insert()</tt> для добавления информации в таблицу:
<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>

Между вызовом метода <tt>insert()</tt> и использованием оператора <tt>[]=</tt> есть небольшая разница. Она заключается в том, что случае, если в хеше уже присутствует пара значений с тем же ключом, то метод <tt>insert()</tt> сгенерирует [[Идеология языка#Понятие исключения|исключение]], в то время как оператор <tt>[]=</tt> заменит старое значение на новое. Существует так же метод <tt>replace()</tt>, который ведет себя подобно вышеозначенному оператору:
<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>

В этом примере используются три различных метода, которые вызывают блок с парой параметров ключ-значение (метод <tt>each()</tt>), либо возвращают массивы ключей и значений (методы <tt>keys()</tt> и <tt>values()</tt> соответственно). Во второй и третьей строках, показывается способ отображения всех ключей хеша, с помощью метода <tt>keys()</tt> и промежуточной переменной. В последней строке вызовы методов совмещены в одной конструкции. Для наглядности приведем вывод, каким он должен был бы быть, при выполнении этого кода (подразумевается использование хеша ''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:''' Как уже было сказано выше, хеши позволяют использовать объекты любого типа как в качестве ключа, так и в качестве значения. Для того, чтобы можно было указывать в качестве ключа объект пользовательского типа, он должен иметь реализацию метода <tt>hash()</tt>, не принимающего параметров и возвращающего объект класса <tt>int</tt>. Дополнительно, класс объектов ключа должен предоставлять операторы сравнения и присвоения (<tt>==</tt> и <tt>=</tt>). На объекты, содержащиеся в значениях, никаких ограничений не накладывается.

Таким образом, реализация класса ключей должена выглядеть примерно так:
<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>

== Указатели ==

Стандартные типы данных

2009-10-28T20:22:03Z

Kamillen: /* Хеши */

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

== Целые числа ==

Основой всей арифметики являются числа. Для представления чисел в программах применяются классы, объекты которых выступают как хранилища значений. В стандартной библиотеке, это класс <tt>int</tt>, умеющий хранить числа в диапазоне от -9223372036854775808 до 9223372036854775807 (64 битное целое со знаком).

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

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

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

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

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

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

== Числа с плавающей точкой ==

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

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

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

== Логический тип ==

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

К переменным булевого типа могут приводиться значения более сложных выражений, например когда такое выражение находится в условии цикла. Правила преобразования значений выражений были описаны при рассмотрении [[Основные синтаксические конструкции#Оператор if|условного оператора <tt>'''if'''</tt>]].

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

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

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

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

== Строки ==

Для хранения и обработки строковых данных используется класс <tt>string</tt>. Он объявлен в [[Стандартная библиотека Gide|стандартной библиотеке Gide]] и дополнен с помощью [[Классы и объекты#Расширения|расширений]] в системной библиотеке К++.

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

Строки, заключенные в двойные кавычки обрабатывают все escape последовательности, а так же позволяют использовать т. н. вставки, или подстановки — кусочки кода, которые вставляются непосредственно в тело строки и при работе программы заменяются на значение, возвращаемое этим кодом (см. ниже). Обрабатываются следующие последовательности:
::{|
! Последовательность || Значение
|-
| <tt>'''\n'''</tt> || перенос строки
|-
| <tt>'''\r'''</tt> || возврат каретки
|-
| <tt>'''\t'''</tt> || символ табуляции
|-
| <tt>'''\"'''</tt> || символ двойной кавычки
|-
| <tt>'''\\'''</tt> || символ обратного слеша
|-
| <tt>'''#{ }'''</tt> || подстановка выражения
|}

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

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

Приведем пример использования подстановок:
<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>
Исключением из правила являются последовательности '''<tt><nowiki>\'</nowiki></tt>''' и <tt>'''\\'''</tt>.

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

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

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

=== Длина строки ===

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

=== Выделение подстрок ===

Для выделения из исходной строки подстрок, разделенных символом или несколькими символвами разделителями, используется метод <tt>split()</tt>. В качестве параметра, этот метод принимает строку, либо [[Введение, или краткий обзор#Регулярные выражения|регулярное выражение]], соответствующие разделителю. Возвращает метод уже массив из полученных подстрок.

В качестве примера приведем два способа обработки 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>

С помощью метода <tt>find()</tt> мы находим позицию символа вопроса в исходной строке, который разделяет адрес на собственно адрес ресурса и на строку параметров запроса. Строка параметров состоит из множества пар ''значение''<tt>=</tt>''результат'', отделенных друг от друга символом амперсанда. Выделив подстроку запроса, мы разделяем ее на подстроки с помощью метода <tt>split()</tt>, указывая амперсанд в качестве разделителя. Полученный массив подстрок мы сохраняем в переменной ''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>

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

'''Примечание 1:''' элементы спецмассива <tt>$[]</tt> представляют собой не сами подстроки, а объекты-совпадения, класса <tt>regexp_match</tt>. В этих объектах содержится дополнительная информация о совпадении, например:
* индексы левой и правой границы (свойства <tt>left</tt> и <tt>right</tt>)
* длина подстроки (свойство <tt>length</tt>)
* и, естественно, сама подстрока (свойство <tt>value</tt>)

Получить доступ к подстроке так же можно, выполнив явное приведение объекта совпадения к типу <tt>string</tt>. Таким образом, следующие строки функционально эквивалентны:
<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>

При желании, можно еще больше упростить код, используя версию оператора <tt>[]</tt>, принимающую регулярное выражение в качестве параметра и возвращающее соответствующую ему подстроку:
<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>

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

=== Операторы индексного доступа ===

Для доступа к отдельным символам строки может использоваться оператор индексного доступа <tt>[]</tt>. При этом, строка представляется как [[Стандартные типы данных#Массивы и списки|массив]], где каждый элемент соответствует '''номеру символа''' в 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>

Возможно так же использовать оператор индексного доступа для присвоения значения отдельным подстрокам. Это осуществляется с помощью оператора <tt>[]=</tt>:
<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 второму с конца и т. д.

Наконец, в последней замене применяется [[Введение, или краткий обзор#Регулярные выражения|регулярное выражение]], для поиска подстроки.

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

== Интервалы ==

В некоторых случаях бывает необходимо передать в качестве параметра не отдельное значение а диапазон. Для указания диапазона обычно достаточно указать только его границы. Это может осуществляться с помощью класса <tt>interval</tt>. К++ предоставляет специальный синтаксис для указания интервалов с помощью оператора "<tt>..</tt>"; как уже было показано выше, это может применяться для выборки подстрок, соответствующих заданному диапазону индексов, либо подмассивов по тому же принципу:
<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>

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

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

Для выяснения принадлежности некоторого объекта к интервалу могут применяться метод <tt>contains()</tt> или соответствующий ему оператор <tt>'''in'''</tt>:
<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>

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

== Массивы и списки ==

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

[[Изображение:Array_vs_list.png|center]]

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

=== Доступ к данным ===

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

=== Добавление элементов ===

Рассмотрим операцию добавления элементов в список. Предположим, что нам надо добавить элемент N в список, между вторым и третьим его элементами. Для выполнения этой операции, нам необходимо всего лишь "разорвать" цепочку в нужном месте и изменить указатель у предыдущего элемента X2 так, чтобы он указывал на новый элемент N. Для того, чтобы продолжить цепочку, элемент N должен указывать на следующий элемент списка, то есть на X3:
[[Изображение:List insert.png|center]]

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

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

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

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

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

=== Применение ===

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

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

Для того, чтобы объявить массив, необходимо перечислить его элементы, заключив их в квадратные скобки и отделив друг от друга запятой:
<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>

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

Существуют еще несколько методов, похожих на метод <tt>each()</tt>, но отличающихся передаваемыми в блок параметрами. Например <tt>each_index()</tt> вызывает блок, передавая ему текущий индекс, а метод <tt>each_pair()</tt> передает ему текущий индекс и элемент. За неимением индекса, списки два последних метода не реализуют. Переделаем немного предыдущий пример и покажем использование этих методов:
<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>

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

<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>

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

<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 ресурсов, а затем полученный список записывается в ''поток''. Класс потока это абстракция, предоставляемая ядром Диптауна для доступа к различным ресурсам. Все что необходимо сделать чтобы использовать потоки, это создать инстанцию класса <tt>stream</tt> с момощью конструктора <tt>create()</tt>, указав требуемый URL потока и задать режим доступа к ресурсу (с помощью констант класса). При этом, на пользовательском уровне, требуется только писать в поток и читать из него; пользователь не должен беспокоиться, каким образом будет происходить реальная работа с данными на низком уровне — этим занимается ядро. Если же ядро не поддерживает конкретный тип потока — будет сгенерировано исключение.

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

В заключение, приведем две реализации кода, вычисляющего первую сотню простых чисел. Одну реализацию мы напишем с использованием списков, а другую с помощью массивов. В нижеприведенном коде активно применяются циклы, так что, для лучшего понимания материала, Читателю предлагается забежать вперед и [[Основные синтаксические конструкции#Циклы|ознакомиться]] с ними. Итак, первая реализация:
<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), то число не является простым. Следовательно проверять его дальше не имеет смысла. Мы прекращаем цикл с помощью оператора <tt>'''break'''</tt> и сбрасываем флаг ''is_prime''. Если после перебора всех множителей, флаг остался установленным, то это значит, что текущее число (переменная ''x'') является и вправду простым: его мы помещаем в конец списка. Так продолжается до тех пор, пока в списке не окажится 100 элементов. Для проверки размера списка (условие [[Основные синтаксические конструкции#Цикл while|цикла <tt>'''while'''</tt>]] в строке 4) применяется метод <tt>size()</tt>.

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

Для перебора списка применяется [[Основные синтаксические конструкции#Цикл for|цикл <tt>'''for'''</tt>]]. В инициализаторе цикла была создана управляющая переменная ''p'', которая и является инстанцией итератора (класса <tt>list_iterator</tt>). Список имеет специальный метод <tt>begin()</tt>, который создает инстанцию итератора и устанавливает ее на свое начало.

Метод <tt>end()</tt> возвращает значение специального итератора, который всегда указывает на конец списка. Его нельзя двигать, и служит он только для одной цели — для проверки граничных условий. Важно понимать, что под концом списка понимается не последний его элемент, а именно конец — нечто, следующее за конечным элементом. Таким образом, условие в цикле <tt>'''for'''</tt> проверяет, есть ли еще элементы "справа" от итератора ''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 элементов), мы можем выделить всю необходимую память одним махом. Это будет намного быстрее, чем выделять память по мере итераций, ведь копирование элементов массива в новое место будет произведено всего один раз. Для изменения размера массива применяется метод <tt>resize()</tt>. В качестве аргумента метод принимает число — размер массива, который мы желаем получить. Если желаемый размер меньше текущего, то массив будет урезан до нового размера (элементы, оказавшиеся "за бортом", будут выброшены). Если больше — массив будет расширен, причем все старые элементы останутся невредимыми на своих местах, а новые примут значение <tt>'''null'''</tt>.

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

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

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

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

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

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

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

== Хеши ==

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

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

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

Чаще всего, хеши применяются для связи текстовых строк или для организации ''ассоциативных массивов'', у которых в качестве индекса применяется строка. Приведем несколько примеров применения хешей. Допустим, мы хотим поставить в соответствие названию дня недели его порядковый номер. То есть, строке "понедельник" должно соответствовать число 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 EInvalidCall.create('указанная строка не является днем недели');
}
</source>

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

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

Далее, с помощью условного оператора проверяется, было ли переменной ''result'' присвоено некоторое значение. Если было, то оно возвращается как результат функции; если нет (то есть, оно по прежнему равно <tt>'''null'''</tt>) — генерируется [[Идеология языка#Понятие исключения|исключение]].

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

function int WeekDay2DayNr(const string day) {
try {
return weekdays[day];
} catch (ERangeError e) {
throw EInvalidCall.create('указанная строка не является днем недели');
}
}
</source>

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

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

Разумеется, для заполнения хеша можно применять и обычную операцию создания объекта, с последующим вызовом методов <tt>insert()</tt> для добавления информации в таблицу:
<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>

Между вызовом метода <tt>insert()</tt> и использованием оператора <tt>[]=</tt> есть небольшая разница. Она заключается в том, что случае, если в хеше уже присутствует пара значений с тем же ключом, то метод <tt>insert()</tt> сгенерирует [[Идеология языка#Понятие исключения|исключение]], в то время как оператор <tt>[]=</tt> заменит старое значение на новое. Существует так же метод <tt>replace()</tt>, который ведет себя подобно вышеозначенному оператору:
<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>

В этом примере используются три различных метода, которые вызывают блок с парой параметров ключ-значение (метод <tt>each()</tt>), либо возвращают массивы ключей и значений (методы <tt>keys()</tt> и <tt>values()</tt> соответственно). Во второй и третьей строках, показывается способ отображения всех ключей хеша, с помощью метода <tt>keys()</tt> и промежуточной переменной. В последней строке вызовы методов совмещены в одной конструкции. Для наглядности приведем вывод, каким он должен был бы быть, при выполнении этого кода (подразумевается использование хеша ''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:''' Как уже было сказано выше, хеши позволяют использовать объекты любого типа как в качестве ключа, так и в качестве значения. Для того, чтобы можно было указывать в качестве ключа объект пользовательского типа, он должен иметь реализацию метода <tt>hash()</tt>, не принимающего параметров и возвращающего объект класса <tt>int</tt>. Дополнительно, класс объектов ключа должен предоставлять операторы сравнения и присвоения (<tt>==</tt> и <tt>=</tt>). На объекты, содержащиеся в значениях, никаких ограничений не накладывается.

Таким образом, реализация класса ключей должена выглядеть примерно так:
<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>

== Указатели ==