Стандартные типы данных — различия между версиями
Korvin (обсуждение | вклад) м (→Массивы и списки) |
Korvin (обсуждение | вклад) (→Массивы и списки) |
||
Строка 314: | Строка 314: | ||
Это случай неудачного стечения обстоятельств, при котором происходит копирование большого количества информации, что естественным образом, сказывается на призводительности всей операции. Из этого можно сделать вывод, что массивы следует применять тогда, когда операции вставки или добавления элементов происходят редко. В случаях, когда необходимо организовывать очереди, где обращение по номеру элемента не требуется, наилучшим решением будет использование списков. | Это случай неудачного стечения обстоятельств, при котором происходит копирование большого количества информации, что естественным образом, сказывается на призводительности всей операции. Из этого можно сделать вывод, что массивы следует применять тогда, когда операции вставки или добавления элементов происходят редко. В случаях, когда необходимо организовывать очереди, где обращение по номеру элемента не требуется, наилучшим решением будет использование списков. | ||
+ | |||
+ | === Применение === | ||
+ | |||
+ | Разобравшись с философией работы массивов и списков, поняв разницу между ними и определившись с областями применения тех и других, мы переходим непосредственно к практике. Массивы и списки в языке К++ представляются классами <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, 'a', 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> | ||
== Хеши == | == Хеши == | ||
== Указатели == | == Указатели == |
Версия 00:12, 26 сентября 2007
В этой главе будут рассмотрены базовые типы данных, применяющиеся в языке К++. Большинство из них объявлены в стандартной библиотеке Gide, однако некоторые, например интервалы, описываются в системной библиотеке самого языка К++. Еще раз напомним Читателю, что в языке К++, стандартные типы данных не являются встроенными. Конечно, компилятор опирается на них при генерации кода, но это совершенно не означает, что их нужно воспринимать как что-то единожды определенное и неизменное. Как уже было показано в книге, как с точки зрения компилятора так и самой виртуальной машины, эти классы ничем не отличаются от обычных, пользовательских классов, когда дело касается их использования на высоком уровне. Если забежать вперед, то можно отметить, что на низком уровне они реализованы на языке C++ (из соображений производительности) и их интерфейсы представлены в стандартной библиотеке. Тем не менее, существует возможность их дополнения программистом-пользователем, что и было проделано в главах, посвященных расширениям. Разумеется, от этих классов возможно наследовать собственные классы, точно так же, как и от любых других. В этой главе мы рассмотрим стандартные типы данных с точки зрения их применения и укажем некоторые свойства которые не были упомянуты в ходе повествования.
Содержание |
Целые числа
Основой всей арифметики являются числа. Для представления чисел в программах применяются классы, объекты которых выступают как хранилища значений. Существует несколько классов целых чисел, различающихся по длине охватываемого ими диапазона и по возможности указания знака:
Имя класса | Нижняя граница | Верхняя граница | Размер в байтах |
---|---|---|---|
int | -2147483648 | 2147483647 | 4 |
uint | 0 | 4294967295 | 4 |
bigint | -9223372036854775808 | 9223372036854775807 | 8 |
ubigint | 0 | 18446744073709551615 | 8 |
Данные классы поддерживают все возможные арифметические операции, а так же имеют операторы преобразования друг в друга, а так же в строку и из строки. Однако, следует быть осторожным и не полагаться полностью на автоматическое приведение типов. В некоторых случаях, можно получить не те результаты, что ожидает программист. Например: <source lang=kpp> var i = 1; var j = "2"; println(i + j); println(j + i); </source>
В приведенном выше примере, объявлены две переменных: целочисленная i и переменная j, содержащая строку "2". При вычислении первой суммы происходит следующее: компилятор "видит", что необходимо посчитать сумму переменных i и j, которые для нас являются представлениями чисел 1 и 2. Но с точки зрения компилятора, это всего лишь две инстанции классов int и string соответственно.
Разбор выражения производится слева-направо, так же как его считает человек. Компилятор пытается найти в классе int оператор + с типом второго операнда, то есть string. Такого оператора в классе нет. Тогда компилятор смотрит, существует ли в классе string оператор приведения к типу int, либо к другому типу, для которого в классе int объявлен оператор +. Такой оператор находится, соответственно компилятор генерирует вызов оператора приведения для переменной j, а затем уже выполняется сам оператор +. Поэтому, сложение происходит численно, так как и ожидалось. Результат суммы будет соответствовать числу 3: <source lang=kpp> i + j = 1 + ("2" as int) = 1 + 2 = 3 </source>
Во втором случае, все происходит с точностью наоборот: первым операндом является строка, то есть инстанция класса string. В этом классе так же объявлен оператор +, но принимающий в качестве второго операнда строку. Этот оператор используется для конкатенации двух строк, при которой вторая строка дописывается в конец первой, то есть: <source lang=kpp> var s1 = "hello"; var s2 = "world"; println(s1 + s2); //результат: "hello" + "world" = "helloworld" </source>
В нашей сумме, вторым операндом является инстанция класса int, которая по вышеописанным правилам, будет приведена к типу string. Таким образом, операция суммы будет приведена к операции конкатенации строк "2" и "1", то есть результат выражения будет "21": <source lang=kpp> j + i = "2" + (1 as string) = "2" + "1" = "21" </source>
Приведенная проблема особенно опасна при использовании динамических переменных, поскольку в одном случае может произойти одна операция, а в другом другая. Поэтому, использовать динамические переменные следует очень осторожно. Если у вас нет уверенности относительно типа передаваемой переменной, лучше подстраховаться и произвести операцию явного преобразования к интересующему вас типу.
Числа с плавающей точкой
Для проведения сложных математических рассчетов, одних целых чисел недостаточно. Для представления действительных чисел, или чисел с плавающей точкой (запятой), как их называют в информатике, в стандартной библиотеке создан класс real, который на низком уровне представлен типом двойной точности (double).
В отличие от класса string, класс real корректно обрабатывается в сочетании с целочисленными классами. Например, следующие выражения дадут одинаковые результаты: <source lang=kpp> var i = 3 + 0.1415 var j = 0.1415 + 3 </source>
В результате, обе переменных будут иметь тип real и значение 3,1415. Это достигается тем, что в целочисленных классах есть специальные версии арифметических операторов, которые принимают в качестве параметра объекты класса real.
Логический тип
В некоторых случаях в программе бывает необходимо сохранять логическое значение. Это может потребоваться в алгоритмах, где такое значение используется в качестве флага, либо в свойствах объектов, которые подразумевают наличие или отсутствие некоторого признака. Это осуществляется с помощью булевых переменных и псевдотипа bool. Переменные булевого типа могут иметь только два значения: true, соответствующее истине и false, соответствующее лжи.
К переменным булевого типа могут приводиться значения более сложных выражений, например когда такое выражение находится в условии цикла. Правила преобразования значений выражений были описаны при рассмотрении условного оператора if.
Примечание: псевдотипом bool назван потому, что он не является классом в полной мере. Это абстракция, которая была введена в язык К++ для преодоления некоторых сложностей при проектировании языка. Переменные такого класса обрабатываются на уровне самого К++; с точки зрения Gide такого класса не существует (вернее, существуют специальные объекты @true и @false, но это тема, требующая отдельного обсуждения).
Существует несколько ограничений, которые важно понимать. Первое ограничение заключается в том, что от этого типа нельзя наследовать собственные классы. Второе ограничение проявляется в том, что переменные типа bool обрабрабатываются особым образом. Если в выражении присутствует переменная булевого типа, то операторы отношения работают немного по другому. Например, следующее выражение будет трактовано как истина: <source lang=kpp> if (0 == true)
//...
</source>
Условие сработает потому что 0 представляет собой действительный, существующий объект, стало быть он истинен (об этом уже было написано). Вот другой пример, иллюстрирующий ту же проблему: <source lang=kpp> var MyClass c = new MyClass; if (c == true)
//...
</source>
Подобное условие так же сработает (будет считаться истинным), поскольку оператор == в данном случае обрабаытвается самим компилятором. Конечно, приведенные примеры являются довольно странными с точки зрения обычного кода, но их все же следует иметь в виду при написании программ.
Строки
Для хранения и обработки строковых данных используется класс string. Он объявлен в стандартной библиотеке Gide и дополнен с помощью расширений в системной библиотеке К++.
В языке К++ предусмотрены два синтаксиса для объявления строковых констант, оба вида строк в конечном счете представляются одним и тем же классом string.
Строки, заключенные в двойные кавычки обрабатывают все escape последовательности, а так же позволяют использовать т. н. вставки, или подстановки — кусочки кода, которые вставляются непосредственно в тело строки и при работе программы заменяются на значение, возвращаемое этим кодом (см. ниже). Обрабатываются следующие последовательности:
Последовательность Значение \n перенос строки \r возврат каретки \t символ табуляции \" символ двойной кавычки \\ символ обратного слеша #{ } подстановка выражения
Подстановки это очень способ совмещать в одном выражении строку которую необходимо вывести и выражения, значение которых необходимо добавить к выводу. Получается что подстановки это что-то среднее между простой строкой и строкой для форматируемого вывода. Подстановка начинается с пары символов #{, которые должны идти друг за другом, без пробелов. То что идет дальше, воспринимается компилятором как выражение, как если бы оно было записано просто в коде, вне строки. Завершает подстановку соответствующая ей закрывающая фигурная скобка.
Приведем пример использования подстановок: <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> Исключением из правила являются последовательности \' и \\.
Класс string предоставляет пользователю широкий спектр различных методов, которые могут использоваться для работы со строками.
Длина строки
Для определения длины строки используется метод length(), который возвращает число символов в строке. Так же, существует метод empty() который возвращает истину если строка пуста и ложь в противном случае.
Выделение подстрок
Для выделения из исходной строки подстрок, разделенных символом или несколькими символвами разделителями, используется метод split(). В качестве параметра, этот метод принимает строку, либо регулярное выражение, соответствующие разделителю. Возвращает метод уже массив из полученных подстрок.
В качестве примера приведем два способа обработки URL строки и выделения из нее отдельных частей: <source lang=kpp> var url = "http://example.com?key1=value1&key2=value2&key3=value3"; var qm = url.find("?"); var args = url.substr(qm, url.length()); var pairs = args.split('&'); var options = new hash; pairs.each() { |pair|
var kv = pair.split('='); options[kv[0]] = kv[1];
}; </source>
С помощью метода find() мы находим позицию символа вопроса в исходной строке, который разделяет адрес на собственно адрес ресурса и на строку параметров запроса. Строка параметров состоит из множества пар значение=результат, отделенных друг от друга символом амперсанда. Выделив подстроку запроса, мы разделяем ее на подстроки с помощью метода split(), указывая амперсанд в качестве разделителя. Полученный массив подстрок мы сохраняем в переменной pairs. Теперь, мы заводим хеш options в который будем записывать параметры запроса, по мере его обработки. Выполняя перебор по всем парам, мы опять разделяем их на две части, на этот раз по символу равенства. Последним действием, полученная пара значение-результат сохраняется в хеше.
Несмотря на то, что вышеприведенный код работает, он является не очень эффективным. В процессе его работы создается много промежуточных переменных и может задействоваться большое количество памяти (при длинных строках запросов). При задачах обработки строк выгодно использовать регулярные выражения. Они позволяют относительно легко производить обработку строк; выполнять поиск и замену по некоторому шаблону. Приведем другой, более элегантный способ решения той же самой задачи, но уже с использованием регулярных выражений: <source lang=kpp> var options = new hash; if (url =~ `\?(.*)$`) {
//разделяем строку на пары значение=результат var pairs = $[1].value.split('&'); //обрабатываем пары по очереди pairs.each() { |pair| if (pair =~ `^([\w\d]+)=([\w\d]+)$`) options[$[1].value] = $[2.value]; };
} </source>
Оператор =~ служит для связи исходной строки с регулярным выражением. В результате, в специальный массив $[] будут помещены все совпадения. Элемент с индексом 0 будет соответствовать всей совпавшей подстроке, в остальных элементах будут находиться совпадения, соответствующие подвыражениям в скобках.
Примечание 1: элементы спецмассива $[] представляют собой не сами подстроки, а объекты-совпадения, класса regexp_match. В этих объектах содержится дополнительная информация о совпадении, например:
- индексы левой и правой границы (свойства left и right)
- длина подстроки (свойство length)
- и, естественно, сама подстрока (свойство value)
Получить доступ к подстроке так же можно, выполнив явное приведение объекта совпадения к типу string. Таким образом, следующие строки функционально эквивалентны: <source lang=kpp> var substr1 = $[1].value; var substr2 = $[1] as string; </source>
Примечание 2: в принципе, можно было и не объявлять отдельную переменную pairs. В книге это было сделано для большей читаемости кода, однако на практике может применяться и более лаконичная форма, которая, тем не менее, остается довольно удобной к восприятию: <source lang=kpp> if (url =~ `\?(.*)$`) {
$[1].value.split('&').each() { |pair| if (pair =~ `^([\w\d]+)=([\w\d]+)$`) options[$[1].value] = $[2.value]; };
} </source>
Объединение строк (конкатенация)
Конкатенация строк осуществляется с помощью обычных арифметических операторов (при этом, приоритеты операций остаются теми же). В зависимости от оператора, действие будет производиться над самим объектом или над его копией: <source lang=kpp> 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; // s1 = "hello world!!!" </source>
Обратите внимание на две последние строки. Оператор *, выполняемый над строкой действительно "умножает" ее, повторяя заданное количество раз.
Операторы индексного доступа
Для доступа к отдельным символам строки может использоваться оператор индексного доступа []. При этом, строка представляется как массив, где каждый элемент соответствует номеру символа в unicode: <source lang=kpp> var str = "hello world"; var ord = str[0]; // ord = 104 </source>
Можно совершать и обратную операцию, а именно присваивать по некоторому индексу числовое значение. Тогда в строке будет стоять символ, соответствующий указанному числу: <source lang=kpp> str[0] = 72; // str = "Hello world" str[6] = 'W'[0]; // str = "Hello World" </source>
Если же требуется получить подстроку исходной строки на основании индексов символов, нужно применять интервалы: <source lang=kpp> var s2 = str[0 .. 4]; // s2 = "Hello" </source>
Возможно так же использовать оператор индексного доступа для присвоения значения отдельным подстрокам. Это осуществляется с помощью оператора []=: <source lang=kpp> var greeting = "Welcome to the real world, Neo."; greeting['real world'] = 'matrix'; // Welcome to the matrix, Neo. greeting[15 .. 20] = 'Deeptown'; // Welcome to the Deeptown, Neo. greeting[-1] = '!'[0]; // Welcome to the Deeptown, Neo! greeting[`\sNeo.$`] = 'Leonid!'; // Welcome to the Deeptown, Leonid! </source>
В примере выше, применены четыре способа индексного доступа для изменения строки, соответствующие четырем различным операторам (точнее, четырем версиям перегруженного оператора). В первом случае используется доступ по подстроке. При этом подстрока будет "вырезана" из строки, а на ее место будет вставлена присваиваемая строка. Таким образом, эта операция не зависит от размера искомой и заменяемой подстрок (если заменяемая строка длиннее, исходная строка будет "раздвинута").
Во втором случае осуществляется доступ по интервалу. Символы с индексами в диапазоне 15-20 соответствуют слову "matrix". Замена опять же производится по правилу "вырезания" подстроки с последующим "склеиванием".
В третьем случае, используются отрицательные индексы, для указания того, что отсчитывать символы нужно с конца строки. Так, -1 соответствует последнему символу, -2 второму с конца и т. д.
Наконец, в последней замене применяется регулярное выражение, для поиска подстроки.
Примечание: Методы замены через оператор []= на деле являются обертками к соответствующим реализациям метода replace_all(). При этом, будут производиться замены всех включений подстроки в исходную строку (разумеется, кроме случаев ин тервала и одиночного индекса). Если вы хотите заменить только одно включение, — используйте методы replace().
Интервалы
В некоторых случаях бывает необходимо передать в качестве параметра не отдельное значение а диапазон. Для указания диапазона обычно достаточно указать только его границы. Это может осуществляться с помощью класса interval. К++ предоставляет специальный синтаксис для указания интервалов с помощью оператора ".."; как уже было показано выше, это может применяться для выборки подстрок, соответствующих заданному диапазону индексов, либо подмассивов по тому же принципу: <source lang=kpp> var s = "abcdef"[0..2]; // "abc" var a = [1, 2, 3, 4][1..-1]; // [2, 3, 4] </source>
Вообще, интервалы могут быть не только численными. В качестве объектов, формирующих интервал, могут выступать любые два объекта, имеющие одинаковые типы: <source lang=kpp> var left = MyClass.Create(5), right = MyClass.Create(10); var i = interval.create(left, right); var alpahbet = 'a' .. 'z'; </source>
Интервалы могут использоваться как виртуальные массивы, то есть к ним можно обращаться как к массиву, запрашивая некоторый элемент по индексу. И он будет возвращен, как будто действительно хранится в массиве (на сама деле, он создается в момент обращения по некоторому известному закону): <source lang=kpp> var numbers = 1 .. 100; var alpahbet = 'a' .. 'z'; var x = numbers[50]; // x = 1 + (50-1) = 50. var y = alphabet[10]; // y = ('a'.ord + (10-1)).char = 'k' </source>
Преимуществом такого подхода является то, что не нужно хранить весь массив в памяти. Зная закон изменения элементов, можно получить любой элемент, зная базу (одну из границ) и индекс элемента.
Подобно массивам, интервалы так же обладают методом each(), позволяющем проходить по всему массиву, выполняя некоторый блок с параметром текущего элемента массива: <source lang=kpp> var s = 0; //здесь будет сумма var numbers = 1 .. 100; numbers.each() { |x| s += x; }; </source>
Для выяснения принадлежности некоторого объекта к интервалу могут применяться метод contains() или соответствующий ему оператор in: <source lang=kpp> var numbers = 1 .. 100; var lowercase = 'a' .. 'z'; var x = numbers.contains(75) ? "yes" : "no"; //x = "yes" var y = 'X' in lowercase ? "yes" : "no"; //y = "no" </source>
Для создания интервалов на базе собственных классов необходимо перегрузить конструктор, а так же соответствующие методы, своими реализациями.
Массивы и списки
Для хранения наборов объектов применяются массивы и списки. И те и другие являются контейнерами, то есть, их объекты способны хранить в себе другие объекты и обладают соответствующими методами для добавления в них элементов и их извлечения. Разница между массивом и списком заключается в том, что массив хранит элементы в одной цельной области памяти, в то время как список организует их в виде цепочки связанных друг с другом элементов:
У каждого из этих контейнеров есть свои преимущества и недостатки. Постараемся рассмотреть основные операции, осуществляемые с контейнерами и выяснить, в каких случаях предпочтительнее использовать массив, а в каких список.
Доступ к данным
Массивы обладают высокой скоростью доступа к информации, поскольку все данные находятся в одном месте и структурированы. То есть, доступ есть сразу ко всем элементам, поэтому не приходится двигаться вдоль массива для поиска нужного элемента. Списки работают несколко по другому. Для того, чтобы обратиться к некоторому элементу списка, необходимо пройти всю цепочку от начала до требуемого элемента (см. рисунок выше). Поэтому, списки значительно уступают по скорости доступа массивам. В случаях, когда содержимое контейнера меняется относительно редко, но присутствует большое количество обращений к данным, следует применять массивы.
Добавление элементов
Рассмотрим операцию добавления элементов в список. Предположим, что нам надо добавить элемент N в список, между вторым и третьим его элементами. Для выполнения этой операции, нам необходимо всего лишь "разорвать" цепочку в нужном месте и изменить указатель у предыдущего элемента X2 так, чтобы он указывал на новый элемент N. Для того, чтобы продолжить цепочку, элемент N должен указывать на следующий элемент списка, то есть на X3:
Операция добавления к началу или к хвосту списка так же не составляет труда, и сводится все к той же работе с указателями. Удаление элементов производится обратным образом: элемент удаляется, а указатель предыдущего элемента меняется так, чтобы он указывал на последующий за удаляемым элемент.
В случае массивов все усложняется. Как уже было сказано выше, массивы хранят элементы в монолитных областях памяти, следовательно, чтобы добавить или удалить элемент, приходится задействовать весь массив. Если места в текущей области памяти, занятой массивом недостаточно, чтобы вместить еще один элемент, то произойдет выделение нового блока памяти, с последующим копированием всех существующих элементов массисва в новый блок.
Операция выделения производится "с запасом", то есть размер нового блока будет больше чем размер занимаемый всеми элементами, причем зависимость тут экспоненциальная: чем больеше будет добавляться элементов в массив, тем больше будет размер выделяемого блока памяти. Это делается для того, чтобы минимизировать риск полного копирования. Тем не менее, такое может случиться (а при операции вставки — случается обязательно), что в итоге может привести к значительной задержке.
Рассмотрим тот же случай, что и в случае со списком, а именно, операцию вставки нового элемента между вторым и третьим элементами массива. Для выполнения этой операции создается новый массив, с размером, достаточным для помещения всех предыдущих элементов, а так же нового элемента. Далее, происходит копирование нового элемента, а так же старых элементов на соответствующие места:
Это случай неудачного стечения обстоятельств, при котором происходит копирование большого количества информации, что естественным образом, сказывается на призводительности всей операции. Из этого можно сделать вывод, что массивы следует применять тогда, когда операции вставки или добавления элементов происходят редко. В случаях, когда необходимо организовывать очереди, где обращение по номеру элемента не требуется, наилучшим решением будет использование списков.
Применение
Разобравшись с философией работы массивов и списков, поняв разницу между ними и определившись с областями применения тех и других, мы переходим непосредственно к практике. Массивы и списки в языке К++ представляются классами array и list соответственно. Оба класса имеют похожие наборы методов, так что дважды изучать похожие сущности не придется.
Объявление массива реализуется с помощью специального синтаксиса, встроенного в язык К++. Это может осуществляться как в инициализаторе переменной, так и в любом другом выражении, вплоть до фактического параметра в коде вызова функции или даже для указания значения по умолчанию для него.
Для того, чтобы объявить массив, необходимо перечислить его элементы, заключив их в квадратные скобки и отделяя друг от друга запятой: <source lang=kpp> var my_array = [1, 2, 3]; </source>
В качестве элементов массива могут быть указаны любые объекты: числа, строки, экземпляры классов, блоки и даже вложенные массивы с хешами — массиву все равно что хранить, поскольку все что он делает, это хранит объекты не вдаваясь в подробности, какие именно: <source lang=kpp> var myobject = new MyClass; var object_dump = [1, 3.14, 'a', myobject, {|x| return x + 1;},
{'a' => 1, 'b' => 2 }, [1,2,3], true, 10 .. 20];
</source>
Можно сказать, что массив представляет собой реализацию абстрактного упорядоченного хранилища данных с возможностью произвольного доступа.
Специального синтаксиса для создания списков нет, поскольку большинство задач которые решают списки не предполагают инициализации значениями. Если же это все таки потребовалось, на помощь придут массивы. Вот небольшой пример того как можно занести в список значения из массива, создаваемого компилятором автоматически: <source lang=kpp> var my_list = new list; [1, 2, 3].each() { |x| my_list.push(x); }; </source>
В этом примере показываются сразу два важных метода, которые являются одними из самых частых по использованию (если вы внимательно читали книгу, то наверняка это заметили). Метод each() используется для перебора всего содержимого коллекции (массива списка или интервала) и вызова переданного в качестве параметра блока, передавая ему на каждой итерации значение текущего элемента. Таким образом, в случае нашего массива, блок будет вызыван три раза, с параметрами, соответственно, 1, 2 и 3. Метод push() присутствует как в массивах, так и в списках, и служит для добавления элемента в конец коллекции. Здесь он применяется для добавления текущего элемента массива в список. Получается, что по выполнении этой процедуры, список будет содержать в себе все элементы, присутствующие в массиве (в том же порядке).
Существуют еще несколько методов, похожих на метод each(), но отличающихся передаваемыми в блок параметрами. Например each_index() вызывает блок, передавая ему текущий индекс, а метод each_pair() передает ему текущий индекс и элемент. За неимением индекса, списки два последних метода не реализуют. Переделаем немного предыдущий пример и покажем использование этих методов: <source lang=kpp> var my_array = [1, 2, 3]; var my_list = new list; my_array.each() { |x| my_list.push(x); };
my_list.each() { |x| print("#{x}\n"); }; my_array.each_pair() { |i, e| print("my_array[#{i}] = #{e}\n"); }; </source>