#pragma once

#include <functional>
#include <memory>
#include <utility>
#include <type_traits>
#include <vector>

namespace fefu
{//load factor == 0.5

	template<typename T>
	class allocator {
	public:
		using size_type = std::size_t;
		using difference_type = std::ptrdiff_t;
		using pointer = T*;
		using const_pointer = const T*;
		using reference = typename std::add_lvalue_reference<T>::type;
		using const_reference = typename std::add_lvalue_reference<const T>::type;
		using value_type = T;

		allocator() noexcept = default;

		allocator(const allocator&) noexcept = default;

		template <class U>
		allocator(const allocator<U>&) noexcept {

		}

		~allocator() {

		}

		pointer allocate(size_type size) {
			auto p = :: operator new (size * sizeof(value_type));
			return static_cast<pointer>(p);
		}

		void deallocate(pointer p, size_type n) noexcept {
			::operator delete(p, n);
		}
	};

	template<typename ValueType>
	class hash_map_iterator {
	public:
		using iterator_category = std::forward_iterator_tag;
		using value_type = ValueType;
		using difference_type = std::ptrdiff_t;
		using reference = ValueType&;
		using pointer = ValueType*;

		hash_map_iterator() noexcept {

		}
		hash_map_iterator(const hash_map_iterator& other) noexcept : data(other.data), m_set(other.m_set), pos(other.pos){

		}

		reference operator*() const {
			return &data + pos;//ссылка
		}
		pointer operator->() const {
			return data + pos;
		}

		// prefix ++
		hash_map_iterator& operator++() {
			size_t i = pos;
			while (m_set[i] != 1 && pos < m_set->size()) {
				i++;
			}
			pos = i;
			return *this;
		}
		// postfix ++
		hash_map_iterator operator++(int) {
			hash_map_iterator tmp = *this;
			++(*this);
			return tmp;
		}

		friend bool operator==(const hash_map_iterator<ValueType>& first, const hash_map_iterator<ValueType>& second) {
			if (first.pos == second.pos) {
				return true; //сравнить дату и вектор
			}
			return false;
		}
		friend bool operator!=(const hash_map_iterator<ValueType>& first, const hash_map_iterator<ValueType>& second) {
			if (first.pos != second.pos) {
				return true;
			}
			return false;
		}


		template<typename, typename, typename, typename, typename>
			friend class hash_map;

	private:
		hash_map_iterator(value_type* cell, std::vector<int>* set, size_t p) : data(cell), m_set(set), pos(p){

		}
		value_type* data;
		std::vector<int>* m_set;
		size_t pos;
	};

	template<typename ValueType>
	class hash_map_const_iterator {
		// Shouldn't give non const references on value
	public:
		using iterator_category = std::forward_iterator_tag;
		using value_type = ValueType;
		using difference_type = std::ptrdiff_t;
		using reference = const ValueType&;
		using pointer = const ValueType*;

		hash_map_const_iterator() noexcept;
		hash_map_const_iterator(const hash_map_const_iterator& other) noexcept;
		hash_map_const_iterator(const hash_map_iterator<ValueType>& other) noexcept;

		reference operator*() const;
		pointer operator->() const;

		// prefix ++
		hash_map_const_iterator& operator++();
		// postfix ++
		hash_map_const_iterator operator++(int);

		friend bool operator==(const hash_map_const_iterator<ValueType>&, const hash_map_const_iterator<ValueType>&);
		friend bool operator!=(const hash_map_const_iterator<ValueType>&, const hash_map_const_iterator<ValueType>&);
	};
	template<typename K, typename T,
		typename Hash = std::hash<K>,
		typename Pred = std::equal_to<K>,
		typename Alloc = allocator<std::pair<const K, T>>>
		class hash_map
	{
	public:
		using key_type = K;
		using mapped_type = T;
		using hasher = Hash;
		using key_equal = Pred;
		using allocator_type = Alloc;
		using value_type = std::pair<const key_type, mapped_type>;
		using reference = value_type&;
		using const_reference = const value_type&;
		using iterator = hash_map_iterator<value_type>;
		using const_iterator = hash_map_const_iterator<value_type>;
		using size_type = std::size_t;

