Коллекции и контейнеры в языках программирования. Алгоритмы обработки данных в библиотеке STL. Технология LINQ to Object

1. Коллекции и контейнеры в языках программирования.

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

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

Контейнеры представляют собой классы, специ­ально предназначенные для упорядоченного хранения данных различных типов. В терминах языка С# такие контейнеры называются наборами данных (collections).

Классы коллекций по своей сути подобны классам стандартной библиотеки шаблонов (Standard Template Library — STL), определенной в С++. То, что в программировании на С++ называется контейнером, в программировании на С# называется коллекцией.

STL. В библиотеке выделяют пять основных компонентов:

· Контейнер (container) — хранение набора объектов в памяти.

· Итератор (iterator) — обеспечение средств доступа к содержимому контейнера.

· Алгоритм (algorithm) — определение вычислительной процедуры.

· Адаптер (adaptor) — адаптация компонентов для обеспечения различного интерфейса.

· Функциональный объект (functor) — сокрытие функции в объекте для использования другими компонентами.

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

Основные коллекции C# размещены в пространстве имен System.Collections, они являются аналогами контейнеров библиотеки STL (Standard Template Library) C++ и обладают такой же функциональностью. Это устаревшая библиотека, реализованная в версии C# 1.0. Коллекции принимают объекты любого типа, что затрудняет контроль типов данных.

2. Алгоритмы обработки данных в библиотеке STL

Стандартная библиотека шаблонов (STL) (англ. Standard Template Library) — набор согласованных обобщённых алгоритмов, контейнеров, средств доступа к их содержимому и различных вспомогательных функций в C++.

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

Библиотека STL предоставляет основные виды алгоритмов:

· Математические (расчёт сумм, произведений, генерация случайных значений)

· Поиска (минимальное значение, поиск последовательности, подсчёт числа значений)

· Сортировки

· Работы с последовательностями (объединение последовательностей, сравнения, обработки последовательности типовой операцией)

3. Технология LINQ to Object

Термином "LINQ to Objects" называют использование запросов LINQ с коллекциями, поддерживающими интерфейс IEnumerable или IEnumerable<T> без промежуточных поставщиков LINQ или API-интерфейсов, таких как LINQ to SQL или LINQ to XML. LINQ можно использовать для запроса любых перечислимых коллекций, таких как List<T>, Array или Dictionary<TKey, TValue>. Коллекция может быть определенной пользователем или возвращенной API.NET Framework.

По сути, LINQ to Objects представляет новый подход к коллекциям. Раньше нужно было писать сложные циклы foreach, которые определяли способ извлечения данных из коллекции. При применении подхода LINQ создается декларативный код с описанием необходимых извлекаемых данных.

Кроме того, запросы LINQ имеют три основных преимущества перед традиционными циклами foreach.

· Они более компактные и удобочитаемые, особенно при фильтрации по нескольким условиям.

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

· Они могут быть перенесены на другие источники данных с минимальными изменениями или без изменений.

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

Язык интегрированных запросов LINQ (Language Integrated Query) появился в Visual Studio 2008 и.NET Framework версии 3.5, это подсистема языка, предназначена для обработки данных и дополняет C# средствами, позволяющими формировать запросы для любого LINQ-совместимого источника данных. Причем в качестве источника данных могут выступать как коллекции языка C#, так и таблицы баз данных.

Предложения LINQ реализованы при помощи методов расширения, размещенных в пространстве имен System.Linq.

В основу LINQ положено понятие запроса, в котором определяется информация, полученная из источника данных. Выражения запросов составляются в соответствии с декларативным синтаксисом, который позволяет выполнять достаточно сложную фильтрацию, упорядочение и операции группирования при работе с источниками данных, в этом источнике должен быть реализован интерфейс IEnumerable<T>.

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

Основные операции запроса:

· Получение источника данных.

from переменная диапазона in источник данных

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

· Фильтрация.

where логическое выражение

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

· Упорядочение (Сортировка).

orderby элемент [порядок]

Предложение orderby сортирует элементы возвращаемой последовательности в зависимости от метода сравнения по умолчанию. Порядок сортировки по возрастанию или убыванию определяется ключевым словом ascending (по умолчанию) или descending соответственно.

Возможна сортировка по нескольким элементам

orderby элемент А [порядок], элемент В [порядок],...

· Соединение.

Предложение join создает связи между последовательностями, неявно смоделированными в источниках данных.

· Группировка.

group переменная диапазона by ключ

Предложение group позволяет группировать результаты на основе указанного ключа.

· Выбор (Проецирование).

select выражение

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