Интерфейсы. Контейнерные классы

Разбить на страницы

Показывать лекцию целиком

Интерфейсы

Презентацию к данной лекции Вы можете скачать здесь.

Синтаксис интерфейса

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

Каждый класс может определять элементы интерфейса по-своему. Так достигается полиморфизм: объекты разных классов по-разному реагируют на вызовы одного и того же метода.

Синтаксис интерфейса аналогичен синтаксису класса:

[ атрибуты ] [ спецификаторы ] interface имя_интерфейса [ : предки ]
     тело_интерфейса [ ; ]

Для интерфейса могут быть указаны спецификаторы new, public, protected, internal и private. Спецификатор new применяется для вложенных интерфейсов и имеет такой же смысл, как и соответствующий модификатор метода класса. Остальные спецификаторы управляют видимостью интерфейса. По умолчанию интерфейс доступен только из сборки, в которой он описан ( internal ).

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

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

interface IAction
{
    void Draw();
    int Attack(int a);
    void Die();
    int Power { get; }
}

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

int Power { get; set; }

Отличия интерфейса от абстрактного класса:

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

интерфейс не может содержать полей и обычных методов — все элементы интерфейса должны быть абстрактными;

класс, в списке предков которого задается интерфейс, должен определять все его элементы, в то время как потомок абстрактного класса может не переопределять часть абстрактных методов предка (в этом случае производный класс также будет абстрактным);

класс может иметь в списке предков несколько интерфейсов, при этом он должен определять все их методы.

Реализация интерфейса

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

using System;
namespace ConsoleApplication1
{
    interface IAction
    {
        void Draw();
        int Attack( int a );
        void Die();
        int Power { get; }
    }

    class Monster : IAction
    {
        public void Draw()
        {
            Console.WriteLine( "Здесь был " + name );

        }
        public int Attack( int ammo_ )
        {
            ammo -= ammo_;
            if ( ammo > 0 ) Console.WriteLine( "Ба-бах!" );
            else            ammo = 0;
            return ammo;
        }

        public void Die()
        {
            Console.WriteLine( "Monster " + name + " RIP" );
            health = 0;
        }

        public int Power 
        { 
            get
            {
                return ammo * health; 
            }
        }

        …
}

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

Monster Vasia = new Monster( 50, 50, "Вася" );  // объект класса Monster
Vasia.Draw();                                   // результат: Здесь был Вася
IAction Actor = new Monster( 10, 10, "Маша" );  // объект типа интерфейса
Actor.Draw();                                   // результат: Здесь был Маша

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

class Monster : IAction
    {
        int IAction.Power 
        { 
            get
            {
                return ammo * health; 
            }
        }

