stlab.adobe.com Adobe Systems Incorporated
closed_hash.hpp
Go to the documentation of this file.
1 /*
2  Copyright 2005-2007 Adobe Systems Incorporated
3  Distributed under the MIT License (see accompanying file LICENSE_1_0_0.txt
4  or a copy at http://stlab.adobe.com/licenses.html)
5 */
6 
7 /*************************************************************************************************/
8 
9 #ifndef ADOBE_CLOSED_HASH_HPP
10 #define ADOBE_CLOSED_HASH_HPP
11 
12 /*************************************************************************************************/
13 
14 #include <adobe/config.hpp>
15 
17 
18 #include <climits>
19 #include <cstddef>
20 #include <limits>
21 
22 #include <boost/compressed_pair.hpp>
23 #include <boost/functional/hash.hpp>
24 #include <boost/iterator/iterator_adaptor.hpp>
25 #include <boost/iterator/iterator_facade.hpp>
26 #include <boost/static_assert.hpp>
27 #include <boost/type_traits/has_nothrow_constructor.hpp>
28 #include <boost/type_traits/remove_reference.hpp>
29 #include <boost/operators.hpp>
30 #include <boost/next_prior.hpp>
31 
33 #include <adobe/conversion.hpp>
34 #include <adobe/cstdint.hpp>
35 #include <adobe/empty.hpp>
36 #include <adobe/functional.hpp>
38 #include <adobe/memory.hpp>
39 #include <adobe/move.hpp>
40 #include <adobe/utility.hpp>
41 
42 #include <adobe/implementation/swap.hpp>
43 
44 /*************************************************************************************************/
45 
46 namespace adobe {
47 
48 /*************************************************************************************************/
49 
50 namespace implementation {
51 
52 /*************************************************************************************************/
53 
54 template <typename T, typename V> // V is value_type(T) const qualified
55 class closed_hash_iterator : public boost::iterator_facade<closed_hash_iterator<T, V>, V,
56  std::bidirectional_iterator_tag>
57 {
58  typedef boost::iterator_facade<closed_hash_iterator<T, V>, V,
59  std::bidirectional_iterator_tag> inherited_t;
60 
61  typedef typename T::node_t node_t;
62  public:
63  typedef typename inherited_t::reference reference;
64  typedef typename inherited_t::difference_type difference_type;
65  typedef typename inherited_t::value_type value_type;
66 
67  closed_hash_iterator() : node_m(0) { }
68 
69  template <typename O>
70  closed_hash_iterator(const closed_hash_iterator<T, O>& x) : node_m(x.node_m) { }
71 
72  public:
73  /*
74  REVISIT (sparent@adobe.com) : node_m should be private but
75  "gcc version 4.0.1 (Apple Inc. build 5465)" doesn't like it.
76  */
77 
78  node_t* node_m;
79 
80  private:
81 
82  reference dereference() const { return node_m->value_m; }
83  void increment() { node_m = node_m->next(); }
84  void decrement() { node_m = node_m->prior(); }
85 
86  template< typename O>
87  bool equal(const closed_hash_iterator<T, O>& y) const { return node_m == y.node_m; }
88 
89  std::size_t state() const { return node_m->state(); }
90  void set_state(std::size_t x) { return node_m->set_state(x); }
91 
92  explicit closed_hash_iterator(node_t* node) : node_m(node) { }
93 
94  friend class version_1::closed_hash_set<value_type, typename T::key_transform, typename T::hasher,
95  typename T::key_equal, typename T::allocator_type>;
96  friend class boost::iterator_core_access;
97  friend struct unsafe::set_next_fn<closed_hash_iterator>;
98 };
99 
100 /*************************************************************************************************/
101 
102 } // namespace implementation
103 
104 /*************************************************************************************************/
105 
106 namespace unsafe {
107 
108 template <typename T, typename V>
109 struct set_next_fn<implementation::closed_hash_iterator<T, V> >
110 {
111  typedef typename implementation::closed_hash_iterator<T, V> iterator;
112 
113  void operator()(iterator x, iterator y) const
114  { set_next(*x.node_m, *y.node_m); }
115 };
116 
117 } // namespace unsafe
118 
119 /*************************************************************************************************/
120 
121 #ifndef ADOBE_NO_DOCUMENTATION
122 
123 namespace version_1 {
124 
125 #endif
126 
127 /*************************************************************************************************/
128 
152 template< typename T,
153  typename KeyTransform,
154  typename Hash,
155  typename Pred,
156  typename A>
157 class closed_hash_set : boost::equality_comparable<closed_hash_set<T, KeyTransform, Hash, Pred, A>,
158  closed_hash_set<T, KeyTransform, Hash, Pred, A>,
159  empty_base<closed_hash_set<T, KeyTransform, Hash, Pred, A> > >
160 {
161  public:
162  typedef KeyTransform key_transform;
163 
164  typedef typename boost::remove_reference<typename key_transform::result_type>::type
166 
167  typedef T value_type;
168  typedef Hash hasher;
169  typedef Pred key_equal;
170  typedef A allocator_type;
171  typedef value_type* pointer;
172  typedef const value_type* const_pointer;
174  typedef const value_type& const_reference;
175  typedef std::size_t size_type;
176  typedef std::ptrdiff_t difference_type;
177 
178  friend class implementation::closed_hash_iterator<closed_hash_set, value_type>;
179  friend class implementation::closed_hash_iterator<closed_hash_set, const value_type>;
180 
181  typedef implementation::closed_hash_iterator<closed_hash_set, value_type> iterator;
182  typedef implementation::closed_hash_iterator<closed_hash_set, const value_type> const_iterator;
183 
184  typedef std::reverse_iterator<iterator> reverse_iterator;
185  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
186 
187  private:
188  enum
189  {
190  state_free = 0,
191  state_home = 1,
192  state_misplaced = 2
193  };
194 
195  template <typename U> // U is derived node
196  struct list_node_base
197  {
198  list_node_base() { next_m = static_cast<U*>(this); prior_m = static_cast<U*>(this); }
199 
200  U* address() { return static_cast<U*>(this); }
201  const U* address() const { return static_cast<const U*>(this); }
202 
203  operator U& () { return *static_cast<U*>(this); }
204  operator const U& () const { return *static_cast<const U*>(this); }
205 
206  friend inline void set_next(U& x, U& y)
207  { x.next_m = reinterpret_cast<U*>(uintptr_t(&y) | uintptr_t(x.state())); y.prior_m = &x; }
208 
209  friend inline void set_next_raw(U& x, U& y)
210  { x.next_m = &y; y.prior_m = &x; }
211 
212  std::size_t state() const { return std::size_t(uintptr_t(next_m) & uintptr_t(0x03UL)); }
213  void set_state(std::size_t x)
214  {
215  assert(x < 0x04UL);
216  next_m = reinterpret_cast<U*>(uintptr_t(next()) | uintptr_t(x));
217  }
218 
219  U* next() const { return reinterpret_cast<U*>(reinterpret_cast<uintptr_t>(next_m) & ~uintptr_t(0x03UL)); }
220  U* prior() const { return prior_m; }
221 
222  private:
223  U* next_m;
224  U* prior_m;
225  };
226 
227  struct node_t : list_node_base<node_t>
228  {
229  T value_m;
230  };
231 
232  typedef list_node_base<node_t> node_base_t;
233 
234  struct header_t
235  {
237  {
238  boost::compressed_pair<allocator_type, node_base_t> alloc_free_tail_m;
239  node_base_t used_tail_m;
240  std::size_t capacity_m;
241  std::size_t size_m;
242  };
243 
244  /*
245  NOTE (sparent) - the assumption is that the initial items are pointers and that size_t is
246  either equal to the sizeof a pointer or a lower power of two so this packs tightly.
247  */
248 
249  BOOST_STATIC_ASSERT(!(sizeof(A) == sizeof(void*) || sizeof(A) == 0)
250  || (sizeof(compact_header_t) == (sizeof(allocator_type) + 2 * sizeof(node_base_t) + 2 *
251  sizeof(std::size_t))));
252 
254  node_t storage_m[1];
255 
256  allocator_type& allocator() { return header_m.get().alloc_free_tail_m.first(); }
257  const allocator_type& allocator() const { return header_m.get().alloc_free_tail_m.first(); }
258  node_base_t& free_tail() { return header_m.get().alloc_free_tail_m.second(); }
259  const node_base_t& free_tail() const { return header_m.get().alloc_free_tail_m.second(); }
260  node_base_t& used_tail() { return header_m.get().used_tail_m; }
261  const node_base_t& used_tail() const { return header_m.get().used_tail_m; }
262  std::size_t& capacity() { return header_m.get().capacity_m; }
263  const std::size_t& capacity() const { return header_m.get().capacity_m; }
264  std::size_t& size() { return header_m.get().size_m; }
265  const std::size_t& size() const { return header_m.get().size_m; }
266  };
267 
268  typedef node_t* node_ptr;
269 
270  typedef boost::compressed_pair< hasher,
271  boost::compressed_pair< key_equal,
272  boost::compressed_pair< key_transform,
273  header_t*
274  >
275  >
276  > data_t;
277 
278  data_t data_m;
279 
280  typedef header_t* header_pointer;
281 
282  const header_pointer& header() const { return data_m.second().second().second(); }
283  header_pointer& header() { return data_m.second().second().second(); }
284 
285  public:
286  // construct/destroy/copy
287 
288  closed_hash_set() { header() = 0; }
289 
291  {
292  header() = 0;
293  allocate(allocator_type(), n);
294  }
295 
296  closed_hash_set(size_type n, const hasher& hf, const key_equal& eq = key_equal(),
297  const key_transform& kf = key_transform(),
298  const allocator_type& a = allocator_type())
299  {
300  header() = 0;
301  data_m.first() = hf;
302  data_m.second().first() = eq;
303  data_m.second().second().first() = kf;
304  allocate(a, n);
305  }
306 
307  template <typename I> // I models InputIterator
308  closed_hash_set(I f, I l) { header() = 0; insert(f, l); }
309 
310  template <typename I> // I models InputIterator
311  closed_hash_set(I f, I l, size_type n, const hasher& hf = hasher(),
312  const key_equal& eq = key_equal(),
313  const key_transform& kf = key_transform(),
314  const allocator_type& a = allocator_type())
315  {
316  header() = 0;
317  data_m.first() = hf;
318  data_m.second().first() = eq;
319  data_m.second().second().first() = kf;
320  allocate(a, n);
321  insert(f, l);
322  }
323 
324  closed_hash_set(const closed_hash_set& x) : data_m(x.data_m)
325  {
326  header() = 0;
327  allocate(x.get_allocator(), x.size());
328  insert(x.begin(), x.end());
329  }
330  closed_hash_set& operator=(closed_hash_set x) { swap(x, *this); return *this; }
331 
333  { return header() ? header()->allocator() : allocator_type(); }
334 
335  closed_hash_set(move_from<closed_hash_set> x) : data_m(x.source.data_m) { x.source.header() = 0; }
336 
337 #if 0
338  template <typename I> // I models ForwardIterator
339  closed_hash_set(I f, I l, move_ctor) { header() = 0; move_insert(f, l); }
340 #endif
341 
342  // size and capacity
343 
344  size_type size() const { return header() ? header()->size() : 0; }
345  size_type max_size() const { return size_type(-1) / sizeof(node_t); }
346  bool empty() const { return size() == 0; }
347  size_type capacity() const { return header() ? header()->capacity() : 0; }
348 
350  {
351  if (n <= capacity()) return;
352 
353  if (!header()) allocate(allocator_type(), n);
354  else
355  {
356  closed_hash_set tmp(n, hash_function(), key_eq(), key_function(), get_allocator());
357  tmp.move_insert(begin(), end());
358  swap(*this, tmp);
359  }
360  }
361 
362  key_transform key_function() const { return data_m.second().second().first(); }
363  hasher hash_function() const { return data_m.first(); }
364  key_equal key_eq() const { return data_m.second().first(); }
365 
366  iterator begin() { return iterator(header() ? header()->used_tail().next() : 0); }
367  iterator end() { return iterator(header() ? header()->used_tail().address() : 0); }
368 
369  const_iterator begin() const { return iterator(header() ? header()->used_tail().next() : 0); }
370  const_iterator end() const { return iterator(header() ? const_cast<node_t*>(header()->used_tail().address()) : 0); }
371 
373  reverse_iterator rend() { return reverse_iterator(begin()); }
374 
377 
379  {
380  iterator next(boost::next(location));
381  iterator result = next;
382 
383  if ((location.state() == std::size_t(state_home)) && (next != end())
384  && (next.state() == std::size_t(state_misplaced)))
385  {
386  swap(*next, *location);
387  result = location;
388  location = next;
389  }
390 
391  unsafe::skip_node(location);
392  erase_raw(location);
393 
394  --header()->size();
395 
396  return result;
397  }
398 
399  std::size_t erase(const key_type& key)
400  {
401  iterator node(find(key));
402  if (node == end()) return 0;
403  erase(node);
404  return 1;
405  }
406 
407  void clear()
408  {
409  for(iterator first(begin()), last(end()); first != last; first = erase(first)) ;
410  }
411 
412  const_iterator find(const key_type& key) const
413  {
414  return adobe::remove_const(*this).find(key);
415  }
416 
417  iterator find(const key_type& key)
418  {
419  if (empty()) return end();
420 
421  iterator node(bucket(key));
422 
423  if (node.state() != std::size_t(state_home)) return end();
424 
425  return find(node, key);
426  }
427 
428  std::pair<const_iterator, const_iterator> equal_range(const key_type& key) const
429  {
430  const_iterator result = find(key);
431  if (result == end()) return std::make_pair(result, result);
432  return std::make_pair(result, boost::next(result));
433  }
434 
435  std::pair<iterator, iterator> equal_range(const key_type& key)
436  {
437  iterator result = find(key);
438  if (result == end()) return std::make_pair(result, result);
439  return std::make_pair(result, boost::next(result));
440  }
441 
442  std::size_t count(const key_type& key) const
443  { return std::size_t(find(key) != end()); }
444 
445  template <typename I> // I models InputIterator
446  void insert(I first, I last)
447  { while (first != last) { insert(*first); ++first; } }
448 
449  template <typename I> // I models ForwardIterator
450  void move_insert(I first, I last)
451  { while (first != last) { insert(adobe::move(*first)); ++first; } }
452 
453  /*
454  NOTE (sparent): If there is not enough space for one element we will reserve the space
455  prior to attempting the insert even if the item is already in the hash table. Without
456  recalculating the bucket (a potentially expensive operation) there is no other solution.
457  */
458 
459  std::pair<iterator, bool> insert(value_type x)
460  {
461  if (capacity() == size()) reserve(size() ? 2 * size() : 3);
462 
463  iterator node = bucket(key_function()(x));
464 
465  switch (node.state())
466  {
467  case state_home:
468  {
469  iterator found = find(node, key_function()(x));
470  if (found != end()) {
471  *found = adobe::move(x);
472  return std::make_pair(found, false);
473  }
474 
475  iterator free(begin_free());
476  insert_raw(free, adobe::move(x), state_misplaced);
477  unsafe::splice_node_range(node, free, free);
478  node = free;
479  }
480  break;
481  case state_misplaced:
482  {
483  iterator free(begin_free());
484  insert_raw(free, adobe::move(*node), state_misplaced);
485 
486  unsafe::set_next(boost::prior(node), free);
487  unsafe::set_next(free, boost::next(node));
488 
489  erase_raw(node);
490  }
491  // fall through
492  default: // state_free
493  {
494  insert_raw(node, adobe::move(x), state_home);
495  unsafe::splice_node_range(end(), node, node);
496  }
497  }
498  header()->size() += 1;
499  return std::make_pair(node, true);
500  }
501 
503  {
504  return insert(adobe::move(x)).first;
505  }
506 
508  {
509  if (header())
510  {
511  for(iterator first(begin()), last(end()); first != last; ++first) destroy(&*first);
512  raw_allocator alloc(get_allocator());
513  alloc.deallocate(reinterpret_cast<char*>(header()), 0);
514  }
515  }
516 
518  {
519  std::swap(x.data_m, y.data_m);
520  }
521 
522  friend bool operator==(const closed_hash_set& x, const closed_hash_set& y)
523  {
524  if (x.size() != y.size()) return false;
525  for (const_iterator first(x.begin()), last(x.end()); first != last; ++first)
526  {
527  const_iterator iter(y.find(y.key_function()(*first)));
528  if (iter == y.end() || !(*first == *iter)) return false;
529  }
530  return true;
531  }
532  private:
533 
534  typedef typename allocator_type::template rebind<char>::other raw_allocator;
535 
536 
537  void allocate(const allocator_type& a, size_type n)
538  {
539  // table of primes such that p[n + 1] = next_prime(2 * p[n])
540 
541  static const std::size_t prime_table[] = { 3UL, 7UL, 17UL, 37UL, 79UL, 163UL, 331UL, 673UL,
542  1361UL, 2729UL, 5471UL, 10949UL, 21911UL, 43853UL, 87719UL, 175447UL, 350899UL,
543  701819UL, 1403641UL, 2807303UL, 5614657UL, 11229331UL, 22458671UL, 44917381UL,
544  89834777UL, 179669557UL, 359339171UL, 718678369UL, 1437356741UL, 2874713497UL,
545  ULONG_MAX
546  };
547 
548  assert(!header() && "WARNING (sparent@adobe.com) : About to write over allocated header.");
549 
550  if (n == 0 && a == allocator_type()) return;
551 
552  n = *adobe::lower_bound(prime_table, n);
553 
554  raw_allocator alloc(a);
555 
556  header() = reinterpret_cast<header_t*>(alloc.allocate(sizeof(header_t) - sizeof(node_t)
557  + sizeof(node_t) * n));
558  header()->capacity() = n;
559  header()->size() = 0;
560  construct(&header()->free_tail());
561  construct(&header()->used_tail());
562  construct(&header()->allocator(), a);
563 
564  node_t* prior = header()->free_tail().address();
565  for (node_ptr first(&header()->storage_m[0]), last(&header()->storage_m[0]+ n);
566  first != last; ++first)
567  {
568  set_next_raw(*prior, *first);
569  prior = first;
570  // first->set_state(state_free);
571  }
572  set_next_raw(*prior, header()->free_tail());
573 
574  }
575 
576  iterator bucket(const key_type& key)
577  {
578  std::size_t slot(hash_function()(key) % capacity());
579  return iterator(&header()->storage_m[0] + slot);
580  }
581 
582  iterator find(iterator node, const key_type& key)
583  {
584  do
585  {
586  if (key_eq()(key, key_function()(*node))) return node;
587  ++node;
588  } while ((node != end()) && (node.state() != std::size_t(state_home)));
589 
590  return end();
591  }
592 
593  // location points to a free node
594  static void insert_raw(iterator location, value_type x, std::size_t state)
595  {
596  construct<value_type>(&*location, adobe::move(x));
597  location.set_state(state);
598  unsafe::skip_node(location);
599  }
600 
601  // location points to a used but detatched node
602  void erase_raw(iterator location)
603  {
604  destroy(&*location);
605  location.set_state(state_free);
606  unsafe::splice_node_range(end_free(), location, location);
607  }
608 
609  iterator begin_free() { return iterator(header() ? header()->free_tail().next() : 0); }
610  iterator end_free() { return iterator(header() ? header()->free_tail().address() : 0); }
611 };
612 
613 /*************************************************************************************************/
614 
633 template<typename Key,
634  typename T,
635  typename Hash,
636  typename Pred,
637  typename A>
638 class closed_hash_map : public closed_hash_set<pair<Key, T>,
639  get_element<0, pair<Key, T> >,
640  Hash,
641  Pred,
642  A>
643 {
646  Hash,
647  Pred,
648  A> set_type;
649  public:
650  typedef T mapped_type;
651 
653 
654  template <typename I> // I models InputIterator
655  closed_hash_map(I f, I l) : set_type(f, l) { }
656 
657 #if 0
658  template <typename I> // I models ForwardIterator
659  closed_hash_map(I f, I l, move_ctor) : set_type(f, l, move_ctor()) { }
660 #endif
661 
665  { swap(x, *this); return *this; }
666 
668  { swap(static_cast<set_type&>(x), static_cast<set_type&>(y)); }
669 
670 
671  friend bool operator==(const closed_hash_map& x, const closed_hash_map& y)
672  { return static_cast<const set_type&>(x) == static_cast<const set_type&>(y); }
673 
674  /*
675  NOTE (sparent) : Can't use boost::equality_comparable without introducing extra base class
676  overhead.
677  */
678 
679  friend bool operator!=(const closed_hash_map& x, const closed_hash_map& y)
680  { return !(x == y); }
681 
682 #ifndef ADOBE_CLOSED_HASH_MAP_INDEX
683 #define ADOBE_CLOSED_HASH_MAP_INDEX 1
684 #endif
685 
686 #if ADOBE_CLOSED_HASH_MAP_INDEX
687 
688  mapped_type& operator[](const Key& x)
689  {
690  typename set_type::iterator i = this->find(x);
691  if (i == this->end()) return insert(adobe::make_pair(x, mapped_type())).first->second;
692  return i->second;
693  }
694 
695 #endif
696 };
697 
698 /*************************************************************************************************/
699 
700 BOOST_STATIC_ASSERT(sizeof(closed_hash_set<int>) == sizeof(void*));
701 
702 
703 #ifndef ADOBE_NO_DOCUMENTATION
704 
705 } // namespace version_1
706 
707 #endif
708 
709 /*************************************************************************************************/
710 
711 } // namespace adobe
712 
713 /*************************************************************************************************/
714 
715 ADOBE_NAME_TYPE_1("closed_hash_set:version_1:adobe",
716  adobe::version_1::closed_hash_set<T0, adobe::identity<const T0>, boost::hash<T0>, std::equal_to<T0>,
718 ADOBE_NAME_TYPE_2("closed_hash_map:version_1:adobe",
719  adobe::version_1::closed_hash_map<T0, T1, boost::hash<T0>, std::equal_to<T0>,
721 
722 ADOBE_NAME_TYPE_5("closed_hash_set:version_1:adobe",
724 ADOBE_NAME_TYPE_5("closed_hash_map:version_1:adobe",
726 
727 /*************************************************************************************************/
728 
729 namespace boost {
730 
731 template< typename T,
732  typename KeyTransform,
733  typename Hash,
734  typename Pred,
735  typename A>
736 struct has_nothrow_constructor<adobe::version_1::closed_hash_set<T, KeyTransform, Hash, Pred, A> >
737  : boost::mpl::true_ { };
738 
739 template<typename Key,
740  typename T,
741  typename Hash,
742  typename Pred,
743  typename A>
744 struct has_nothrow_constructor<adobe::version_1::closed_hash_map<Key, T, Hash, Pred, A> >
745  : boost::mpl::true_ { };
746 
747 } // namespace boost
748 
749 /*************************************************************************************************/
750 
751 #endif
752 
753 /*************************************************************************************************/
std::reverse_iterator< iterator > reverse_iterator
closed_hash_map & operator=(closed_hash_map x)
bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, BinaryPredicate pred)
Definition: equal.hpp:38
void skip_node(I location)
Definition: set_next.hpp:71
closed_hash_map(const closed_hash_map &x)
reverse_iterator rend()
std::pair< iterator, iterator > equal_range(const key_type &key)
reverse_iterator rbegin()
closed_hash_set(size_type n, const hasher &hf, const key_equal &eq=key_equal(), const key_transform &kf=key_transform(), const allocator_type &a=allocator_type())
size_type capacity() const
friend bool operator==(const closed_hash_map &x, const closed_hash_map &y)
const_reverse_iterator rend() const
friend bool operator==(const closed_hash_set &x, const closed_hash_set &y)
move_from is used for move_ctors.
Definition: move.hpp:306
key_equal key_eq() const
allocator_type get_allocator() const
void swap(adobe::lex_stream_t &, adobe::lex_stream_t &)
Definition: lex_stream.hpp:68
A hash based associative container.
I lower_bound(I f, I l, const T &x)
BOOST_STATIC_ASSERT(sizeof(closed_hash_set< int >)==sizeof(void *))
iterator erase(iterator location)
std::size_t count(const key_type &key) const
void destroy(T *p)
Definition: memory.hpp:626
version_1::closed_hash_set closed_hash_set
const_iterator end() const
friend void swap(closed_hash_map &x, closed_hash_map &y)
void set_next(I x, I y)
Definition: set_next.hpp:44
const_iterator begin() const
iterator find(const key_type &key)
std::ptrdiff_t difference_type
ADOBE_NAME_TYPE_1("closed_hash_set:version_1:adobe", adobe::version_1::closed_hash_set< T0, adobe::identity< const T0 >, boost::hash< T0 >, std::equal_to< T0 >, adobe::capture_allocator< T0 > >)
key_transform key_function() const
closed_hash_set & operator=(closed_hash_set x)
const value_type * const_pointer
void splice_node_range(I location, I first, I last)
Definition: set_next.hpp:59
void reserve(size_type n)
size_type max_size() const
friend void swap(closed_hash_set &x, closed_hash_set &y)
A hash based associative container.
friend bool operator!=(const closed_hash_map &x, const closed_hash_map &y)
size_type size() const
std::pair< const_iterator, const_iterator > equal_range(const key_type &key) const
implementation::closed_hash_iterator< closed_hash_set, value_type > iterator
std::pair< iterator, bool > insert(value_type x)
closed_hash_set(move_from< closed_hash_set > x)
closed_hash_set(I f, I l, size_type n, const hasher &hf=hasher(), const key_equal &eq=key_equal(), const key_transform &kf=key_transform(), const allocator_type &a=allocator_type())
void move_insert(I first, I last)
void swap(circular_queue< T > &, circular_queue< T > &)
iterator insert(iterator, value_type x)
const_iterator find(const key_type &key) const
KeyTransform key_transform
boost::compressed_pair< allocator_type, node_base_t > alloc_free_tail_m
ADOBE_NAME_TYPE_5("closed_hash_set:version_1:adobe", adobe::version_1::closed_hash_set< T0, T1, T2, T3, T4 >)
boost::remove_reference< typename key_transform::result_type >::type key_type
T::iterator erase(T &x, typename T::iterator f, typename T::iterator l)
Definition: erase_if.hpp:63
closed_hash_map(move_from< closed_hash_map > x)
boost::range_iterator< InputRange >::type find(InputRange &range, const T &value)
find implementation
Definition: find.hpp:151
void insert(I first, I last)
closed_hash_set(const closed_hash_set &x)
closed_hash_set(size_type n)
void construct(T *p)
Definition: memory.hpp:629
unsigned long uintptr_t
Definition: cstdint.hpp:41
const_reverse_iterator rbegin() const
version_1::closed_hash_map closed_hash_map
ADOBE_NAME_TYPE_2("closed_hash_map:version_1:adobe", adobe::version_1::closed_hash_map< T0, T1, boost::hash< T0 >, std::equal_to< T0 >, adobe::capture_allocator< adobe::pair< T0, T1 > > >)
const value_type & const_reference
implementation::closed_hash_iterator< closed_hash_set, const value_type > const_iterator
std::size_t erase(const key_type &key)
std::reverse_iterator< const_iterator > const_reverse_iterator
boost::range_size< Selection >::type size(const Selection &x)
pair< T1, T2 > make_pair(T1 x, T2 y)
Definition: pair.hpp:109
hasher hash_function() const
mapped_type & operator[](const Key &x)
T & remove_const(const T &x)
Definition: conversion.hpp:85

Copyright © 2006-2007 Adobe Systems Incorporated.

Use of this website signifies your agreement to the Terms of Use and Online Privacy Policy.

Search powered by Google