		/// Default constructor.
		hash_map() = default;

		/**
		 *  @brief  Default constructor creates no elements.
		 *  @param n  Minimal initial number of buckets.
		 */
		explicit hash_map(size_type n) : allocator(), m_data(allocator.allocate(n)), vec(n, 0), m_size(n), max_load(0.5), current_load(0) {} //done

		/**
		 *  @brief  Builds an %hash_map from a range.
		 *  @param  first  An input iterator.
		 *  @param  last  An input iterator.
		 *  @param  n  Minimal initial number of buckets.
		 *
		 *  Create an %hash_map consisting of copies of the elements from
		 *  [first,last).  This is linear in N (where N is
		 *  distance(first,last)).
		 */
		template<typename InputIterator>
		hash_map(InputIterator first, InputIterator last,
			size_type n = 0);

		/// Copy constructor.
		hash_map(const hash_map& hash) : allocator(hash.allocator), m_hash(hash.m_hash), m_key_equal(hash.m_key_equal),
		m_data(allocator.allocate(hash.m_size)), m_size(hash.m_size), m_real_size(hash.m_real_size), vec(hash.vec),
		max_load(hash.max_load), current_load(hash.current_load){
			for (int i = 0; i < hash.m_size; i++) {
				if (vec[i] != 0) {
					m_data[i] = hash.m_data[i];
				}
			}
		}

		/// Move constructor.
		hash_map(hash_map&&);

		/**
		 *  @brief Creates an %hash_map with no elements.
		 *  @param a An allocator object.
		 */
		explicit hash_map(const allocator_type& a);

		/*
		*  @brief Copy constructor with allocator argument.
		* @param  uset  Input %hash_map to copy.
		* @param  a  An allocator object.
		*/
		hash_map(const hash_map& umap,
			const allocator_type& a);

		/*
		*  @brief  Move constructor with allocator argument.
		*  @param  uset Input %hash_map to move.
		*  @param  a    An allocator object.
		*/
		hash_map(hash_map&& umap,
			const allocator_type& a);

		/**
		 *  @brief  Builds an %hash_map from an initializer_list.
		 *  @param  l  An initializer_list.
		 *  @param n  Minimal initial number of buckets.
		 *
		 *  Create an %hash_map consisting of copies of the elements in the
		 *  list. This is linear in N (where N is @a l.size()).
		 */
		hash_map(std::initializer_list<value_type> l,
			size_type n = 0);

		/// Copy assignment operator.
		hash_map& operator=(const hash_map&);

		/// Move assignment operator.
		hash_map& operator=(hash_map&&);

		/**
		 *  @brief  %hash_map list assignment operator.
		 *  @param  l  An initializer_list.
		 *
		 *  This function fills an %hash_map with copies of the elements in
		 *  the initializer list @a l.
		 *
		 *  Note that the assignment completely changes the %hash_map and
		 *  that the resulting %hash_map's size is the same as the number
		 *  of elements assigned.
		 */
		hash_map& operator=(std::initializer_list<value_type> l);

		///  Returns the allocator object used by the %hash_map.
		allocator_type get_allocator() const noexcept {
			return allocator;
		}

		// size and capacity:

		///  Returns true if the %hash_map is empty.
		bool empty() const noexcept { //done
			for (int i = 0; i < vec.size(); i++) { //проверить просто переменную
				if (vec[i] == 1) {
					return false;
				}
			}
			return true;
		}

		///  Returns the size of the %hash_map.
		size_type size() const noexcept {
			return m_real_size;
		}

		///  Returns the maximum size of the %hash_map.
		size_type max_size() const noexcept {
			return INT_MAX;//std::numeric limits
		}

		// iterators.

		/**
		 *  Returns a read/write iterator that points to the first element in the
		 *  %hash_map.
		 */
		iterator begin() noexcept {
			for (int i = 0; i < m_size; i++) {
				if (vec[i] == 1) {
					return(iterator(m_data, &vec, i));
				}
			}
			return iterator();
		}