        void IAction.Draw()
        {
            Console.WriteLine( "Здесь был " + name );
        }
        ...
    }
...
IAction Actor = new Monster( 10, 10, "Маша" );
Actor.Draw();                      // обращение через объект типа интерфейса

// Monster Vasia = new Monster( 50, 50, "Вася" );    
// Vasia.Draw();

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

Работа с объектами через интерфейсы. Операции is и as

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

Результат операции равен true, если объект можно преобразовать к заданному типу, и false в противном случае. Операция обычно используется в следующем контексте:

{
    // выполнить преобразование "объекта" к "типу"
    // выполнить действия с преобразованным объектом
}

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

static void Act( object A )
{
    if ( A is IAction )
    {
        IAction Actor = (IAction) A;
        Actor.Draw();
    }
}

В метод Act можно передавать любые объекты, но на экран будут выведены только те, которые поддерживают интерфейс IAction.

Недостатком использования операции is является то, что преобразование фактически выполняется дважды: при проверке и при собственно преобразовании. Более эффективной является другая операция — as. Она выполняет преобразование к заданному типу, а если это невозможно, формирует результат null, например:

static void Act( object A )
{
    IAction Actor = A as IAction;
    if ( Actor != null ) Actor.Draw();
}

Обе рассмотренные операции применяются как к интерфейсам, так и к классам.

Интерфейсы и наследование

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

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

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

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

interface IBase  
{  
   void A();  
}  

class Base : IBase  
{  
   public void A() { ... }  
}  

class Derived: Base
{  
   new public void A() { ... }  
}  

...
Derived d = new Derived ();  
d.A();                        // вызывается Derived.A();  
IBase id = d;  
id.A();                       // вызывается Base.A();

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

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

interface IBase  
{  
   void A();  
}  

class Base : IBase  
{  
   void IBase.A() { ... }        // не используется в Derived
}  

class Derived : Base, IBase
{  
   public void A() { ... }  
}

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

Стандартные интерфейсы .NET

В библиотеке классов .NET определено множество стандартных интерфейсов, задающих желаемое поведение объектов. Например, интерфейс IComparable задает метод сравнения объектов на больше-меньше, что позволяет выполнять их сортировку. Реализация интерфейсов IEnumerable и IEnumerator дает возможность просматривать содержимое объекта с помощью конструкции foreach, а реализация интерфейса ICloneable — клонировать объекты.

Стандартные интерфейсы поддерживаются многими стандартными классами библиотеки. Например, работа с массивами с помощью цикла foreach возможна именно потому, что тип Array реализует интерфейсы IEnumerable и IEnumerator. Можно создавать и собственные классы, поддерживающие стандартные интерфейсы, что позволит использовать объекты этих классов стандартными способами.

Сравнение объектов

Интерфейс IComparable определен в пространстве имен System. Он содержит всего один метод CompareTo, возвращающий результат сравнения двух объектов — текущего и переданного ему в качестве параметра:

interface IComparable
{
    int CompareTo( object obj )
}

Метод должен возвращать:

0, если текущий объект и параметр равны;

отрицательное число, если текущий объект меньше параметра;

положительное число, если текущий объект больше параметра.

Реализуем интерфейс IComparable в знакомом нам классе Monster. В качестве критерия сравнения объектов выберем поле health. В листинге 9.1 приведена программа, сортирующая массив монстров по возрастанию величины, характеризующей их здоровье.

using System;
namespace ConsoleApplication1
{
    class Monster : IComparable
    {
        public Monster( int health, int ammo, string name )
        {
            this.health = health;
            this.ammo   = ammo;
            this.name   = name;
        }
        
        virtual public void Passport()
        {
            Console.WriteLine( "Monster {0} \t health = {1} ammo = {2}", 
                               name, health, ammo );
        }

        public int CompareTo( object obj )          // реализация интерфейса
        {
            Monster temp = (Monster) obj;
            if ( this.health > temp.health ) return  1;
            if ( this.health < temp.health ) return -1;
            return 0;
        }

        string name;
        int health, ammo;
    }

    class Class1
    {   static void Main()
        {
            const int n = 3;
            Monster[] stado = new Monster[n];

            stado[0] = new Monster( 50, 50, "Вася" );
            stado[1] = new Monster( 80, 80, "Петя" );
            stado[2] = new Monster( 40, 10, "Маша" );

            Array.Sort( stado );               // сортировка стала возможной
            foreach ( Monster elem in stado ) elem.Passport();
        }
    }
}

Результат работы программы:

Monster Маша     health = 40 ammo = 10
Monster Вася     health = 50 ammo = 50
Monster Петя     health = 80 ammo = 80

Во многих алгоритмах требуется выполнять сортировку объектов по различным критериям. В C# для этого используется интерфейс IComparer, который мы рассмотрим далее.

Сортировка по разным критериям (интерфейс IComparer)

Интерфейс IComparer определен в пространстве имен System.Collections. Он содержит один метод Compare, возвращающий результат сравнения двух объектов, переданных ему в качестве параметров:

interface IComparer
{
    int Compare( object ob1, object ob2 )
}

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

Пример сортировки массива объектов из предыдущего листинга по именам (свойство Name, класс SortByName ) и количеству вооружений (свойство Ammo, класс SortByAmmo ) приведен в листинге 9.2.

using System;
using System.Collections;
namespace ConsoleApplication1
{
    class Monster
    {
        public Monster( int health, int ammo, string name )
        {
            this.health = health;
            this.ammo   = ammo;
            this.name   = name;
        }
        
