70.1.6. КОЛЛЕКЦИИ

 
  THIS SECTION IS UNDER CONSTRUCTION  
 




Коллекции  --+---- Линейные ----+--- с индексным ---+--- Cловарь
	     |                  |    доступом	    +--- Hash таблица
	     |                  |    
	     |                  +--- с прямым  ----+---- Массив
	     |			|    доступом      +---- Структура
	     |			|		   +---- Файл
	     |		        |
	     |			+-- с последоват --+---- Файл
	     |			     доступом      +---- Список
	     |					   +---- Stack
             |					   +---- Очередь (Queue)
	     |					   +---- Очередь с приоритетами
	     |
	     +-- Нелинейные ---+-- Иерархические --+---- Дерево
	     		       |		   +---- Пирамида
	     		       |
			       +- Неиерархические -+---- Набор   (Set)
						   +---- Граф

  



	Списки
		Создать список
		Удалить список
			удалить все элементы в списке

		Добавить элемент в список 
			в начало
			в конец
			на указанную позицию

		Удалить элемент из списка
			указанный элемент
			первый элемент
			последний элемент

		Создать элемент списка
		Удалить элемент списка

		Взять Nй элемент из списка
		Итерационный обход списка
		Итерационный обход списка по признаку
			или с callback по элементам
				predicate
			
		Найти элемент в списке по признаку
			первый
			последний
			Nй



  
  Односвязный список 
 

  

  





  
  Двухсвязный список 
 

  


  

  




  
  Дека 
 

  

  




  




  
  Стек 
 
  




  
  FIFO 
 

  




  
  Skip List 
 

Skip List - список с пропусками
некоторые элементы содержат указатели сильно вперед.
(лучше делать двойной).

  




  
  Cyclic Buffer 
 

  





  
  Set 
 

  

  


Еще есть Multiset.



  
  Map 
 
  

  


Еще есть Multimap.

	Set/Multiset
	Map/Multimap
	Hash/Multihash
		то же что и для списка, но просто
		Добавить элемент
		Удалить  элемент
		Найти элемент по признаку




  
  Hash 
 

  


Функция хэширования для строк

	Hash = (Hash * 17 + char[i]) mod TableSize
	TableSize - лучше выбирать простое число

Функция Вайнбергера
	Loop
	{
		Hash = (Hash << 4) + char[i]
		G = Hash & 0xf0000000
		if (G != 0)
		{
			Hash = (Hash ^ (G >> 24)) ^ G
	}
	Hash = Hash mod TableSize





  
  Деревья 
 

  

  


Операции: сортировка поиск обход



  
  B-tree 
 

  


delete:
  


join:
  


move:
  


search:
  


split:
  






  
  B+tree 
 

  


  



Скошенные деревья
Красно-черные деревья