Контейнеры STL библиотеки. Коллекции на Java и C#

Контейнеры STL библиотеки. Коллекции на Java и C#. 1) Использование библиотеки STL на C++ Стандартная библиотека шаблонов (STL) содержит пять основных видов компонентов: • алгоритм (algorithm): определяет вычислительную процедуру. • контейнер (container): управляет набором объектов в памяти. • итератор (iterator): обеспечивает для алгоритма средство доступа к содержимому контейнера. • функциональный объект (function object): инкапсулирует функцию в объекте для использования другими компонентами. • адаптер (adaptor): адаптирует компонент для обеспечения различного интерфейса. Недостаток массива на C++ - необходимо заранее определить число элементов. int A[100]; // далее происходит чтение чисел из файла, а там может быть 5, может 200 Последовательные контейнеры STL: vector (вектор), list (список) и deque (двусторонняя очередь, дек). Ассоциативные контейнеры STL: map (ассоциативный массив), set (множество) и multimap и multiset. Вектор - обобщенный массив с подвижной правой границей. Имеет дополнительные методы добавки/удаления и доступа. Основные методы vector a) push_back - добавка в конец vector b) pop_back - удаление последнего элемента c) size - текущий размер vector Пример - вектор из целых чисел и вектор из объектов Record. #include "stdafx.h" #include #include // использование контейнера using namespace std; class Record { private: int min,sec; public: Record(int m,int s); void Display(); int Numbersec(); }; Record::Record(int m,int s) { min=m; sec=s; } void Record::Display() { cout << min<<" "< v1; // контейнер целых чисел vector v2; // контейнер из объектов класса Record v1.clear(); // очистка контейнеров v2.clear(); int k,m,n,p,z; k=2; m=5; n=3; v1.push_back(k); v1.push_back(m); v1.push_back(n); v1.push_back(9); // v1: 2 5 3 9 p=v1.size(); // p=4 v1.pop_back(); // v1: 253 Record a(2,55),b(3,1),c(3,8); v2.push_back(a); v2.push_back(b); z=v1[1]; // обращение как к элементу массива cout<::iterator it; // итератор для целых чисел vector ::iterator ir; // итератор для Record it=v1.begin(); // итератор - на начало контейнера it++; // встроенная операция – итератор на 1 элемент v1.insert(it,6); // v1: 2 6 5 3 вставка it+=2; v1.erase(it); // v1: 2 6 5 удаление ir=v2.end(); // итератор на конец контейнера (за последним элементом) ir--; v2.insert(ir,d); // v2: {2 55} {4 1} {3 1} вставка Record int s; s=0; for (ir=v2.begin();ir != v2.end(); ++ir) // цикл по всем элементам контейнера { s+=(*ir).Numbersec(); // добавка очередного результата s - сумма всех результатов } cout<<'\n'; cout < tmp = v1; v1.swap(tmp); // освобождение памяти контейнера v2.clear(); // очистка контейнера vector tmp1 = v2; v2.swap(tmp1); // освобождение памяти 2) Краткие сведения о контейнере list, adapter, functor В обычном массиве обеспечивается быстрый доступ к элементам массива, но операции вставки и удаления элементов требуют значительного времени. s=0; for(i=0;i];[Inf1,-> ],...,[Infn,->NULL]. Вставки/удаления выполняются присваиванием указателей (быстро), извлечение k-го элемента медленно (с головы - по указателям двигаться k раз). Контейнер list представляет собой двусвязный список. Элемент имеет вид: [<- Inf1,-> ] – указатель назад позволяет быстрее двигаться в обратном направлении. adapter – дополнительные контейнеры (stack, queue, priority_queue – стек, очередь, очередь с приоритетами) functor – функциональный объект. Функциональный объект – объект + (), т.е. объект, который ведет себя как функция. Еще одна концепция обобщенного программирования – функция – все, что ведет себя как функция. class absV { public: float operator()(float f)// functor – вычисление модуля { if(f<0) return -f; else return f; } }; int _tmain(int argc, _TCHAR* argv[]) { float f=-12.34; absV a; // объект класса absV float x; x=a(f); // объект как метод!! } 3) Алгоритмы Набор эффективных алгоритмов для работы с элементами контейнера или с другими наборами данных. Реализованы наиболее быстрые алгоритмы сортировки и поиска. а) Сортировка с предикатом Обычная сортировка целых чисел в контейнере: #include "stdafx.h" #include #include #include // алгоритмы using namespace std; ...... int _tmain(int argc, _TCHAR* argv[]) { vector v1; v1.clear(); v1.push_back(9); v1.push_back(6); v1.push_back(-2); v1.push_back(-5); v1.push_back(3); v1.push_back(-1); v1.push_back(4); v1.push_back(7); // 9 6 -2 -5 3 -1 4 sort(v1.begin(),v1.end()); // -5 -2 -1 3 4 5 6 7 9 Дан контейнер с целыми числами. Выполнить преобразование: Вначале расположить все отрицательные числа в порядке убывания, затем положительные в порядке убывания. #include "stdafx.h" #include #include #include using namespace std; bool cmd (int i1,int i2) // предикат для сортировки если i1 надо менять с i2 - вернуть false, иначе true. { if(i1>0 && i2<0) // слева +, справа - -> нужно поменять местами return false; else if(i1<0 && i2>0) // слева - справа + -- не нужно поменять местами return true; else return i1>i2; // оставшийся случай слева меньше чем справа - false менять местами } int _tmain(int argc, _TCHAR* argv[]) { vector v1; v1.clear(); v1.push_back(9); v1.push_back(6); v1.push_back(-2); v1.push_back(-5); v1.push_back(3); v1.push_back(-1); v1.push_back(4); v1.push_back(7); sort(v1.begin(),v1.end(),cmd); // -1 -2 -5 9 7 6 4 3 Пример сортировки для контейнера с объектами. В контейнере объетов класса Record сортировать по возрастанию результатов (значению метода Numbersec() ) #include "stdafx.h" #include #include #include using namespace std; class Record { private: int min,sec; public: Record(int m,int s); void Display(); int Numbersec(); }; Record::Record(int m,int s) { min=m; sec=s; } void Record::Display() { cout << min<<" "<v2; Record a(2,55),b(3,1),c(3,8),d(4,1); v2.clear(); v2.push_back(d); v2.push_back(b); v2.push_back(c); v2.push_back(a); // v2: {4 1} {3 1} {3 8} {2 55} sort(v2.begin(),v2.end(),con); // v2: {2 55} {3 1} {3 8} {4 1} б) Поиск с предикатом Найти в контейнере целых чисел число в диапазоне [5 6] ...... bool cond(int k) { return (k>=5 && k<=6); // предикат - условие поиска } ..... vector v1; vector v2; v1.clear(); v1.push_back(9); v1.push_back(6); v1.push_back(-2); v1.push_back(-5); v1.push_back(3); v1.push_back(-1); v1.push_back(4); v1.push_back(7); // поиск vector::iterator ia; ia=find_if(v1.begin(),v1.end(),cond); // поиск, удовлетворяющий условию if(ia != v1.end()) // если найден int v=(*ia); // v=6 в) Некоторые другие алгоритмы binary_search() - бинарный поиск. Элементы упорядочены, поиск - разбиение контейнера пополам и сравнение со срединой. 1 4 7 9 11 14 18. Искать 3 3 <9 - искать в левой половине 1 4 7 9 11 14 18 3 <4 искать в левой половине 1 4 7 остался 1 элемент - не найдено. count_if() - подсчет элементов в контейнере по условию merge() - слияние контейнеров unique() - удаление дублей, остается по одному элементу remove() - удаление элементов 4) Контейнер vector библиотеки STL с объектами базового и производного классов В контейнер помещаются объекты классов Record и Sprint ...... // базовый класс должен быть полиморфным, т.е. должна быть по крайней мере одна виртуальная функция class Record { ....... virtual void Display(); // виртуальная функция ..... }; ..... class Sprint:public Record { .... void Display(); // перегрузка виртуальной функции ...... }; ...... в main: vector v; // контейнер для Record и Sprint (указатели базового класса!) // динамические объекты для заполнения. Record *R; Sprint *S; R= new Record; S=new Sprint; R=new Record(3,25); v.push_back(R); S=new Sprint(2,11,7); v.push_back(S); R=new Record(1,4); v.push_back(R); S=new Sprint(1,10,3); v.push_back(S); // В контейнере 2 Record и 2 Sprint vector::iterator ir; for (ir=v.begin(); ir != v.end(); ++ir) { (*ir)->Display(); } Display - виртуальная, вывод для каждого типа свой: 3 25 2 11 7 1 4 1 10 3 Вычислить количество объектов в контейнере типа Sprint. Для определения типа объекта метод TypeId не подходит, результат всегда будет Record. int Nsprint=0; for (ir=v.begin(); ir != v.end(); ++ir) { if (dynamic_cast(*ir)) // Sprint ? Nsprint++; } dynamic_cast - динамическое (безопасное приведение типа) от базового полиморфного к производному. // if (dynamic_cast(*ir)) объект приводится к Sprint ? 4) Контейнер map библиотеки STL На Java аналог называется HashSet (Хеш таблицы), на C# Hashtable или Dictionary. Пример Хеш таблиц. Имеются данные о пациентах поликлиники. В массиве хранятся ФИО и номер страхового свидетельства (СС). СС – 11 цифр, две последние – функция от первых 9. Петров 547654319 Иванов 687654578 .............................. Варианты хранения данных. а) Добавление к концу списка. Последовательный поиск по СС, в среднем проверять N/2 элементов. Удаление – сдвиг части массива (в цикле много операций). б) Упорядочивание по СС. Бинарный поик по СС – быстрый вариант. Добавка элемента – сдвиг массива (много операций в цикле). В базах данных обычно несколько индексов – уупорядочивают по СС, ФИО и т.д. для быстрого поиска. в) Хеширование. Пусть емкость массива всего 1000 элементов. Ближайшее простое число 997. Вначале массив пуст. --------- 000000000 // 0 --------- 000000000 // 1 .............................. --------- 000000000 // 997 Добавление элемента. Иванов 253456371 K=253456371 % 997. – остаток от деления. K-номер элемента массива для занесения информации. Пусть K=281. --------- 000000000 // 1 .............................. Иванов 253456371 // 281 .............................. При поиске номер проверяемого элемента вычисляется: K=CC % 997. Коллизия – два номера СС дают одинаковый остаток от деления. Петров 464597349 K=CC % 997= 281. --------- 000000000 // 1 .............................. Иванов 253456371 // 281 Элемент занят! СС не нулевой. .............................. В этом случае можно попытаться занести на 282, если занят на 283 и т.д. K – ключ к хеш таблице, K=CC % 997 – метод хеширования. В контейнерах и коллекциях ключ и метод подобраны с минимальным числом коллизий. Dictionary – словарь. Слово – ключ, а в контейнере – определение слова (как в энциклопедии). 5) Коллекции на Java Типы классов коллекций ArrayList - динамический массив , аналог Vector для C++ LinkedList - двусвязный список AbstractSet – Множество (Объединение, пересечение и т.д.) EnumSet - перечисление HashSet - Хэш таблицы TreeSet - организация данных в виде дерева Пример использования ArrayList. Коллекция может содержать элементы различных типов, в отличие от контейнеров C++ package javaapplication1; import java.util.*; public class lab9_1 { public static void main(String[] args) { ArrayList a=new ArrayList(); a.add(1); a.add("qwerty"); a.add(3); a.add(2.5); a.add(3); a.add(5); int k; k=a.size(); // k=6 System.out.println(a); // 1, qwerty, 3, 2.5, 3, 5 a.remove(2.5); // удаление по значению элемента a.remove(0); // удаление по номеру элемента System.out.println(a); // qwerty, 3, 3, 5 } } Итератор Пример использования итераторов package javaapplication1; import java.util.*; public class lab9_1 { public static void main(String[] args) { ArrayList a=new ArrayList(); a.add(1); a.add("qwerty"); a.add(3); a.add(2.5); a.add(3); a.add(5); a.remove(2.5); a.remove(0); int s; String gc; s=0; Iterator ir=a.iterator(); // итератор для коллекции a while(ir.hasNext()) // пока есть следующий элемент { Object el=ir.next(); // e1 - следующий элемент коллекции gc=el.getClass().getSimpleName(); // тип очередного объекта коллекции if(gc.equals("Integer")) // если объект - целое число s+=Integer.valueOf(el.toString()); // перевод Object ->String->int } System.out.println(s); // s=11 } } Пример коллекции с объектами разных типов Record и Sprint. package lab9_1; import java.util.ArrayList; import java.util.Iterator; class Record { protected int min,sec; public void Init(int m,int s) { min=m; sec=s; } int Numbersec() { return 60*min+sec; } } class Sprint extends Record { private int dec; public int Numbersec() { int k=60*min+sec; if(dec>=5) return k+1; else return k; } public void Init(int m,int s,int d) { super.Init(m, s); dec=d; } } public class lab9 { public static void main(String[] args) { ArrayList b=new ArrayList(); Record r=new Record(); Sprint s=new Sprint(); s.Init(2, 5,7); b.add(s); r.Init(3, 7); b.add(r); s.Init(2, 5,4); b.add(s); r.Init(3, 9); b.add(r); int k=0; // количество объектов класса Sprint String gc; Iterator ik=b.iterator(); while(ik.hasNext()) // пока есть следующий элемент { Object el=ik.next(); gc=el.getClass().getSimpleName(); if(gc.equals("Sprint")) k++; } System.out.println(k); // k=2 } } Коллекции одного типа String sss; sss=""; ArrayList a1=new ArrayList (); // - все объекты String a1.add("111"); a1.add("222"); a1.add("333"); a1.remove(1); Iterator itr=a1.iterator(); // итератор a1 типа String while(itr.hasNext()) { String e1=itr.next(); sss=sss+e1; // сцепление строк - нет перевода Object в String } System.out.println(sss); // sss -> 111333 Возможен вариант без итераторов sss = ""; for (int i = 0; i < a1.size(); i++) { sss = sss + a1.get(i) ; } Пример сортировки по условию. В коллекции из строк упорядочить строки по убыванию трех последних символов package javaapplication1; import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; class MyString implements Comparable // класс строк перегрузка сравнения { private String name; MyString() // конструктор без параметров { } MyString(String n) // конструктор с параметром { name = n; } public String getName() { return name; } public int compareTo(MyString d) // перегрузка метода сравнения { int k,k1,k2; String s1,s2; k1=this.name.length(); k2=d.name.length(); s1=this.name.substring(k1-3); // последние 3 символа s2=d.name.substring(k2-3); k=s1.compareTo(s2); if(k>0) // если слева больше, return -1; // то ответ - меньше, переставлять не нужно else return 1; } } public class lab9_3 { public static void main(String[] args) { ArrayList a = new ArrayList(); a.add(new MyString("qwerty333")); a.add(new MyString("asd111")); a.add(new MyString("zx222")); Collections.sort(a); // сортировка по int compareTo(MyString d) MyString f=new MyString(); for (int i = 0; i < a.size(); i++) { f=(MyString)a.get(i); System.out.println(f.getName()); } } } Вывод: qwerty333 zx222 asd111 Возможен вариант с компаратором (Comparator) с перегрузкой compare class MyString implements Comparator ............ public int compare(MyString d, MyString d1) { ............ 6)Коллекции на C# Типы коллекций. ArrayList — представляет из себя упорядоченную коллекцию объектов, доступ к которым можно получить, используя индекс, т.е. это аналог массива. Hashtable — Хеш таблицы SortedList — представляет из себя нечто среднее между ArrayList и Hashtable, обладая двумя сортируемыми массивами: ключей и значений. BitArray — представляет из себя вариант коллекции ArrayList для хранения значений битов. Queue — реализует структуру, называемую очередью. В этой структуре к элементам осуществляется доступ по принципу «первый пришел, первый ушел». Stack — реализует структуру, называемую стеком, В этой структуре к элементам осуществляется доступ по принципу «первый пришел, последним ушел». Необобщенные коллекции позволяют хранить элементы любого типа. Все переводятся в тип Object. ArrayList - аналог массива с переменной правой границей. using System; using System.Collections; using System.Linq; using System.Text; namespace NongenericCollections // необобщенные коллекции { class Program { static void Main(string[] args) { ArrayList one = new ArrayList(); // размер массива не указан тип не указан // ArrayList one = new ArrayList(10); // вариант сначала 10 элементов one.Add(1); // добавка элементов one.Add(3); one.Add(5); int m, i; m = one.Count; // количество элементов m=3 int Sum = 0; for (i = 0; i < one.Count; i++) { Sum = Sum + (int)one[i]; // не типизирован, требуется перевод из Object в int } } } } другие методы. one.Insert(1, 5); // перед первым элеметом коллекции one[1] = 7; // задание значения элементу коллекции one[2]="qwerty"; // задание элементу другого типа (string) m = (int)one[1]; // m=7 преобразование в int ! string s; s = (string)one[2]; m=one.IndexOf(7); // m=1 m=one.IndexOf("qwerty"); // m=2 one.RemoveAt(1); // 7 удалена one.Remove("qwerty"); // удалена qwerty one.Clear(); // очистка Сам объект one не удаляется! Пример коллекций с объектами базового и производного классов using System; using System.Collections; using System.Linq; using System.Text; namespace NongenericCollections // необобщенные коллекции { class Record { protected int min, sec; public void Init(int m, int s) { min = m; sec = s; } public int Numbersec() { return min * 60 + sec; } }; class Sprint : Record { private int dec; public void Init(int m, int s,int d) { base.Init(m, s); dec = d; } public int Numbersec() // перегруженная функция { int k; k=min * 60 + sec; if (dec >= 5) k++; return k; } }; class Program { static void Main(string[] args) { ArrayList two = new ArrayList(); int a, b,c,i; Random x = new Random(); // x - случайное число for (i = 0; i < 10; i++) { a = x.Next(2); // x= 0 или 1 if (a == 0) { // генерация Record a = x.Next(3); // 0-2 min b = x.Next(60); // 0-59 sec Record p = new Record(); p.Init(a, b); two.Add(p); } else { // генерация Sprint a = x.Next(3); // 0-2 min b = x.Next(60); // 0-59 sec c = x.Next(10); // 0-9 dec Sprint q = new Sprint(); q.Init(a, b, c); two.Add(q); } } string s; // определение сколько объектов Sprint в коллекции int KolS; KolS = 0; for (i = 0; i < 10; i++) { System.Type type = two[i].GetType(); // извлечение типа объекта s = type.Name; // имя типа if (s == "Sprint") KolS++; } } } } Сумма всех секунд в коллекции Numbersec перегружена class Record { protected int min, sec; public void Init(int m, int s) { min = m; sec = s; } virtual public int Numbersec() // функция виртуальная { return min * 60 + sec; } }; class Sprint : Record { private int dec; public void Init(int m, int s,int d) { base.Init(m, s); dec = d; } public override int Numbersec() { int k; k=min * 60 + sec; if (dec >= 5) k++; return k; } }; ..... int Sum; Sum = 0; foreach (Record k in two) { Sum = Sum + k.Numbersec(); // сумма sec у 10 элементов коллекции } Numbersec - виртуальная - в зависимости от типа объекта высисление по базовому или производному классу. Если функция Numbersec не виртуальная, (virtual, override убраны), то в варианте: int Sum; Sum = 0; Record d; for (i = 0; i < two.Count; i++) { d = (Record)two[i]; // все Sprint --> Record Sum = Sum + d.Numbersec(); // вычисления по Record } вычисления только Numbersec по классу Record. Сортировка. Упорядочить объекты по значению Numbersec class Record: IComparable, IComparer // интерфейсы { protected int min, sec; public void Init(int m, int s) { min = m; sec = s; } public int Numbersec() { return min * 60 + sec; } public int Compare(Object x0, Object y0) // сравнение 2 объектов { string s; int t1, t2; Record a; a = (Record)x0; t1 = a.Numbersec(); a = (Record)y0; t2 = a.Numbersec(); if (t1 < t2) return -1; else return 1; } public int CompareTo(Object x) { return Compare(this, x); } }; ........ IComparer Comp = new Record(); two.Sort(Comp); Вариант сортировки: вначале все Record, затем Sprint. Метод Display виртуальный. class Record: IComparable, IComparer { ......... virtual public void Display() { Console.Write(min); Console.Write(" "); Console.WriteLine(sec); } ....... public int Compare(Object x0, Object y0) { string s; int t1, t2; System.Type type = x0.GetType(); s = type.Name; if (s == "Sprint") t1 = 1; else t1 = 0; type = y0.GetType(); s = type.Name; if (s == "Sprint") t2 = 1; else t2 = 0; if (t1 == 0 && t2 == 1) return -1; // если x0-Record, y0-Sprint только тогда меньше! else return 1; } ........ class Sprint : Record { ...... public override void Display() { Console.Write(min); Console.Write(" "); Console.Write(sec); Console.Write(" "); Console.WriteLine(dec); } ...... static void Main(string[] args) { ...... IComparer Comp = new Record(); two.Sort(Comp); foreach (Record k in two) { k.Display(); } ..... на консоли: 10 значений до сортировки вперемешку 0 3 0 52 7 ..... 1 22 10 значений - сначала Record, потом Sprint 0 3 2 11 .... 1 22 0 52 7 ..... 1 22 8 2) Обобщенные коллекции на C#. Типы обобщенных коллекций: обобщенная - аналог необобщенная List - ArrayList LinkedList - программно // Список! Queue - Queue Stack - Stack Dictionary - Hashtable - шаблон для размещения реального типа. Обобщенная коллекция абстрактна для реальной коллекции требуется инициализация конкретным типом. В реализациях элементы конкретной коллекции могут быть одного типа. Пример. 2 реализации обобщенной коллекции List - коллекция Record и коллекция int. Вычисляется сумма количества секунд. using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace GenericCollections // обобщенные коллекции { class Record { private int min, sec; public void Init(int m, int s) { min = m; sec = s; } public int Numbersec() { return min * 60 + sec; } }; class Program { static void Main(string[] args) { List one = new List(); // коллекция из Record int a, b, i; Random x = new Random(); // случайное число for (i = 0; i < 10; i++) { a = x.Next(2); // случайное число 0-1 b = x.Next(60); // случайное число 0-59 Record z = new Record(); z.Init(a, b); // min, sec - случайные one.Add(z); // добавка в коллекцию } List two = new List(); // коллекция из целых чисел int m; foreach (Record k in one) { m = k.Numbersec(); two.Add(m); // заполнение коллекции из числа секунд объектов Record } int Sum = 0; foreach (int k in two) { Sum = Sum + k; // общее количество секунд у всех участников } } } } Пример сортировки коллекции целых чисел с помощью компаратора. Расположить вначале четные числа в коллекции, затем нечетные. using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace GenericCollections { public class IntComparer : IComparer // компаратор для целых чисел { public int Compare(int x, int y) // сравнение целых чисел { if (x % 2 == 0 && y % 2 == 1) // если слева четное, справа нет менять не нужно return -1; else return 1; } } class Program { static void Main(string[] args) { IntComparer ic = new IntComparer(); List two = new List(); two.Add(2); two.Add(7); two.Add(3); two.Add(6); two.Add(8); two.Add(1); two.Sort(ic); // сортировка по компаратору - 8 2 6 3 7 1 } } }