        public int Ammo 
        {
            get { return ammo; }
            set 
            {
                if (value > 0) ammo = value;
                else           ammo = 0;
            }
        }

        public string Name 
        {
            get { return name; }
        }

        virtual public void Passport()
        {
            Console.WriteLine( "Monster {0} \t health = {1} ammo = {2}", 
                               name, health, ammo );
        }

        public class SortByName : IComparer                               //
        {
            int IComparer.Compare( object ob1, object ob2 )
            {
                Monster m1 = (Monster) ob1;
                Monster m2 = (Monster) ob2;
                return String.Compare( m1.Name, m2.Name );
            }
        }

        public class SortByAmmo : IComparer                               //
        {
            int IComparer.Compare( object ob1, object ob2 )
            {
                Monster m1 = (Monster) ob1;
                Monster m2 = (Monster) ob2;
                if ( m1.Ammo > m2.Ammo ) return  1;
                if ( m1.Ammo < m2.Ammo ) return -1;
                return 0;
            }
        }
        string name;
        int health, ammo;
    }
    
    class Class1
    {   static void Main()
        {
            const int n = 3;
            Monster[] stado = new Monster[n];

            stado[0] = new Monster( 50, 50, "Вася" );
            stado[1] = new Monster( 80, 80, "Петя" );
            stado[2] = new Monster( 40, 10, "Маша" );

            Console.WriteLine( "Сортировка по имени:" );
            Array.Sort( stado, new Monster.SortByName() );
            foreach ( Monster elem in stado ) elem.Passport();

            Console.WriteLine( "Сортировка по вооружению:" );
            Array.Sort( stado, new Monster.SortByAmmo() );
            foreach ( Monster elem in stado ) elem.Passport();
        }
    }
}

Результат работы программы:

Сортировка по имени:
Monster Вася     health = 50 ammo = 50
Monster Маша     health = 40 ammo = 10
Monster Петя     health = 80 ammo = 80
Сортировка по вооружению:
Monster Маша     health = 40 ammo = 10
Monster Вася     health = 50 ammo = 50
Monster Петя     health = 80 ammo = 80

Перегрузка операций отношения

Если класс реализует интерфейс IComparable, его экземпляры можно сравнивать между собой на больше-меньше. Логично разрешить использовать для этого операции отношения, перегрузив их. Операции должны перегружаться парами: < и >, <= и >=, == и !=. Перегрузка операций обычно выполняется путем делегирования, то есть обращения к переопределенным методам CompareTo и Equals.

Примечание

Если класс реализует интерфейс IComparable, требуется переопределить метод Equals и связанный с ним метод GetHashCode. Оба метода унаследованы от базового класса object.

В листинге 9.3 операции отношения перегружены для класса Monster. В качестве критерия сравнения объектов на больше-меньше выступает поле health, а при сравнении на равенство попарно сравниваются все поля объектов

using System;
namespace ConsoleApplication1
{
    class Monster : IComparable
    {
        public Monster( int health, int ammo, string name )
        {
            this.health = health;
            this.ammo   = ammo;
            this.name   = name;
        }

        public override bool Equals( object obj )
        {
            if ( obj == null || GetType() != obj.GetType() ) return false;

            Monster temp = (Monster) obj;
            return health == temp.health 
                   ammo   == temp.ammo   
                   name   == temp.name;
        }

        public override int GetHashCode()
        {
            return name.GetHashCode();
        }

        public static bool operator == ( Monster a, Monster b )
        {
            return a.Equals( b );
        }

        public static bool operator != ( Monster a, Monster b )
        {
            return ! a.Equals( b );
        }

        public static bool operator < ( Monster a, Monster b )
        {
            return ( a.CompareTo( b ) < 0 );
        }
        
        public static bool operator > ( Monster a, Monster b )
        {
            return ( a.CompareTo( b ) > 0 );
        }
        
