Line data Source code
1 : #ifndef VSET_VTREE_VTREE_HPP
2 : #define VSET_VTREE_VTREE_HPP
3 :
4 : #include <cstddef>
5 : #include <stdexcept>
6 : #include <map>
7 : #include <limits>
8 : #include <algorithm>
9 :
10 : #ifdef __GXX_EXPERIMENTAL_CXX0X__
11 : #include <type_traits>
12 : #endif
13 :
14 : #include <vset/vtree/vtree_iterator.hpp>
15 : #include <vset/vtree/aspect/tags.hpp>
16 : #include <vset/buffer/persistent/tags.hpp>
17 :
18 : #include <fas/aop.hpp>
19 : #include <fas/static_check/static_error.hpp>
20 :
21 : namespace vset{ namespace vtree{
22 :
23 : /// @cond ignore
24 : template<typename K, typename C>
25 : struct compare_pair
26 : {
27 : C _comp;
28 :
29 27 : compare_pair()
30 : : _comp()
31 27 : {}
32 :
33 2 : explicit compare_pair(C comp)
34 2 : : _comp(comp)
35 : {
36 2 : }
37 :
38 299648 : bool operator()(const K& first, const K& second) const
39 : {
40 : return _comp(first.first, second.first)
41 448947 : || ( !_comp(second.first, first.first)
42 448947 : && _comp(first.second, second.second) );
43 : }
44 : };
45 :
46 : /// @endcond
47 :
48 :
49 : /**
50 : @brief Базовый класс для vset::multiset реализующий основные его методы.
51 : @tparam A - аспект
52 : */
53 : template< typename A >
54 29 : class vtree:
55 : public fas::aspect_class<A>
56 : {
57 : typedef vtree<A> self;
58 : typedef fas::aspect_class<A> super;
59 : typedef typename super::aspect::template advice_cast<_allocator_>::type allocator_builder;
60 :
61 : typedef typename super::aspect::template advice_cast<_key_compare_>::type key_compare_tag;
62 : typedef typename super::aspect::template advice_cast<_value_compare_>::type value_compare_tag;
63 : typedef typename super::aspect::template advice_cast<_value_type_>::type value_type_tag;
64 : typedef typename super::aspect::template advice_cast<_key_type_>::type key_type_tag;
65 :
66 : typedef typename allocator_builder::template apply<self>::type allocator_type_tag;
67 : typedef typename allocator_type_tag::size_type size_type_tag;
68 : typedef typename allocator_type_tag::difference_type difference_type_tag;
69 :
70 : typedef std::pair<key_type_tag, key_type_tag> container_key_tag;
71 : typedef compare_pair<container_key_tag, key_compare_tag> container_comparator_tag;
72 :
73 : typedef typename super::aspect
74 : ::template advice_cast<_container_>::type
75 : ::template apply<
76 : container_key_tag,
77 : typename allocator_type_tag::pointer,
78 : container_comparator_tag
79 : >::type container_type_tag;
80 :
81 : typedef vtree_iterator<typename container_type_tag::iterator, value_type_tag> iterator_tag;
82 : typedef vtree_iterator<typename container_type_tag::const_iterator, const value_type_tag> const_iterator_tag;
83 : typedef std::reverse_iterator<iterator_tag> reverse_iterator_tag;
84 : typedef std::reverse_iterator<const_iterator_tag> const_reverse_iterator_tag;
85 :
86 : typedef typename std::iterator_traits<iterator_tag>::pointer pointer_tag;
87 : typedef typename std::iterator_traits<iterator_tag>::reference reference_tag;
88 : typedef typename std::iterator_traits<const_iterator_tag>::pointer const_pointer_tag;
89 : typedef typename std::iterator_traits<const_iterator_tag>::reference const_reference_tag;
90 : public:
91 :
92 : typedef key_compare_tag key_compare;
93 : typedef value_compare_tag value_compare;
94 : typedef value_type_tag value_type;
95 : typedef key_type_tag key_type;
96 :
97 : typedef allocator_type_tag allocator_type;
98 : typedef size_type_tag size_type;
99 : typedef difference_type_tag difference_type;
100 :
101 : typedef container_key_tag container_key;
102 : typedef container_comparator_tag container_comparator;
103 : typedef container_type_tag container_type;
104 :
105 : typedef iterator_tag iterator;
106 : typedef const_iterator_tag const_iterator;
107 : typedef reverse_iterator_tag reverse_iterator;
108 : typedef const_reverse_iterator_tag const_reverse_iterator;
109 :
110 : typedef pointer_tag pointer;
111 : typedef reference_tag reference;
112 : typedef const_pointer_tag const_pointer;
113 : typedef const_reference_tag const_reference;
114 :
115 :
116 : allocator_type _allocator;
117 : container_type _container;
118 :
119 : // если есть _open_file_ копирование недоступно
120 : struct copy_ctor_disabled_for_mapped_files;
121 :
122 : public:
123 :
124 : /**
125 : * @brief Конструктор по умолчанию. Создаёт пустой контейнер.
126 : */
127 25 : vtree()
128 25 : : _allocator( this->get_aspect().template get<_allocator_>()( *this ) )
129 50 : , _container()
130 : {
131 25 : }
132 :
133 : /**
134 : * @brief Конструктор создаёт пустой контейнер.
135 : * @param comp функции сравнения ключей
136 : * @param alloc функции сравнения ключей
137 : */
138 2 : explicit vtree(const key_compare& comp,const allocator_type& alloc = allocator_type() )
139 : : _allocator(alloc)
140 2 : , _container( container_comparator(comp) )
141 : {
142 2 : this->get_aspect().template get<_compare_>() = comp;
143 2 : _allocator = this->get_aspect().template get<_allocator_>()(*this);
144 2 : }
145 :
146 : /**
147 : * @brief Создаёт контейнер с содержимым из диапазона [first, last).
148 : * @param first итератор начала диапазона
149 : * @param last итератор конеца диапазона
150 : */
151 : template<typename InputIterator>
152 : vtree(InputIterator b, InputIterator e)
153 : : _allocator( this->get_aspect().template get<_allocator_>()(*this) )
154 : , _container()
155 : {
156 : this->insert(b, e);
157 : }
158 :
159 : /**
160 : * @brief Создаёт контейнер с содержимым из диапазона [first, last).
161 : * @param first итератор начала диапазона
162 : * @param last итератор конеца диапазона
163 : * @param comp функции сравнения ключей
164 : * @param alloc функции сравнения ключей
165 : */
166 : template<typename InputIterator>
167 : vtree(InputIterator b, InputIterator e, const value_compare& comp, const allocator_type& alloc = allocator_type() )
168 : : _allocator(alloc)
169 : , _container( container_comparator(comp) )
170 : {
171 : this->get_aspect().template get<_compare_>() = comp;
172 : _allocator = this->get_aspect().template get<_allocator_>()(*this);
173 : this->insert(b, e);
174 : }
175 :
176 : /**
177 : * @brief Конструктор копирования
178 : * @details Для персистентных контейнеров копирование запрещено
179 : */
180 1 : vtree(const self& __x)
181 1 : : _allocator( this->get_aspect().template get<_allocator_>()(*this) )
182 2 : , _container()
183 : {
184 : typedef typename fas::static_error<
185 : copy_ctor_disabled_for_mapped_files,
186 : super::aspect::template has_advice< ::vset::buffer::persistent::_open_file_ >::value == 0
187 : >::type error;
188 1 : this->dummy( error() );
189 1 : this->insert(__x.begin(), __x.end());
190 1 : }
191 :
192 :
193 : #ifdef __GXX_EXPERIMENTAL_CXX0X__
194 :
195 : /**
196 : * @brief Move-конструктор (c++11). Создает контейнер с содержимым other с использованием move-семантики.
197 : * Если alloc не был предоставлен, то он будет получен с помощью move-конструктора от аллокатора принадлежащего other.
198 : * @param other другой контейнер, который будет использован в качестве источника данных для инициализации элементов контейнера
199 : */
200 1 : vtree(vtree&& __x)
201 1 : {
202 1 : vtree tmp;
203 1 : this->swap(__x);
204 1 : }
205 :
206 : /**
207 : * @brief Создает контейнер с содержимым списка инициализации init (c++11).
208 : * @param init — список инициализации элементов контейнера
209 : * @param comp функции сравнения ключей
210 : * @param alloc функции сравнения ключей
211 : */
212 : vtree( std::initializer_list<value_type> il, const value_compare& comp = value_compare(), const allocator_type& alloc = allocator_type())
213 : : _allocator(alloc)
214 : , _container( container_comparator(comp) )
215 : {
216 : this->get_aspect().template get<_compare_>() = comp;
217 : _allocator = this->get_aspect().template get<_allocator_>()(*this);
218 : this->insert(il.begin(), il.end());
219 : }
220 :
221 : vtree&& clone(const value_compare& comp, const allocator_type& alloc = allocator_type()) const
222 : {
223 : return std::move(vtree( this->begin(), this->end(), comp, alloc));
224 : }
225 :
226 : #endif
227 :
228 : vtree& operator=(const vtree& __x)
229 : {
230 : vtree tmp(__x);
231 : this->swap(tmp);
232 : return *this;
233 : }
234 :
235 : #ifdef __GXX_EXPERIMENTAL_CXX0X__
236 :
237 : /**
238 : * @brief Заменяет содержимое содержимым other использованием семантики переноса (c++11)
239 : * @param other другой контейнер, который будет использоваться в качестве источника
240 : */
241 : vtree& operator=(vtree&& __x)
242 : {
243 : this->clear();
244 : this->swap(__x);
245 : return *this;
246 : }
247 :
248 : /**
249 : * @brief Заменяет содержимое элементами, которые указаны в списке идентификаторов инициализатора (c++11).
250 : * @param il список инициализации для использования в качестве источника данных
251 : */
252 : vtree& operator=( std::initializer_list<value_type> il)
253 : {
254 : this->clear();
255 : this->insert(il.begin(), il.end());
256 : return *this;
257 : }
258 : #endif
259 :
260 13 : const key_compare& key_comp() const
261 : {
262 13 : return this->get_aspect().template get<_key_compare_>();
263 : }
264 :
265 : const value_compare& value_comp() const
266 : {
267 : return this->get_aspect().template get<_value_compare_>();
268 : }
269 :
270 146 : allocator_type get_allocator() const
271 : {
272 146 : return _allocator;
273 : }
274 :
275 40 : const container_type& get_container() const
276 : {
277 40 : return _container;
278 : }
279 :
280 326326 : container_type& get_container()
281 : {
282 326326 : return _container;
283 : }
284 :
285 : /**
286 : * @brief Возвращает итератор на первый элемент контейнера.
287 : * @return итератор на первый элемент
288 : */
289 411 : iterator begin()
290 : {
291 411 : return iterator( _container.begin(), typename iterator::difference_type(0));
292 : }
293 :
294 : /**
295 : * @brief Возвращает итератор на элемент, следующий за последним элементом контейнера
296 : * @return итератор на элемент, следующий за последним элементом контейнера
297 : * @details Этот элемент выступает в качестве заполнителя; попытке доступа к нему приводит к неопределенному поведению
298 : */
299 74895 : iterator end()
300 : {
301 74895 : return iterator( _container.end(), typename iterator::difference_type(0) );
302 : }
303 :
304 : /**
305 : * @brief Возвращает константный итератор на первый элемент контейнера.
306 : * @return Константный итератор на первый элемент
307 : */
308 27 : const_iterator begin() const
309 : {
310 27 : return const_iterator( _container.begin(), 0);
311 : }
312 :
313 : /**
314 : * @brief Возвращает константный итератор на элемент, следующий за последним элементом контейнера
315 : * @return константный итератор на элемент, следующий за последним элементом контейнера
316 : * @details Этот элемент выступает в качестве заполнителя; попытке доступа к нему приводит к неопределенному поведению
317 : */
318 27 : const_iterator end() const
319 : {
320 27 : return const_iterator( _container.end(), 0 );
321 : }
322 :
323 : /**
324 : * @brief Возвращает обратный итератор на последний элемент контейнера.
325 : * @return обратный итератор на последний элемент
326 : */
327 : reverse_iterator rbegin()
328 : {
329 : return reverse_iterator( this->end() );
330 : }
331 :
332 : /**
333 : * @brief Возвращает обратный итератор на элемент, перед первым элементом контейнера
334 : * @return обратный итератор на элемент, перед первым элементом контейнера
335 : * @details Этот элемент выступает в качестве заполнителя; попытке доступа к нему приводит к неопределенному поведению
336 : */
337 : reverse_iterator rend()
338 : {
339 : return reverse_iterator( this->begin() );
340 : }
341 :
342 : /**
343 : * @brief Возвращает константный обратный итератор на последний элемент контейнера.
344 : * @return Константный обратный итератор на последний элемент
345 : */
346 : const_reverse_iterator rbegin() const
347 : {
348 : return const_reverse_iterator( this->end() );
349 : }
350 :
351 : /**
352 : * @brief Возвращает константный обратный итератор на элемент, следующий перед первым элементом контейнера
353 : * @return константный итератор обратный на элемент, следующий за последним элементом контейнера
354 : * @details Этот элемент выступает в качестве заполнителя; попытке доступа к нему приводит к неопределенному поведению
355 : */
356 : const_reverse_iterator rend() const
357 : {
358 : return const_reverse_iterator( this->begin() );
359 : }
360 :
361 : #ifdef __GXX_EXPERIMENTAL_CXX0X__
362 :
363 : /**
364 : * @brief Возвращает константный итератор на первый элемент контейнера (c++11).
365 : * @return Константный итератор на первый элемент
366 : */
367 : const_iterator cbegin() const
368 : {
369 : return const_iterator( _container.cbegin(), 0);
370 : }
371 :
372 : /**
373 : * @brief Возвращает константный итератор на элемент, следующий за последним элементом контейнера (c++11)
374 : * @return константный итератор на элемент, следующий за последним элементом контейнера
375 : * @details Этот элемент выступает в качестве заполнителя; попытке доступа к нему приводит к неопределенному поведению
376 : */
377 0 : const_iterator cend() const
378 : {
379 0 : return const_iterator( _container.cend(), 0 );
380 : }
381 :
382 : /**
383 : * @brief Возвращает константный обратный итератор на последний элемент контейнера (c++11).
384 : * @return Константный обратный итератор на последний элемент
385 : */
386 : const_reverse_iterator crbegin() const
387 : {
388 : return const_reverse_iterator( this->begin() );
389 : }
390 :
391 :
392 : /**
393 : * @brief Возвращает константный обратный итератор на элемент, следующий перед первым элементом контейнера (c++11)
394 : * @return константный итератор обратный на элемент, следующий перед первым элементом контейнера
395 : * @details Этот элемент выступает в качестве заполнителя; попытке доступа к нему приводит к неопределенному поведению
396 : */
397 : reverse_iterator crend() const
398 : {
399 : return const_reverse_iterator( this->end() );
400 : }
401 :
402 : #endif
403 :
404 : /**
405 : * @brief Проверка на отсутствие элементов в контейнере
406 : * @return true если контейнер пуст, false - в противном случае
407 : */
408 : bool empty() const
409 : {
410 : return _container.empty();
411 : }
412 :
413 : /**
414 : * @brief Возвращает количество элементов в контейнере
415 : * @return количество элементов в контейнере
416 : */
417 10638 : size_type size() const
418 : {
419 10638 : return this->get_aspect().template get<_size_>();
420 : }
421 :
422 : /**
423 : * @brief Возвращает максимально допустимое количество элементов в контейнере
424 : * @return Максимальное количество элементов.
425 : * @details Это значение обычно равно std::numeric_limits<size_type>::max(), и отражает теоретический предел на размер контейнера.
426 : * Ввиду ограничений на доступную оперативную память, во время исполнения это значение может быть ниже чем max_size().
427 : */
428 : size_type max_size() const
429 : {
430 : return std::numeric_limits<size_type>::max();
431 : }
432 :
433 : /**
434 : * @brief Обменивает содержимое контейнера с содержимым контейнера другого
435 : * @param other — Контейнер для обмена содержимым
436 : * @details The behavior is undefined if get_allocator() != other.get_allocator()
437 : * and std::allocator_traits<allocator_type>::propagate_on_container_swap::value != true.
438 : */
439 1 : void swap( vtree& other )
440 : {
441 1 : this->get_aspect().template get<_swap_container_>()(*this, other);
442 1 : _allocator = this->get_aspect().template get<_allocator_>()(*this);
443 1 : other._allocator = this->get_aspect().template get<_allocator_>()(other);
444 1 : }
445 :
446 : /**
447 : * @brief Возвращает количество элементов, которые могут одновременно храниться в выделенной области памяти
448 : * @return Вместимость контейнера, под которую в сейчас выделена память
449 : */
450 5 : size_t capacity() const
451 : {
452 5 : return this->get_aspect().template get<_capacity_>()(*this);
453 : }
454 :
455 : /**
456 : * @brief Вставляет элемент
457 : * @param value вставляемое значение
458 : * @return итератор на вставленный элемент
459 : * @details Сложность от O(log(size/t)) до O(log(size*4/t) + t)
460 : */
461 11262 : iterator insert(const value_type& value)
462 : {
463 11262 : return this->get_aspect().template get<_insert_value_>()(*this, value);
464 : }
465 :
466 :
467 : #ifdef __GXX_EXPERIMENTAL_CXX0X__
468 :
469 : /**
470 : * @brief Вставляет элемент (c++11)
471 : * @param value вставляемое значение
472 : * @return итератор на вставленный элемент
473 : * @details Сложность от O(log(size/t)) до O(log(size*4/t) + t)
474 : */
475 10094 : iterator insert(value_type&& value)
476 : {
477 10094 : return this->get_aspect().template get<_insert_value_>()(*this, value );
478 : }
479 :
480 : #endif
481 :
482 : /**
483 : * @brief Вставляет элемент
484 : * @param const_iterator игнорируеться
485 : * @param value вставляемое значение
486 : * @return итератор на вставленный элемент
487 : * @details Сложность от O(log(size/t)) до O(log(size*4/t) + t)
488 : */
489 : iterator insert(const_iterator, const value_type& value)
490 : {
491 : return this->get_aspect().template get<_insert_value_>()(*this, value );
492 : }
493 :
494 : #ifdef __GXX_EXPERIMENTAL_CXX0X__
495 : /**
496 : * @brief Вставляет элемент (c++11)
497 : * @param const_iterator игнорируеться
498 : * @param value вставляемое значение
499 : * @return итератор на вставленный элемент
500 : * @details Сложность от O(log(size/t)) до O(log(size*4/t) + t)
501 : */
502 : iterator insert(const_iterator, value_type&& value)
503 : {
504 : return this->get_aspect().template get<_insert_value_>()(*this, value );
505 : }
506 : #endif
507 :
508 : /**
509 : * @brief Вставляет элементы из диапазона [first, last)
510 : * @param first итератор начала диапазона
511 : * @param last итератор конеца диапазона
512 : */
513 : template<typename InputIterator>
514 1 : void insert(InputIterator first, InputIterator last)
515 : {
516 5 : for (; first != last; ++first)
517 : {
518 4 : this->insert(*first);
519 : }
520 1 : }
521 :
522 : #ifdef __GXX_EXPERIMENTAL_CXX0X__
523 :
524 : /**
525 : * @brief Вставляет элементы из списка инициализации init (c++11)
526 : * @param init — список инициализации элементов контейнера
527 : */
528 : void insert( std::initializer_list<value_type> init)
529 : {
530 : this->insert(init.begin(), init.end());
531 : }
532 :
533 : #endif
534 :
535 : #ifdef __GXX_EXPERIMENTAL_CXX0X__
536 :
537 : /**
538 : * @brief Удаляет элементы (c++11)
539 : * @param pos итератор на элемент для удаления
540 : */
541 5 : iterator erase(const_iterator pos)
542 : {
543 5 : return this->get_aspect().template get<_erase_iterator_>()(*this, pos);
544 : }
545 :
546 : #else
547 :
548 : /**
549 : * @brief Удаляет элементы (c++03)
550 : * @param pos итератор на элемент для удаления
551 : */
552 : void erase(iterator itr)
553 : {
554 : this->get_aspect().template get<_erase_iterator_>()(*this, itr);
555 : }
556 :
557 : #endif
558 :
559 : /**
560 : * @brief Удаляет элементы (c++11)
561 : * @param key Ключевое значение элементов для удаления
562 : */
563 16847 : size_type erase(const key_type& key)
564 : {
565 16847 : return this->get_aspect().template get<_erase_value_>()(*this, key);
566 : }
567 :
568 : #ifdef __GXX_EXPERIMENTAL_CXX0X__
569 :
570 : /**
571 : * @brief Удаляет элементы (c++11) из диапазона [first, last)
572 : * @param first итератор начала диапазона
573 : * @param last итератор конеца диапазона
574 : * @return iterator, следующего за последним удаленным элементом
575 : */
576 : iterator erase(const_iterator first, const_iterator last)
577 : {
578 : return this->get_aspect().template get<_erase_range_>()(*this, first, last);
579 : }
580 :
581 : #else
582 :
583 : /**
584 : * @brief Удаляет элементы (c++03) из диапазона [first, last)
585 : * @param first итератор начала диапазона
586 : * @param last итератор конеца диапазона
587 : */
588 : void erase(iterator first, iterator last)
589 : {
590 : this->get_aspect().template get<_erase_range_>()(*this, first, last);
591 : }
592 :
593 : #endif
594 :
595 : /** @brief Очищает контейнер */
596 3 : void clear()
597 : {
598 3 : return this->get_aspect().template get<_clear_>()(*this);
599 : }
600 :
601 : /**
602 : * @brief Возвращает количество элементов с ключом key.
603 : * @param key Значение ключа
604 : * @return Количество элементов с ключом key
605 : */
606 7 : size_type count(const key_type& key) const
607 : {
608 7 : return static_cast<size_type>( this->upper_bound(key) - this->lower_bound(key) );
609 : }
610 :
611 : #ifdef __GXX_EXPERIMENTAL_CXX0X__
612 :
613 : /**
614 : * @brief находит элемент с конкретным ключом (c++11)
615 : * @param key Ключевое значение элемента для поиска
616 : * @return Итератор элемент с ключом key. Если такой элемент не найден, итератора возвращается vtree::end()
617 : */
618 10014 : iterator find(const key_type& key)
619 : {
620 10014 : return this->get_aspect().template get<_find_>()(*this, key);
621 : }
622 :
623 : /**
624 : * @brief находит элемент с конкретным ключом (c++11)
625 : * @param key Ключевое значение элемента для поиска
626 : * @return Итератор элемент с ключом key. Если такой элемент не найден, итератора возвращается vtree::end()
627 : */
628 : const_iterator find(const key_type& key ) const
629 : {
630 : return this->get_aspect().template get<_find_>()(*this, key);
631 : }
632 :
633 : /**
634 : * @brief возвращает итератор на первый элемент не меньшим, чем заданное значение (c++11)
635 : * @param key ключевое значение для сравнения элементов
636 : * @return итератор, указывающий на первый элемент, который не меньше, чем key. Если такой элемент не найден, итератора возвращается vtree::end()
637 : */
638 10933 : iterator lower_bound(const key_type& key)
639 : {
640 10933 : return this->get_aspect().template get<_lower_bound_>()(*this, key);
641 : }
642 :
643 : /**
644 : * @brief возвращает итератор на первый элемент не меньшим, чем заданное значение (c++11)
645 : * @param key ключевое значение для сравнения элементов
646 : * @return итератор, указывающий на первый элемент, который не меньше, чем key. Если такой элемент не найден, итератора возвращается vtree::end()
647 : */
648 7 : const_iterator lower_bound(const key_type& key) const
649 : {
650 7 : return this->get_aspect().template get<_lower_bound_>()(*this, key);
651 : }
652 :
653 : /**
654 : * @brief возвращает итератор на первый элемент больше, чем заданное значение (c++11)
655 : * @param key ключевое значение для сравнения элементов
656 : * @return итератор, указывающий на первый элемент, который больше, чем key. Если такой элемент не найден, итератора возвращается vtree::end()
657 : */
658 10924 : iterator upper_bound(const key_type& key)
659 : {
660 10924 : return this->get_aspect().template get<_upper_bound_>()(*this, key);
661 : }
662 :
663 : /**
664 : * @brief возвращает итератор на первый элемент больше, чем заданное значение (c++11)
665 : * @param key ключевое значение для сравнения элементов
666 : * @return итератор, указывающий на первый элемент, который больше, чем key. Если такой элемент не найден, итератора возвращается vtree::end()
667 : */
668 7 : const_iterator upper_bound(const key_type& key) const
669 : {
670 7 : return this->get_aspect().template get<_upper_bound_>()(*this, key);
671 : }
672 :
673 : #else
674 :
675 : /**
676 : * @brief находит элемент с конкретным ключом (c++03)
677 : * @param key Ключевое значение элемента для поиска
678 : * @return Итератор элемент с ключом key. Если такой элемент не найден, итератора возвращается vtree::end()
679 : */
680 : iterator find(const key_type& key) const
681 : {
682 : self* t = const_cast<self*>(this);
683 : return t->get_aspect().template get<_find_>()(*t, key);
684 : }
685 :
686 : /**
687 : * @brief возвращает итератор на первый элемент не меньшим, чем заданное значение (c++03)
688 : * @param key ключевое значение для сравнения элементов
689 : * @return итератор, указывающий на первый элемент, который не меньше, чем key. Если такой элемент не найден, итератора возвращается vtree::end()
690 : */
691 : iterator lower_bound(const key_type& key) const
692 : {
693 : self* t = const_cast<self*>(this);
694 : return t->get_aspect().template get<_lower_bound_>()(*t, key);
695 : }
696 :
697 : /**
698 : * @brief возвращает итератор на первый элемент больше, чем заданное значение (c++03)
699 : * @param key ключевое значение для сравнения элементов
700 : * @return итератор, указывающий на первый элемент, который больше, чем key. Если такой элемент не найден, итератора возвращается vtree::end()
701 : */
702 : iterator upper_bound(const key_type& key) const
703 : {
704 : self* t = const_cast<self*>(this);
705 : return t->get_aspect().template get<_upper_bound_>()(*t, key);
706 : }
707 :
708 : #endif
709 :
710 : /**
711 : * @brief Возвращает диапазон, содержащий все элементы с ключевыми key в контейнере
712 : * @param key ключевое значение для сравнения элементов
713 : * @return Пара (std::pair) итераторов, определяющих требуемый диапазон: первый указывает на первый элемент, который не меньше ключа,
714 : * а второй указывает на первый элемент, кторый больше ключа.
715 : */
716 : std::pair<iterator, iterator> equal_range(const key_type& x)
717 : {
718 : return std::make_pair(this->lower_bound(x), this->upper_bound(x) );
719 : }
720 :
721 : /**
722 : * @brief Возвращает диапазон, содержащий все элементы с ключевыми key в контейнере
723 : * @param key ключевое значение для сравнения элементов
724 : * @return Пара (std::pair) итераторов, определяющих требуемый диапазон: первый указывает на первый элемент, который не меньше ключа,
725 : * а второй указывает на первый элемент, кторый больше ключа.
726 : */
727 : std::pair<const_iterator, const_iterator> equal_range(const key_type& x) const
728 : {
729 : return std::make_pair(this->lower_bound(x), this->upper_bound(x) );
730 : }
731 :
732 :
733 : template<typename AA>
734 : friend bool operator==(const vtree<AA>&, const vtree<AA>&);
735 :
736 : template<typename AA>
737 : friend bool operator<(const vtree<AA>&, const vtree<AA>&);
738 :
739 : private:
740 :
741 :
742 : template<typename T>
743 1 : void dummy(T){}
744 :
745 : };
746 :
747 : template<typename A>
748 5 : inline bool operator==(const vtree<A>& __x, const vtree<A>& __y)
749 : {
750 5 : return !(__x < __y) && !(__y < __x);
751 : //return __x.size() == __y.size() && std::equal(__x.begin(), __x.end(), __y.begin());
752 : }
753 :
754 : template<typename A>
755 13 : inline bool operator< (const vtree<A>& __x, const vtree<A>& __y)
756 : {
757 13 : return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end(), __x.key_comp() );
758 : }
759 :
760 : template<typename A>
761 : inline bool
762 : operator!=(const vtree<A>& __x, const vtree<A>& __y)
763 : {
764 : return !(__x == __y);
765 : }
766 :
767 : template<typename A>
768 : inline bool operator>(const vtree<A>& __x, const vtree<A>& __y)
769 : {
770 : return __y < __x;
771 : }
772 :
773 : template<typename A>
774 : inline bool operator<=(const vtree<A>& __x, const vtree<A>& __y)
775 : {
776 : return !(__y < __x);
777 : }
778 :
779 : template<typename A>
780 : inline bool operator>=(const vtree<A>& __x, const vtree<A>& __y)
781 : {
782 : return !(__x < __y);
783 : }
784 :
785 : template<typename A>
786 : inline void swap(vtree<A>& __x, vtree<A>& __y)
787 : {
788 : __x.swap(__y);
789 : }
790 :
791 : }}
792 :
793 : #endif
|