		//@{
		/**
		 *  Returns a read-only (constant) iterator that points to the first
		 *  element in the %hash_map.
		 */
		const_iterator begin() const noexcept;

		const_iterator cbegin() const noexcept;

		/**
		 *  Returns a read/write iterator that points one past the last element in
		 *  the %hash_map.
		 */
		iterator end() noexcept {
			return(iterator(m_data, &vec, m_size));
		}

		//@{
		/**
		 *  Returns a read-only (constant) iterator that points one past the last
		 *  element in the %hash_map.
		 */
		const_iterator end() const noexcept;

		const_iterator cend() const noexcept;
		//@}

		// modifiers.

		/**
		 *  @brief Attempts to build and insert a std::pair into the
		 *  %hash_map.
		 *
		 *  @param args  Arguments used to generate a new pair instance (see
		 *	        std::piecewise_contruct for passing arguments to each
		*	        part of the pair constructor).
		*
		*  @return  A pair, of which the first element is an iterator that points
		*           to the possibly inserted pair, and the second is a bool that
		*           is true if the pair was actually inserted.
		*
		*  This function attempts to build and insert a (key, value) %pair into
		*  the %hash_map.
		*  An %hash_map relies on unique keys and thus a %pair is only
		*  inserted if its first element (the key) is not already present in the
		*  %hash_map.
		*
		*  Insertion requires amortized constant time.
		*///Принимает аргумерты и создаем пару
		template<typename... _Args>
		std::pair<iterator, bool> emplace(_Args&&... args) {

		}

		/**
		 *  @brief Attempts to build and insert a std::pair into the
		 *  %hash_map.
		 *
		 *  @param k    Key to use for finding a possibly existing pair in
		 *                the hash_map.
		 *  @param args  Arguments used to generate the .second for a
		 *                new pair instance.
		 *
		 *  @return  A pair, of which the first element is an iterator that points
		 *           to the possibly inserted pair, and the second is a bool that
		 *           is true if the pair was actually inserted.
		 *
		 *  This function attempts to build and insert a (key, value) %pair into
		 *  the %hash_map.
		 *  An %hash_map relies on unique keys and thus a %pair is only
		 *  inserted if its first element (the key) is not already present in the
		 *  %hash_map.
		 *  If a %pair is not inserted, this function has no effect.
		 *
		 *  Insertion requires amortized constant time.
		 */
		template <typename... _Args> //move делает из чего-то rvalue на это что-то
		std::pair<iterator, bool> try_emplace(const key_type& k, _Args&&... args) {
			return insert({ k, mapped_type(std::forward<_Args>(args)...) }); //неправильно, загуглить как сдеать на cpp ref
		}

		// move-capable overload
		template <typename... _Args>//если в праметре шаблона 2 амп, то это универсальная ссылка, если нет в параметре шаблона, то это не унивирсальная
		std::pair<iterator, bool> try_emplace(key_type&& k, _Args&&... args) {
			return insert({ std::move(k),  mapped_type(std::forward<_Args>(args)...) });
		}