        public static bool operator <= ( Monster a, Monster b )
        {
            return ( a.CompareTo( b ) <= 0 );
        }
        
        public static bool operator >= ( Monster a, Monster b )
        {
            return ( a.CompareTo( b ) >= 0 );
        }

        public int CompareTo( object obj )
        {
            Monster temp = (Monster) obj;
            if ( this.health > temp.health ) return  1;
            if ( this.health < temp.health ) return -1;
            return 0;
        }

        string name;
        int health, ammo;
    }

    class Class1
    {   static void Main()
        {
            Monster Вася = new Monster( 70, 80, "Вася" );
            Monster Петя = new Monster( 80, 80, "Петя" );
        
            if      ( Вася > Петя )  Console.WriteLine( "Вася больше Пети");
            else if ( Вася == Петя ) Console.WriteLine( "Вася == Петя");
            else                     Console.WriteLine( "Вася меньше Пети");
        }
    }
}

Результат работы программы:

Вася меньше Пети

Клонирование объектов

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

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

Объект, имеющий собственные алгоритмы клонирования, должен объявляться как наследник интерфейса ICloneable и переопределять его единственный метод Clone. В листинге 9.4 приведен пример создания поверхностной копии объекта класса Monster с помощью метода MemberwiseClone, а также реализован интерфейс ICloneable. В демонстрационных целях в имя клона объекта добавлено слово "Клон".

using System;
namespace ConsoleApplication1
{ 
    class Monster : ICloneable
    {
        public Monster( int health, int ammo, string name )
        {
            this.health = health;
            this.ammo   = ammo;
            this.name   = name;
        }
        public Monster ShallowClone()                 // поверхностная копия
        {
            return (Monster)this.MemberwiseClone();
        }

        public object Clone()                      // пользовательская копия
        {
            return new Monster(this.health, this.ammo, "Клон " + this.name);
        }
 
        virtual public void Passport()
        {
            Console.WriteLine( "Monster {0} \t health = {1} ammo = {2}", 
                               name, health, ammo );
        }

        string name;
        int health, ammo;
    }
        
    class Class1
    {   static void Main()
        {
            Monster Вася = new Monster( 70, 80, "Вася" );
            Monster X = Вася;
            Monster Y = Вася.ShallowClone();
            Monster Z = (Monster)Вася.Clone();
            ...
        }
    }
}

Объект Х ссылается на ту же область памяти, что и объект Вася. Следовательно, если мы внесем изменения в один из этих объектов, это отразится на другом. Объекты Y и Z, созданные путем клонирования, обладают собственными копиями значений полей и независимы от исходного объекта.

Перебор объектов (интерфейс IEnumerable) и итераторы

Оператор foreach является удобным средством перебора элементов объекта. Массивы и все стандартные коллекции библиотеки .NET позволяют выполнять такой перебор благодаря тому, что в них реализованы интерфейсы IEnumerable и IEnumerator. Для применения оператора foreach к пользовательскому типу данных требуется реализовать в нем эти интерфейсы.

Интерфейс IEnumerable ( перечислимый ) определяет всего один метод — GetEnumerator, возвращающий объект типа IEnumerator ( перечислитель ), который можно использовать для просмотра элементов объекта.

Интерфейс IEnumerator задает три элемента:

свойство Current, возвращающее текущий элемент объекта;

метод MoveNext, продвигающий перечислитель на следующий элемент объекта;

метод Reset, устанавливающий перечислитель в начало просмотра.

Цикл foreach использует эти методы для перебора элементов, из которых состоит объект.

Таким образом, если требуется, чтобы для перебора элементов класса мог применяться цикл foreach, необходимо реализовать четыре метода: GetEnumerator, Current, MoveNext и Reset. Это не интересная работа, а выполнять ее приходится часто, поэтому в версию 2.0 были введены средства, облегчающие выполнение перебора в объекте — итераторы.

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

Рассмотрим создание итератора на примере (листинг 9.5). Пусть требуется создать объект, содержащий боевую группу экземпляров типа Monster.

using System;
using System.Collections;
namespace ConsoleApplication1
{
    class Monster { ... }
    class Daemon  { ... }
    class Stado : IEnumerable                                           // 1
    {
        private Monster[] mas;
        private int n;

