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

Контейнеры STL библиотеки. Коллекции на Java. 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 // использование контейнера 1 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(); // очистка контейнера 3 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 – вычисление модуля { 4 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" 5 #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); 6 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); // предикат - условие поиска 7 } ..... 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 ...... // базовый класс должен быть полиморфным, т.е. должна быть по крайней мере одна виртуальная функция 8 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. 9 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 10 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"); 11 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. 12 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); 13 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; 14 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); 15 System.out.println(f.getName()); } } } Вывод: qwerty333 zx222 asd111 Возможен вариант с компаратором (Comparator) с перегрузкой compare class MyString implements Comparator ............ public int compare(MyString d, MyString d1) { ............ 16