Содержание
· 1 МАССИВЫ
o 1.1 Особенности массивов
o 1.2 Массив как объект
o 1.3 Возврат массива
o 1.4 Многомерные массивы
o 1.5 Массивы и параметризация
o 1.6 Создание тестовых данных
o 1.7 Генераторы данных
o 1.8 Создание массивов с использованием генераторов
o 1.9 Вспомогательный инструментарий Arrays
§ 1.9.1 Копирование массива
§ 1.9.2 Сравнение массивов
§ 1.9.3 Сравнение элементов массивов
§ 1.9.4 Сортировка массива
§ 1.9.5 Поиск в отсортированном массиве
o 1.10 Резюме
В конце главы 5 было показано, как определить и инициализировать массив. Программист создает и инициализирует массивы, извлекает из них элементы по целочисленным индексам, а размер массива остается неизменным. Как правило, при работе с массивами этого вполне достаточно, но иногда приходится выполнять более сложные операции, а также оценивать эффективность массива по сравнению с другими контейнерами. В этой главе массивы рассматриваются на более глубоком уровне.
Особенности массивов
В Java существует немало разных способов хранения объектов, почему же массивы занимают особое место?
Массивы отличаются от других контейнеров по трем показателям: эффективность, типизация и возможность хранения примитивов. Массивы Java являются самым эффективным средством хранения и произвольного доступа к последовательности ссылок на объекты. Массив представляет собой простую линейную последовательность, благодаря чему обращения к элементам осуществляются чрезвычайно быстро. За скорость приходится расплачиваться тем, что размер объекта массива фиксируется и не может изменяться на протяжении его жизненного цикла. Как говорилось в главе 11, контейнер ArrayList способен автоматически выделять, дополнительное пространство, выделяя новый блок памяти и перемещая в него все ссылки из старого. Хотя обычно ArrayList отдается предпочтение перед массивами, за гибкость приходится расплачиваться, и ArrayList значительно уступает по эффективности обычному массиву.
И массивы, и контейнеры защищены от возможных злоупотреблений. При выходе за границу массива или контейнера происходит исключение RuntimeException, свидетельствующее об ошибке программиста.
До появления параметризации другим контейнерным классам приходилось работать с объектами так, как если бы они не имели определенного типа. Иначе говоря, объекты рассматривались как принадлежащие к типу Object, корневому для всей иерархии классов в Java. Массивы удобнее «старых» контейнеров тем, что массив создается для хранения конкретного типа. Проверка типов на стадии компиляции не позволит использовать неверный тип или неверно интерпретировать извлекаемый тип. Конечно, Java так или иначе запретит отправить неподходящее сообщение объекту на стадии компиляции или выполнения, так что ни один из способов не является более рискованным по сравнению с другим. Просто будет удобнее, если компилятор укажет на существующую проблему, и снижается вероятность того, что пользователь программы получит неожиданное исключение.
Массив может содержать примитивные типы, а «старые» контейнеры — нет. С другой стороны, параметризованные контейнеры могут проверять тип хранимых объектов, а благодаря автоматической упаковке они работают так, как если бы поддерживали хранение примитивов, поскольку преобразование выполняется автоматически. В следующем примере массивы сравниваются с параметризованными контейнерами:
//: arrays/ContainerComparison.java
import java.util.*;
import static net.mindview.util.Print.*;
class BerylliumSphere {
private static long counter;
private final long id = counter++;
public String toString() { return "Sphere " + id; }
}
public class ContainerComparison {
public static void main(String[] args) {
BerylliumSphere[] spheres = new BerylliumSphere[10];
</spoiler> Оба способа хранения объектов обеспечивают проверку типов, а единственное очевидное различие заключается в том, что массивы используют для обращения к элементам конструкцию [ ], a List — методы вроде add() или get(). Разработчики языка намеренно сделали массивы и ArrayList настолько похожими, чтобы программисту было концептуально проще переключаться между ними. Но, как было показано в главе 11, контейнеры обладают более широкими возможностями, чем массивы. С появлением механизма автоматической упаковки контейнеры по удобству работы с примитивами почти не уступают массивам. Единственным реальным преимуществом массивов остается их эффективность. Впрочем, при решении более общих проблем может оказаться, что возможности массивов слишком ограничены, и тогда приходится пользоваться контейнерными классами.
Массив как объект
С каким бы типом массива вы ни работали, идентификатор массива в действительности представляет собой ссылку на объект, созданный в динамической памяти. Этот объект содержит ссылки на другие объекты и создается либо неявно (в синтаксисе инициализации массива), либо явно конструкцией new. Одной из частей объекта массива (а по сути, единственным доступным полем) является доступная только для чтения переменная length, которая указывает, сколько элементов может храниться в объекте массива. Весь доступ к объекту массива ограничивается синтаксисом [ ]. Следующий пример демонстрирует различные способы инициализации массивов и присваивания ссылок на массивы. Он также наглядно показывает, что массивы объектов и массивы примитивных типов практически идентичны. Единственное различие заключается в том, что массивы объектов содержат ссылки, а массивы примитивов содержат сами примитивные значения.
//: arrays/ArrayOptions.java
// Инициализация и повторное присваивание массивов
// Ссылки в массиве автоматически инициализируются null:
print("b: " + Arrays.toString(b));
BerylliumSphere[] c = new BerylliumSphere[4];
for(int i = 0; i < c.length; i++)
if(c[i] == null) // Проверка ссылки на действительность
c[i] = new BerylliumSphere();
// Агрегатная инициализация:
BerylliumSphere[] d = { new BerylliumSphere(),
new BerylliumSphere(), new BerylliumSphere()
};
// Динамическая агрегатная инициализация:
a = new BerylliumSphere[]{
new BerylliumSphere(), new BerylliumSphere(),
};
// (Завершающая запятая не обязательна в обоих случаях)
print("a.length = " + a.length);
print("b.length = " + b.length);
print("c.length = " + c.length);
print("d.length = " + d.length);
a = d;
print("a.length = " + a.length);
// Массивы примитивов:
int[] e; // Ссылка null
int[] f = new int[5];
// Примитивы в массиве автоматически инициализируются нулями:
print("f: " + Arrays.toString(f));
int[] g = new int[4];
for(int i = 0; i < g.length; i++)
g[i] = i*i;
int[] h = { 11, 47, 93 };
// Ошибка компиляции переменная e не инициализирована:
//!print("e.length = " + e.length);
print("f.length = " + f.length);
print("g.length = " + g.length);
print("h.length = " + h.length);
e = h;
print("e.length = " + e.length);
e = new int[]{ 1, 2 };
print("e.length = " + e.length);
}
}
<spoiler text="Output:">
b: [null, null, null, null, null]
a.length = 2
b.length = 5
c.length = 4
d.length = 3
a.length = 3
f: [0, 0, 0, 0, 0]
f.length = 5
g.length = 4
h.length = 3
e.length = 3
e.length = 2
</spoiler> Массив а — неинициализированная локальная переменная, и компилятор не позволяет что-либо делать с этой ссылкой до тех пор, пока она не будет соответствующим образом инициализирована. Массив b инициализируется массивом ссылок на объектыBerylliumSpere, хотя ни один такой объект в массив не заносится. Несмотря на это, мы можем запросить размер массива, потому что b указывает на действительный объект. В этом проявляется некоторый недостаток массивов: поле length сообщает, сколько элементов может быть помещено в массив, то есть размер объекта массива, а не количество хранящихся в нем элементов. Тем не менее при создании объекта массива все ссылки автоматически инициализируются значением null, и, чтобы узнать, связан ли некоторый элемент массива с объектом, достаточно проверить ссылку на равенство null. Аналогично, массивы примитивных типов автоматически инициализируются нулями для числовых типов: (char)0 для char и false для boolean. Массив с демонстрирует создание массива с последующим присваиванием объектов BerylliumSphere всем элементам массива. Массив d демонстрирует синтаксис «агрегатной инициализации», при котором объект массива создается (с ключевым словом new, как массив с) и инициализируется объектами BerylliumSphere, причем все это происходит в одной команде. Следующую конструкцию инициализации массива можно назвать «динамической агрегатной инициализацией». Агрегатная инициализация, используемая d, должна использоваться в точке определения d, но при втором синтаксисе объект массива может создаваться и использоваться в любой точке. Предположим, методу hide() передается массив объектов BerylliumSphere. Его вызов может выглядеть так:
hide(d);
однако массив, передаваемый в аргументе, также можно создать динамически:
hide(new BerylliumSphere[]{ new BeryllіumSphere(), new BerylliumSphere() });
Во многих ситуациях такой синтаксис оказывается более удобным.
Выражение
a=d;
показывает, как взять ссылку, связанную с одним объектом массива, и присвоить ее другому объекту массива, как это делается с любым другим типом ссылки на объект. В результате a и d указывают на один объект массива в куче. Вторая часть ArrayOptions.javaпоказывает, что примитивные массивы работают точно так же, как массивы объектов, за исключением того, что примитивные значения сохраняются в них напрямую.
Возврат массива
Предположим, вы пишете метод, который должен возвращать не отдельное значение, а целый набор значений. В таких языках, как C и C++, это сделать нелегко, потому что возвращается из метода не массив, а только указатель на массив. При этом возникают проблемы, поскольку сложности с управлением жизненным циклом массива могут привести к утечке памяти. В Java вы просто возвращаете массив. Вам не нужно беспокоиться о нем — массив будет существовать до тех пор, пока он вам нужен, а когда надобность в нем отпадет, массив будет уничтожен уборщиком мусора. В качестве примера рассмотрим возвращение массива String:
//: arrays/IceCream.java
// Возвращение массивов из методов
import java.util.*;
public class IceCream {
private static Random rand = new Random(47);
static final String[] FLAVORS = {
"Chocolate", "Strawberry", "Vanilla Fudge Swirl",
"Mint Chip", "Mocha Almond Fudge", "Rum Raisin",
"Praline Cream", "Mud Pie"
};
public static String[] flavorSet(int n) {
if(n > FLAVORS.length)
throw new IllegalArgumentException("Set too big");
</spoiler> Метод flavorSet() создает массив results с элементами String. Размер массива равен n; он определяется аргументом, передаваемым при вызове метода. Далее метод случайным образом выбирает элементы из массива FLAVORS и помещает их в массив results, возвращаемый методом. Массив возвращается точно так же, как любой другой объект, — по ссылке. При этом не важно, был ли массив создан методом flavorSet(), или он был создан в другом месте. Массив останется с вами все время, пока он будет нужен, а потом уборщик мусора позаботится о его уничтожении. Из выходных данных видно, что метод flavorSet() действительно выбирает случайное подмножество элементов при каждом вызове.
Многомерные массивы
Создание многомерных массивов в Java не вызывает особых сложностей. Для многомерных массивов примитивных типов каждый вектор заключается в фигурные скобки:
//: arrays/MultidimensionalPrimitiveArray.java
// Creating multidimensional arrays.
import java.util.*;
public class MultidimensionalPrimitiveArray {
public static void main(String[] args) {
int[][] a = {
{ 1, 2, 3, },
{ 4, 5, 6, },
};
System.out.println(Arrays.deepToString(a));
}
}
<spoiler text="Output:"> [[1, 2, 3], [4, 5, 6]] </spoiler> Каждая вложенная пара фигурных скобок описывает новую размерность массива. В этом примере используется метод Java SE5Arrays.deepToString(). Как видно из выходных данных, он преобразует многомерные массивы вString. Массив также может создаваться ключевым словом new. Пример создания трехмерного массива выражением new:
</spoiler> Как видите, если массиву примитивных типов не заданы явные значения, он автоматически инициализируется значениями по умолчанию. Массивы объектов инициализируются ссылками null. Векторы массивов, образующих матрицу, могут иметь разную длину (это называется ступенчатым массивом):
//: arrays/RaggedArray.java
import java.util.*;
public class RaggedArray {
public static void main(String[] args) {
Random rand = new Random(47);
// Трехмерный массив с векторами переменной длины:
</spoiler> Первая конструкция new создает массив, у которого первый элемент имеет случайную длину, а остальные остаются неопределенными. Вторая конструкция new в цикле for заполняет элементы, но оставляет третий индекс неопределенным вплоть до выполнения третьего new. Массивы с не-примитивными элементами заполняются аналогичным образом. Пример объединения нескольких выражений new в фигурных скобках:
</spoiler> Массив spheres также является ступенчатым, то есть длины вложенных списков объектов различаются. Механизм автоматической упаковки работает с инициализаторами массивов:
</spoiler> А вот как происходит поэлементное построение массива не-примитивных объектов:
//: arrays/AssemblingMultidimensionalArrays.java
// Создание многомерных массивов
import java.util.*;
public class AssemblingMultidimensionalArrays {
public static void main(String[] args) {
Integer[][] a;
a = new Integer[3][];
for(int i = 0; i < a.length; i++) {
a[i] = new Integer[3];
for(int j = 0; j < a[i].length; j++)
a[i][j] = i * j; // Автоматическая упаковка
}
System.out.println(Arrays.deepToString(a));
}
}
<spoiler text="Output:">
[[0, 0, 0], [0, 1, 2], [0, 2, 4]]
</spoiler> Выражение i*j присутствует только для того, чтобы поместить менее тривиальное значение в Integer. Метод Arrays.deepToString() работает как с массивами примитивных типов, так и с массивами объектов:
</spoiler> И снова в массивах Integer и Double механизм автоматической упаковки Java SE5 создает необходимые объекты-«обертки».
Массивы и параметризация
В общем случае массивы и параметризация плохо сочетаются друг с другом. Например, массивы не могут инициализироваться параметризованными типами:
Peel<Banana>[] peels = new Peel<Banana>[10]: // He разрешено
Стирание удаляет информацию о параметре типа, а массив должен знать точный тип хранящихся в нем объектов для обеспечения безопасности типов. Впрочем, параметризовать можно сам тип массива:
//: arrays/ParameterizedArrayType.java
class ClassParameter<T> {
public T[] f(T[] arg) { return arg; }
}
class MethodParameter {
public static <T> T[] f(T[] arg) { return arg; }
}
public class ParameterizedArrayType {
public static void main(String[] args) {
Integer[] ints = { 1, 2, 3, 4, 5 };
Double[] doubles = { 1.1, 2.2, 3.3, 4.4, 5.5 };
Integer[] ints2 =
new ClassParameter<Integer>().f(ints);
Double[] doubles2 =
new ClassParameter<Double>().f(doubles);
ints2 = MethodParameter.f(ints);
doubles2 = MethodParameter.f(doubles);
}
}
Обратите внимание, как удобно использовать параметризованный метод вместо параметризованного класса: вам не придется создавать очередную «версию» класса с параметром для каждого типа, к которому он применяется, и его можно сделать static. Конечно, параметризованный класс не всегда можно заменить параметризованным методом, но такое решение может оказаться предпочтительным.
Как выясняется, не совсем правильно говорить, что вы не можете создавать массивы параметризованных типов. Действительно, компилятор не позволит создать экземпляр массива параметризованного типа, но вы можете создать ссылку на такой массив. Пример:
List<String>[] Is;
Такая конструкция проходит проверку без малейших возражений со стороны компилятора. И хотя вы не можете создать объект массива с параметризацией, можно создать объект непараметризованного типа и преобразовать его:
//: arrays/ArrayOfGenerics.java
// Возможность создания массивов параметризованных типов.
import java.util.*;
public class ArrayOfGenerics {
@SuppressWarnings("unchecked")
public static void main(String[] args) {
List<String>[] ls;
List[] la = new List[10];
ls = (List<String>[])la; //Предупреждение о
// непроверенном преобразовании
ls[0] = new ArrayList<String>();
// Приводит к ошибке на стадии компиляции :
//! ls[1] = new ArrayList<Integer>();
// Проблема: List<String> является подтипом Object
Object[] objects = ls; // Поэтому присваивание возможно
// Компилируется и выполняется без ошибок и предупреждений :
objects[1] = new ArrayList<Integer>();
// Но если ваши потребности достаточно элементарны.
// создать массив параметризованных типов можно, хотя
// и с предупреждением о "непроверенном" преобразовании
List<BerylliumSphere>[] spheres =
(List<BerylliumSphere>[])new List[10];
for(int i = 0; i < spheres.length; i++)
spheres[i] = new ArrayList<BerylliumSphere>();
}
}
Мы видим, что при при получении ссылки на List<String>[] выполняется некоторая проверка на стадии компиляции. Проблема в том, что массивы ковариантны, поэтому List<String>[] также является Object[], поэтому вашему массиву можно присвоить ArrayList<Integer> без выдачи ошибок на стадии компиляции или выполнения. Если вы уверены в том, что восходящее преобразование выполняться не будет, а ваши потребности относительно просты, можно создать массив параметризованных типов, обеспечивающий простейшую проверку типов на стадии компиляции. Тем не менее параметризованный контейнер практически всегда оказывается более удачным решением, чем массив параметризованных типов.
Создание тестовых данных
При экспериментах с массивами (и программами вообще) полезно иметь возможность простого заполнения массивов тестовыми данными. Инструментарий, описанный в этом разделе, заполняет массив объектными значениями.
Arrays.fill();
Класс Arrays из стандартной библиотеки Java содержит весьма тривиальный метод fill(): он всего лишь дублирует одно значение в каждом элементе массива, а в случае объектов копирует одну ссылку в каждый элемент. Пример:
//: arrays/FillingArrays.java
// Использование Arrays.fill()
import java.util.*;
import static net.mindview.util.Print.*;
public class FillingArrays {
public static void main(String[] args) {
int size = 6;
boolean[] a1 = new boolean[size];
byte[] a2 = new byte[size];
char[] a3 = new char[size];
short[] a4 = new short[size];
int[] a5 = new int[size];
long[] a6 = new long[size];
float[] a7 = new float[size];
double[] a8 = new double[size];
String[] a9 = new String[size];
Arrays.fill(a1, true);
print("a1 = " + Arrays.toString(a1));
Arrays.fill(a2, (byte)11);
print("a2 = " + Arrays.toString(a2));
Arrays.fill(a3, 'x');
print("a3 = " + Arrays.toString(a3));
Arrays.fill(a4, (short)17);
print("a4 = " + Arrays.toString(a4));
Arrays.fill(a5, 19);
print("a5 = " + Arrays.toString(a5));
Arrays.fill(a6, 23);
print("a6 = " + Arrays.toString(a6));
Arrays.fill(a7, 29);
print("a7 = " + Arrays.toString(a7));
Arrays.fill(a8, 47);
print("a8 = " + Arrays.toString(a8));
Arrays.fill(a9, "Hello");
print("a9 = " + Arrays.toString(a9));
// Интервальные операции:
Arrays.fill(a9, 3, 5, "World");
print("a9 = " + Arrays.toString(a9));
}
}
<spoiler text="Output:">
a1 = [true, true, true, true, true, true]
a2 = [11, 11, 11, 11, 11, 11]
a3 = [x, x, x, x, x, x]
a4 = [17, 17, 17, 17, 17, 17]
a5 = [19, 19, 19, 19, 19, 19]
a6 = [23, 23, 23, 23, 23, 23]
a7 = [29.0, 29.0, 29.0, 29.0, 29.0, 29.0]
a8 = [47.0, 47.0, 47.0, 47.0, 47.0, 47.0]
a9 = [Hello, Hello, Hello, Hello, Hello, Hello]
a9 = [Hello, Hello, Hello, World, World, Hello]
</spoiler> Метод заполняет либо весь массив, либо, как показывают две последние команды, диапазон его элементов. Но, поскольку вызывать Arrays.fill() можно только для одного значения данных, полученные результаты не слишком полезны.
Генераторы данных
Чтобы создавать менее тривиальные массивы данных с более гибкими возможностями, мы воспользуемся концепцией генераторов, представленной в главе 14. Генератор способен выдавать любые данные по вашему выбору (напомню, что он является примером паттерна «стратегия» — разные генераторы представляют разные стратегии). В этом разделе будут представлены некоторые готовые генераторы, но вы также сможете легко определить собственный генератор для своих потребностей. Для начала рассмотрим простейший набор счетных генераторов для всех примитивных типов и String. Классы генераторов вложены в класс CountingGenerator, чтобы они могли обозначаться именами генерируемых объектов. Например, генератор, создающий объекты Integer, будет создаваться выражением new CountingGenerator.Integer():