        public Stado()
        {
            mas = new Monster[10];
            n = 0;
        }

        public IEnumerator GetEnumerator()
        {
            for ( int i = 0; i < n; ++i ) yield return mas[i];          // 2
        }

        public void Add( Monster m )
        {
            if ( n >= 10 ) return;
            mas[n] = m;
            ++n;
        }
    }

    class Class1
    {   static void Main()
        {
            Stado s = new Stado();
            s.Add( new Monster() );
            s.Add( new Monster("Вася") );
            s.Add( new Daemon() );
            
            foreach ( Monster m in s ) m.Passport();
        }
    }
}

Все, что требуется сделать в версии 2.0 для поддержки перебора — указать, что класс реализует интерфейс IEnumerable (оператор 1), и описать итератор (оператор 2). Доступ к нему может быть осуществлен через методы MoveNext и Current интерфейса IEnumerator.

Преимущество использования итераторов заключается в том, что для одного и того же класса можно задать различный порядок перебора элементов. В листинге 9.6 описаны две дополнительные стратегии перебора элементов класса Stado, введенного в листинге 9.5 — перебор в обратном порядке и выборка только тех объектов, которые являются экземплярами класса Monster.

using System;
using System.Collections;
using MonsterLib;

namespace ConsoleApplication1
{
    class Monster { ... }
    class Daemon  { ... }
    class Stado : IEnumerable
    {
        private Monster[] mas;
        private int n;
        public Stado()
        {
            mas = new Monster[10];
            n = 0;
        }
        public IEnumerator GetEnumerator()
        {
            for ( int i = 0; i < n; ++i ) yield return mas[i];
        }
        public IEnumerable Backwards()                 // в обратном порядке
        {
            for ( int i = n - 1; i >= 0; --i ) yield return mas[i];
        }

        public IEnumerable MonstersOnly()                  // только монстры
        {
            for ( int i = 0; i < n; ++i )
                if ( mas[i].GetType().Name == "Monster" ) 
                    yield return mas[i];
        }
        public void Add( Monster m )
        {
            if ( n >= 10 ) return;
            mas[n] = m; 
            ++n;
        }
    }