		//@{
		/**
		 *  @brief Attempts to insert a std::pair into the %hash_map.
		 *  @param x Pair to be inserted (see std::make_pair for easy
		 *	     creation of pairs).
		*
		*  @return  A pair, of which the first element is an iterator that
		*           points to the possibly inserted pair, and the second is
		*           a bool that is true if the pair was actually inserted.
		*
		*  This function attempts to insert a (key, value) %pair into the
		*  %hash_map. An %hash_map relies on unique keys and thus a
		*  %pair is only inserted if its first element (the key) is not already
		*  present in the %hash_map.
		*
		*  Insertion requires amortized constant time.
		*/
		std::pair<iterator, bool> insert(const value_type& x) {

			//value_type это пара ключ-значение
			//написать вспомогательные функции для ячейки по ключу и функция вставки
			const size_type index = m_hash(x.first) % vec.size(); //Ищем индекс
			for (int i = index; i < m_size; i++) {
				if (vec[i] == 1 && m_data[i].first == x.first) {
					return std::pair<iterator, bool>(iterator(), false);//такой элемент уже есть
				}
				if (vec[i] == 0) {
					new(m_data + i) value_type{ x.first, x.second };//Иначе создаем
					vec[i] = 1;
					m_real_size++;
					return std::pair<iterator, bool>(iterator(m_data, &vec, i), true);//возвращаемся элемент
				}
				else if (vec[i] == 2 && m_data[i].first == x.first) {
					m_data[i].second = x.second;
					vec[i] = 1;
					m_real_size++;
					return std::pair<iterator, bool>(iterator(m_data, &vec, i), true);//возвращаемся элемент
				}

			}
			for (int i = 0; i < index; i++) {
				if (vec[i] == 1 && m_data[i].first == x.first) {
					return std::pair<iterator, bool>(iterator(), false);//такой элемент уже есть
				}

				if (vec[i] == 0) {
					new(m_data + i) value_type{ x.first, x.second };//Иначе создаем
					vec[i] = 1;
					m_real_size++;
					return std::pair<iterator, bool>(iterator(m_data, &vec, i), true);//возвращаемся элемент
				}
				else if (vec[i] == 2 && m_data[i].first == x.first) {
					m_data[i].second = x.second;
					vec[i] = 1;
					m_real_size++;
					return std::pair<iterator, bool>(iterator(m_data, &vec, i), true);//возвращаемся элемент
				}
			}
			return std::pair<iterator, bool> (iterator(), false );

			//еще нужен рехэш
		}

		std::pair<iterator, bool> insert(value_type&& x) {
			const size_type index = m_hash(x.first) % vec.size(); //Ищем индекс
			int i = index;
			++i;
			/*while (i != index) { //вынести все ифы туда
				if (i == m_size) {
					i = 0;
				}
			}*/
			for (int i = index; i < m_size; i++) {
				if (vec[i] == 1 && m_data[i].first == x.first) {
					return std::pair<iterator, bool>(iterator(), false);//такой элемент уже есть
				}

				if (vec[i] == 0) {
					new(m_data + i) value_type{ std::move(x.first), std::move(x.second) };//Иначе создаем
					vec[i] = 1;
					m_real_size++;
					return std::pair<iterator, bool>(iterator(m_data, &vec, i), true);//возвращаемся элемент
				}
				else if (vec[i] == 2) {
					m_data[i].second = std::move(x.second);
					vec[i] = 1;
					m_real_size++;
					return std::pair<iterator, bool>(iterator(m_data, &vec, i), true);//возвращаемся элемент
				}

			}
			for (int i = 0; i < index; i++) {
				if (m_data[i].first == std::move(x.first)) {
					return { iterator(), false };//такой элемент уже есть
				}

				if (vec[i] != 1) {
					new(m_data + i) value_type{ std::move(x.first), std::move(x.second) };
					vec[i] = 1;
					m_real_size++;
					return std::pair<iterator, bool>(iterator(m_data, &vec, i), true);//возвращаем элемент
				}
				else if (vec[i] == 2) {
					m_data[i].second = std::move(x.second);
					vec[i] = 1;
					m_real_size++;
					return std::pair<iterator, bool>(iterator(m_data, &vec, i), true);//возвращаемся элемент
				}
			}
			return std::pair<iterator, bool>(iterator(), false);
		}


		/**
		 *  @brief A template function that attempts to insert a range of
		 *  elements.
		 *  @param  first  Iterator pointing to the start of the range to be
		 *                   inserted.
		 *  @param  last  Iterator pointing to the end of the range.
		 *
		 *  Complexity similar to that of the range constructor.
		 */
		template<typename _InputIterator>
		void insert(_InputIterator first, _InputIterator last) {
			for (auto i = first; i < last; i++) {
				insert(*i);
			}
		}

		/**
		 *  @brief Attempts to insert a list of elements into the %hash_map.
		 *  @param  l  A std::initializer_list<value_type> of elements
		 *               to be inserted.
		 *
		 *  Complexity similar to that of the range constructor.
		 */
		void insert(std::initializer_list<value_type> l);


		/**
		 *  @brief Attempts to insert a std::pair into the %hash_map.
		 *  @param k    Key to use for finding a possibly existing pair in
		 *                the map.
		 *  @param obj  Argument used to generate the .second for a pair
		 *                instance.
		 *
		 *  @return  A pair, of which the first element is an iterator that
		 *           points to the possibly inserted pair, and the second is
		 *           a bool that is true if the pair was actually inserted.
		 *
		 *  This function attempts to insert a (key, value) %pair into the
		 *  %hash_map. An %hash_map relies on unique keys and thus a
		 *  %pair is only inserted if its first element (the key) is not already
		 *  present in the %hash_map.
		 *  If the %pair was already in the %hash_map, the .second of
		 *  the %pair is assigned from obj.
		 *
		 *  Insertion requires amortized constant time.
		 */
		template <typename _Obj>
		std::pair<iterator, bool> insert_or_assign(const key_type& k, _Obj&& obj);

		// move-capable overload
		template <typename _Obj>
		std::pair<iterator, bool> insert_or_assign(key_type&& k, _Obj&& obj);

		//@{
		/**
		 *  @brief Erases an element from an %hash_map.
		 *  @param  position  An iterator pointing to the element to be erased.
		 *  @return An iterator pointing to the element immediately following
		 *          @a position prior to the element being erased. If no such
		 *          element exists, end() is returned.
		 *
		 *  This function erases an element, pointed to by the given iterator,
		 *  from an %hash_map.
		 *  Note that this function only erases the element, and that if the
		 *  element is itself a pointer, the pointed-to memory is not touched in
		 *  any way.  Managing the pointer is the user's responsibility.
		 */
		iterator erase(const_iterator position);

		// LWG 2059.
		iterator erase(iterator position) {
			if (vec[position.pos] == 1) {
				vec[position.pos] = 2;
				return iterator(m_data, &vec, position.pos - 1); // пробежать от индекса назади найти существующий элемент
			}
			return (end());
		}
		//@}

		/**
		 *  @brief Erases elements according to the provided key.
		 *  @param  x  Key of element to be erased.
		 *  @return  The number of elements erased.
		 *
		 *  This function erases all the elements located by the given key from
		 *  an %hash_map. For an %hash_map the result of this function
		 *  can only be 0 (not present) or 1 (present).
		 *  Note that this function only erases the element, and that if the
		 *  element is itself a pointer, the pointed-to memory is not touched in
		 *  any way.  Managing the pointer is the user's responsibility.
		 */
		size_type erase(const key_type& x) {
			const size_type index = m_hash(x) % vec.size(); //Ищем индекс
			int i = index;
			while(i < m_size && vec[i] != 0) { //один цикл
				if (vec[i] == 1 && m_data[i].first == x) {
					vec[i] = 2;
					m_real_size--;
					return 1;
				}
				i++;
			}

			if (i == m_size) {
				i = 0;
				while(i < index) {
					if (vec[i] == 1 && m_data[i].first == x) {
						vec[i] = 2;
						m_real_size--;
						return 1;
					}
					i++;
				}
			}
			return 0;
		}

		/**
		 *  @brief Erases a [first,last) range of elements from an
		 *  %hash_map.
		 *  @param  first  Iterator pointing to the start of the range to be
		 *                  erased.
		 *  @param last  Iterator pointing to the end of the range to
		 *                be erased.
		 *  @return The iterator @a last.
		 *
		 *  This function erases a sequence of elements from an %hash_map.
		 *  Note that this function only erases the elements, and that if
		 *  the element is itself a pointer, the pointed-to memory is not touched
		 *  in any way.  Managing the pointer is the user's responsibility.
		 */
		iterator erase(const_iterator first, const_iterator last) {
			for (auto i = first; i < last; i++) {
				if (vec[i.pos] == 1) {
					vec[i.pos] = 2;
				}
			}
		}

		/**
		 *  Erases all elements in an %hash_map.
		 *  Note that this function only erases the elements, and that if the
		 *  elements themselves are pointers, the pointed-to memory is not touched
		 *  in any way.  Managing the pointer is the user's responsibility.
		 */
		void clear() noexcept {
			for (int i = 0; i < m_size; i++) {
				if (vec[i] == 1) {
					vec[i] = 2;
					m_real_size--; //вынести
				}
			}
		}

		/**
		 *  @brief  Swaps data with another %hash_map.
		 *  @param  x  An %hash_map of the same element and allocator
		 *  types.
		 *
		 *  This exchanges the elements between two %hash_map in constant
		 *  time.
		 *  Note that the global std::swap() function is specialized such that
		 *  std::swap(m1,m2) will feed to this function.
		 */
		void swap(hash_map& x) {

		}

		template<typename _H2, typename _P2>
		void merge(hash_map<K, T, _H2, _P2, Alloc>& source);

		template<typename _H2, typename _P2>
		void merge(hash_map<K, T, _H2, _P2, Alloc>&& source);

		// observers.

		///  Returns the hash functor object with which the %hash_map was
		///  constructed.
		Hash hash_function() const {
			return m_hash;
		}

		///  Returns the key comparison object with which the %hash_map was
		///  constructed.
		Pred key_eq() const {
			m_key_equal;
		}

		// lookup.

		//@{
		/**
		 *  @brief Tries to locate an element in an %hash_map.
		 *  @param  x  Key to be located.
		 *  @return  Iterator pointing to sought-after element, or end() if not
		 *           found.
		 *
		 *  This function takes a key and tries to locate the element with which
		 *  the key matches.  If successful the function returns an iterator
		 *  pointing to the sought after element.  If unsuccessful it returns the
		 *  past-the-end ( @c end() ) iterator.
		 */
		iterator find(const key_type& x) {
			const size_type index = m_hash(x) % vec.size(); //Ищем индекс
			int i = index;
			while(vec[i] != 0 && i < m_size) {
				if (vec[i] == 1 && m_data[i].first == x) {
					return iterator(m_data, &vec, i);//ИТЕРАТОР
				}
				i++;
			}
			if (i == m_size) {
				i = 0;
				while (vec[i] != 0) {
					if (vec[i] == 1 && m_data[i].first == x) {
						return iterator(m_data, &vec, i);//ИТЕРАТОР
					}
					i++;
				}
			}
			return end();//ИТЕРАТОР
		}

		const_iterator find(const key_type& x) const;
		//@}

		/**
		 *  @brief  Finds the number of elements.
		 *  @param  x  Key to count.
		 *  @return  Number of elements with specified key.
		 *
		 *  This function only makes sense for %unordered_multimap; for
		 *  %hash_map the result will either be 0 (not present) or 1
		 *  (present).
		 */
		size_type count(const key_type& x) const {
			const size_type index = m_hash(x) % vec.size(); //Ищем индекс
			int i = index;
			while(vec[i] != 0 && i < m_size) {
				if (vec[i] == 1 && m_data[i].first == x) {
					return 1;
				}
				i++;
			}

			if (i == m_size) {
				i = 0;
				while (i != index) {
					if (vec[i] == 1 && m_data[i].first == x) {
						return 1;
					}
					i++;
				}
			}

			return 0;
		}

		/**
		 *  @brief  Finds whether an element with the given key exists.
		 *  @param  x  Key of elements to be located.
		 *  @return  True if there is any element with the specified key.
		 */
		bool contains(const key_type& x) const {
			return count(x);
		}

		//@{
		/**
		 *  @brief  Subscript ( @c [] ) access to %hash_map data.
		 *  @param  k  The key for which data should be retrieved.
		 *  @return  A reference to the data of the (key,data) %pair.
		 *
		 *  Allows for easy lookup with the subscript ( @c [] )operator.  Returns
		 *  data associated with the key specified in subscript.  If the key does
		 *  not exist, a pair with that key is created using default values, which
		 *  is then returned.
		 *
		 *  Lookup requires constant time.
		 */
		mapped_type& operator[](const key_type& k) {
			//const size_type h = m_hash(k); //считаем хэш
			const size_type index = m_hash(k) % vec.size(); //Ищем индекс
			for (int i =index; i < m_size; i++) {
				if (vec[i] == 1 && m_data[i].first == k) { //Если создана
					return m_data[i].second;
				}
				else if (vec[i] == 2 && m_data[i].first == k) {
					m_data[i].second = mapped_type{};
					m_real_size++;
					return m_data[i].second;
				}
				else if (vec[i] == 0){
					new(m_data + i) value_type{ k, mapped_type{} };//Иначе создаем
					vec[i] = 1;
					m_real_size++;
					return m_data[i].second;
				}
			}
			for (int i = 0; i < index; i++) {
				if (vec[i] == 1 && m_data[i].first == k) { //Если создана
					return m_data[i].second;
				}
				else if (vec[i] == 2 && m_data[i].first == k) {
					m_data[i].second = mapped_type{};
					m_real_size++;
					return m_data[i].second;
				}
				else if (vec[i] == 0) {
					new(m_data + i) value_type{ k, mapped_type{} };//Иначе создаем
					vec[i] = 1;
					m_real_size++;
					return m_data[i].second;
				}
			}

		}

		mapped_type& operator[](key_type&& k) {
			(*this)[k]; // то же самое с мувами
		}
		//@}

		//@{
		/**
		 *  @brief  Access to %hash_map data.
		 *  @param  k  The key for which data should be retrieved.
		 *  @return  A reference to the data whose key is equal to @a k, if
		 *           such a data is present in the %hash_map.
		 *  @throw  std::out_of_range  If no such data is present.
		 */
		mapped_type& at(const key_type& k);

		const mapped_type& at(const key_type& k) const;
		//@}

		// bucket interface.

		/// Returns the number of buckets of the %hash_map.
		size_type bucket_count() const noexcept {
			return m_size;
		}

		/*
		* @brief  Returns the bucket index of a given element.
		* @param  _K  A key instance.
		* @return  The key bucket index.
		*/
		size_type bucket(const key_type& _K) const {
			const size_type index = m_hash(_K) % vec.size(); //Ищем индекс
			int i = index;
			while(vec[i] != 0 && i < m_size) {
				if (vec[i] == 1 && m_data[i].first == _K) {
					return i;
				}
				i++;
			}
			if (i == m_size) {
				i = 0;
				while (vec[i] != 0) {
					if (vec[i] == 1 && m_data[i].first == _K) {
						return i;
					}
					i++;
				}
			}

			return -1;
		}

		// hash policy.

		/// Returns the average number of elements per bucket.
		float load_factor() const noexcept {
			return current_load;
		}

		/// Returns a positive number that the %hash_map tries to keep the
		/// load factor less than or equal to.
		float max_load_factor() const noexcept {
			return max_load;
		}

		/**
		 *  @brief  Change the %hash_map maximum load factor.
		 *  @param  z The new maximum load factor.
		 */
		void max_load_factor(float z) {
			max_load = z;
			//перехешировать
		}

		/**
		 *  @brief  May rehash the %hash_map.
		 *  @param  n The new number of buckets.
		 *
		 *  Rehash will occur only if the new number of buckets respect the
		 *  %hash_map maximum load factor.
		 */
		void rehash(size_type n) {
			//как-то память снова выделить
		}

		/**
		 *  @brief  Prepare the %hash_map for a specified number of
		 *          elements.
		 *  @param  n Number of elements required.
		 *
		 *  Same as rehash(ceil(n / max_load_factor())).
		 */
		void reserve(size_type n);

		bool operator==(const hash_map& other) const {
			if (vec == other.vec && m_size == other.m_size && m_real_size == other.m_real_size ) {
				for (int i = 0; i < m_size; i++) {
					if (vec[i] == 1) {
						if (m_data[i] != other.m_data[i]) {
							return false;
						}
					}
				}
				return true;
			}
			return false;
		}

	private:
		allocator_type allocator;
		hasher m_hash;
		key_equal m_key_equal;
		value_type* m_data;
		size_type m_size;
		size_type m_real_size;
		std::vector <int> vec;
		const float max_load;
		float current_load;
	};



} // namespace fefu