    class Class1
    {   static void Main()
        {
            Stado s = new Stado();
            s.Add( new Monster() );
            s.Add( new Monster("Вася") );
            s.Add( new Daemon() );
            
            foreach ( Monster i in s )                i.Passport();
            foreach ( Monster i in s.Backwards() )    i.Passport();
            foreach ( Monster i in s.MonstersOnly() ) i.Passport();
        }
    }
}

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

В теле блока итератора могут встречаться две конструкции:

yield return формирует значение, выдаваемое на очередной итерации;

yield break сигнализирует о завершении итерации.

Ключевое слово yield имеет специальное значение для компилятора только в этих конструкциях.

Код блока итератора выполняется не так, как обычные блоки. Компилятор формирует служебный объект-перечислитель, при вызове метода MoveNext которого выполняется код блока итератора, выдающий очередное значение с помощью ключевого слова yield. Следующий вызов метода MoveNext объекта-перечислителя возобновляет выполнение блока итератора с момента, на котором он был приостановлен в предыдущий раз.

Контейнерные классы

Абстрактные структуры данных

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

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

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

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

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

Стек — частный случай однонаправленного списка, добавление элементов в который и выборка из которого выполняются с одного конца, называемого вершиной стека. Другие операции со стеком не определены. При выборке элемент исключается из стека. Говорят, что стек реализует принцип обслуживания LIFO (Last In — First Out, последним пришел — первым ушел).

Очередь — частный случай однонаправленного списка, добавление элементов в который выполняется в один конец, а выборка — из другого конца. Другие операции с очередью не определены. При выборке элемент исключается из очереди. Говорят, что очередь реализует принцип обслуживания FIFO (First In — First Out, первым пришел — первым ушел).

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

(рис 9.1) Пример бинарного дерева поиска

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

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

Пример хэш-таблицы
Ключ	Значение
boy	мальчик
girl	девочка
dog	собачка

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

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

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

Множество — это неупорядоченная совокупность элементов. Для множеств определены операции проверки принадлежности элемента множеству, включения и исключения элемента, а также объединения, пересечения и вычитания множеств.

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

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

Внимание

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

В библиотеке .NET определено множество стандартных классов, реализующих большинство перечисленных ранее абстрактных структур данных. Основные пространства имен, в которых описаны эти классы — System.Collections, System.Collections.Specialized и System.Collections.Generic (начиная с версии 2.0).

Пространство имен System.Collections

В пространстве имен System.Collections определены наборы стандартных коллекций и интерфейсов, которые реализованы в этих коллекциях. В таблице 9.2 приведены наиболее важные интерфейсы, часть из которых уже изучались в разделе "Стандартные интерфейсы .NET".

Интерфейсы пространства имен System.Collections
Интерфейс	Назначение
ICollection	Определяет общие характеристики (например, размер) для набора элементов
IComparer	Позволяет сравнивать два объекта
IDictionary	Позволяет представлять содержимое объекта в виде пар "имя-значение"
IDictionaryEnumerator	Используется для нумерации содержимого объекта, поддерживающего интерфейс IDictionary
IEnumerable	Возвращает интерфейс IEnumerator для указанного объекта
IEnumerator	Обычно используется для поддержки оператора foreach в отношении объектов
IHashCodeProvider	Возвращает хэш-код для реализации типа с применением выбранного пользователем алгоритма хэширования
Ilist	Поддерживает методы добавления, удаления и индексирования элементов в списке объектов

В таблице 9.3 перечислены основные коллекции, определенные в пространстве System.Collections.

Коллекции пространства имен System.Collections
Класс	Назначение	Важнейшие из реализованных интерфейсов
ArrayList	Массив, динамически изменяющий свой размер	IList, ICollection, IEnumerable, ICloneable
BitArray	Компактный массив для хранения битовых значений	ICollection, IEnumerable, ICloneable
Hashtable	Хэш-таблица	IDictionary, ICollection, IEnumerable, ICloneable
Queue	Очередь	ICollection, ICloneable, IEnumerable
SortedList	Коллекция, отсортированная по ключам. Доступ к элементам — по ключу или по индексу	IDictionary, ICollection, IEnumerable, ICloneable
Stack	Стек	ICollection, IEnumerable

Пространство имен System.Collections.Specialized включает специализированные коллекции, например, коллекцию строк StringCollection и хэш-таблицу со строковыми ключами StringDictionary.

В качестве примера стандартной коллекции рассмотрим класс ArrayList.

Класс ArrayList

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

По умолчанию при создании объекта типа ArrayList строится массив из 16 элементов типа object. Можно задать желаемое количество элементов в массиве, передав его в конструктор или установив в качестве значения свойства Capacity, например:

ArrayList arr1 = new ArrayList();          // создается массив из 16   элементов
ArrayList arr2 = new ArrayList(1000);  // создается массив из 1000 элементов
ArrayList arr3 = new ArrayList(); 
arr3.Capacity = 1000;                        // количество элементов задается

Класс ArrayList реализован через класс Array, то есть содержит закрытое поле этого класса. Поскольку все типы в C# являются потомками класса object, массив может содержать элементы произвольного типа. Даже если в массиве хранятся обычные целые числа, то есть элементы значимого типа, внутренний класс является массивом ссылок на экземпляры типа object, которые представляют собой упакованный тип-значение. Соответственно, при занесении в массив выполняется упаковка, а при извлечении — распаковка элемента.

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

arr1.Add( 123 );    arr1.Add( -2 );    arr1.Add( "Вася" );

Доступ к элементу выполняется по индексу, однако при этом необходимо явным образом привести полученную ссылку к целевому типу, например:

int    a = (int) arr1[0];
int    b = (int) arr1[1];
string s = (string) arr1[2];

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

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

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

Классы-прототипы (generics)

Классы-прототипы (generics) — это классы, имеющие в качестве параметров типы данных. Чаще всего их применяют для хранения данных, то есть в качестве контейнерных классов, или коллекций. Во вторую версию библиотеки .NET добавлены параметризованные коллекции для представления основных структур данных, применяющихся при создании программ — стека, очереди, списка, словаря и т. д. Эти коллекции, расположенные в пространстве имен System.Collections.Generic, дублируют аналогичные коллекции пространства имен System.Collections. В таблице 9.4 приводится соответствие между обычными и параметризованными коллекциями библиотеки .NET (параметры, определяющие типы данных, хранимых в коллекции, указаны в угловых скобках).

Параметризованные коллекции библиотеки .NET версии 2.0
Класс-прототип (версия 2.0)	Обычный класс
Comparer<T>	Comparer
Dictionary<K,T>	HashTable
LinkedList<T>	—
List<T>	ArrayList
Queue<T>	Queue
SortedDictionary<K,T>	SortedList
Stack<T>	Stack<T>

В качестве примера рассмотрим применение универсального "двойника" класса ArrayList — класса List<T> — для хранения коллекции объектов известных нам классов Monster и Daemon, а также для хранения целых чисел.

using System;
using System.Collections.Generic;
using System.Text;

namespace ConsoleApplication1
{
    using MonsterLib;    // библиотека, в которой хранятся классы Monster и Daemon
    class Program
    {
        static void Main()
        {
            List<Monster> stado = new List<Monster>();
            stado.Add( new Monster( "Monia" ) );
            stado.Add( new Monster( "Monk" ) );
            stado.Add( new Daemon ( "Dimon", 3 ) );

            foreach ( Monster x in stado ) x.Passport();

            List<int> lint = new List<int>();
            lint.Add( 5 ); lint.Add( 1 ); lint.Add( 3 );
            lint.Sort();
            int a = lint[2];
            Console.WriteLine( a );

            foreach ( int x in lint ) Console.Write( x + " ");
}}}

Результат работы программы:

Monster Monia    health = 100 ammo = 100
Monster Monk     health = 100 ammo = 100
Daemon Dimon     health = 100 ammo = 100 brain = 3
5
1 3 5

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

Коллекция lint состоит из целых чисел, причем для работы с ними не требуются ни операции упаковки и распаковки, ни явные преобразования типа при получении элемента из коллекции.

Классы-прототипы называют также родовыми или шаблонными, поскольку они представляют собой образцы, по которым во время выполнения программы строятся конкретные классы.

Вопросы и задания для самостоятельной работы студента

Изучите разделы стандарта C#, касающиеся интерфейсов.

Изучите по справочной системе основные стандартные интерфейсы .NET.

Чем интерфейс отличается от абстрактного класса?

Должен ли класс реализовывать все методы всех своих интерфейсов-предков?

Какие операции используются для проверки, реализует ли класс заданный интерфейс?

Перечислите стандартные интерфейсы .NET, которые определяют возможности сортировки, клонирования и просмотра объектов с помощью оператора foreach.

Опишите, как используется конструкция yield.

Изучите по справочной системе состав пространства имен System.Collections.

Изучите по справочной системе свойства и методы класса ArrayList.

Изучите разделы стандарта C#, касающиеся классов-прототипов.

Изучите по справочной системе состав пространства имен System.Collections.Generic. Опишите основные виды абстрактных структур данных.

Допускает ли структура "линейный список" прямой доступ к своим элементам?

В чем основная задача хеш-функции?

В каких задачах используется стек? Приведите примеры.

Сравните время поиска элемента в линейном списке и в дереве поиска.

В чем преимущество массива перед другими структурами данных?

Опишите состав пространства имен System.Collections и дайте характеристику основных типов-коллекций.

Какие новые контейнеры появились в библиотеке классов для версии С# 2.0?

В чем преимущества контейнеров версии С# 2.0?

Какие методы содержит класс ArrayList?

Лабораторная работа 10. Интерфейсы и параметризованные коллекции

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

Страницы: