Compact maps

Files CCore/inc/CompactMap.h CCore/src/CompactMap.cpp

These two classes are compact variants of the traditional maps. They have the same set of methods and behavior, except compact maps move elements during delete operations. Compact maps are more efficient and consume less memory, than traditional. They require the object type to be swappable. They also have no node allocator template parameter: compact node allocator is always used. Constructor arguments are forwarded to the allocator.

CompactRBTreeMap

This map is a variant of the RBTreeMap.

template <class K,class T,class KRef=K> 
class CompactRBTreeMap : NoCopy
 {
   ....

  public: 
   
   // constructors
   
   template <class ... SS>
   explicit CompactRBTreeMap(SS && ... ss) noexcept;
   
   ~CompactRBTreeMap();
   
   // std move

   CompactRBTreeMap(CompactRBTreeMap &&obj) noexcept;

   CompactRBTreeMap & operator = (CompactRBTreeMap &&obj) noexcept;

   // props
   
   ulen operator + () const;
   
   bool operator ! () const;
   
   ulen getCount() const;
   
   // find
   
   T * find(KRef key);
   
   T * findMin();
   
   T * findMin(KRef key);
   
   T * findMax();
   
   T * findMax(KRef key);
   
   
   const T * find(KRef key) const;
   
   const T * findMin() const;
   
   const T * findMin(KRef key) const;
   
   const T * findMax() const;
   
   const T * findMax(KRef key) const;
   
   
   const T * find_const(KRef key) const;
   
   const T * findMin_const() const;
   
   const T * findMin_const(KRef key) const;
   
   const T * findMax_const() const;
   
   const T * findMax_const(KRef key) const;
   
   
   template <class S>
   struct NodePtr
    {
     ....
     
     // object ptr
     
     Node * operator + () const;
     
     bool operator ! () const;
     
     S * getPtr() const;
     
     S & operator * () const;
     
     S * operator -> () const;
     
     const K & getKey() const;
    };
   
   
   NodePtr<T> find_ptr(KRef key);
   
   NodePtr<T> findMin_ptr();
   
   NodePtr<T> findMin_ptr(KRef key);
   
   NodePtr<T> findMax_ptr();
   
   NodePtr<T> findMax_ptr(KRef key);
   
   
   NodePtr<const T> find_ptr(KRef key) const;
   
   NodePtr<const T> findMin_ptr() const;
   
   NodePtr<const T> findMin_ptr(KRef key) const;
   
   NodePtr<const T> findMax_ptr() const;
   
   NodePtr<const T> findMax_ptr(KRef key) const;
   

   NodePtr<const T> find_ptr_const(KRef key) const;
   
   NodePtr<const T> findMin_ptr_const() const;
   
   NodePtr<const T> findMin_ptr_const(KRef key) const;
   
   NodePtr<const T> findMax_ptr_const() const;
   
   NodePtr<const T> findMax_ptr_const(KRef key) const;
   
   // add/del
   
   struct Result
    {
     T *obj;
     bool new_flag;
     
     Result(T *obj_,bool new_flag_) : obj(obj_),new_flag(new_flag_) {}
     
     operator T * () const { return obj; }
    };
   
   template <class ... SS>
   Result find_or_add(KRef key,SS && ... ss);
   
   bool del(KRef key);
   
   bool delMin();
   
   bool delMax();
   
   template <class S>
   bool del(NodePtr<S> node_ptr);
   
   ulen erase();
   
   // apply
   
   template <class FuncInit>
   void applyIncr(FuncInit func_init);
   
   template <class FuncInit>
   void applyDecr(FuncInit func_init);
   
   template <class FuncInit>
   void applyIncr(FuncInit func_init) const;
   
   template <class FuncInit>
   void applyDecr(FuncInit func_init) const;
   
   template <class FuncInit>
   void applyIncr_const(FuncInit func_init) const;
   
   template <class FuncInit>
   void applyDecr_const(FuncInit func_init) const;
   
   // swap/move objects
   
   void objSwap(CompactRBTreeMap<K,T,KRef> &obj);
   
   explicit CompactRBTreeMap(ToMoveCtor<CompactRBTreeMap<K,T,KRef> > obj);
 };

CompactRadixTreeMap

This map is a variant of the RadixTreeMap.

template <class K,class T> 
class CompactRadixTreeMap : NoCopy
 {
   ....

  public:
 
   // constructors
   
   template <class ... SS>
   explicit CompactRadixTreeMap(SS && ... ss) noexcept;
   
   template <class ... SS>
   explicit CompactRadixTreeMap(KeyRange<K> key_range,SS && ... ss) noexcept;
   
   ~CompactRadixTreeMap();
   
   // std move

   CompactRadixTreeMap(CompactRadixTreeMap &&obj) noexcept;

   CompactRadixTreeMap & operator = (CompactRadixTreeMap &&obj) noexcept;

   // props
   
   ulen operator + () const;
   
   bool operator ! () const;
   
   ulen getCount() const;
   
   // find
   
   T * find(K key);
   
   T * findMin();
   
   T * findMin(K key);
   
   T * findMax();
   
   T * findMax(K key);
   

   const T * find(K key) const;
   
   const T * findMin() const;
   
   const T * findMin(K key) const;
   
   const T * findMax() const;
   
   const T * findMax(K key) const;
   

   const T * find_const(K key) const;
   
   const T * findMin_const() const;
   
   const T * findMin_const(K key) const;
   
   const T * findMax_const() const;
   
   const T * findMax_const(K key) const;
   
   
   template <class S>
   struct NodePtr
    {
     ....
     
     // object ptr
     
     Node * operator + () const;
     
     bool operator ! () const;
     
     S * getPtr() const;
     
     S & operator * () const;
     
     S * operator -> () const;
     
     K getKey() const;
    };
   
   
   NodePtr<T> find_ptr(K key);
   
   NodePtr<T> findMin_ptr();
   
   NodePtr<T> findMin_ptr(K key);
   
   NodePtr<T> findMax_ptr();
   
   NodePtr<T> findMax_ptr(K key);
   
   
   NodePtr<const T> find_ptr(K key) const;
   
   NodePtr<const T> findMin_ptr() const;
   
   NodePtr<const T> findMin_ptr(K key) const;
   
   NodePtr<const T> findMax_ptr() const;
   
   NodePtr<const T> findMax_ptr(K key) const;
   
   
   NodePtr<const T> find_ptr_const(K key) const;
   
   NodePtr<const T> findMin_ptr_const() const;
   
   NodePtr<const T> findMin_ptr_const(K key) const;
   
   NodePtr<const T> findMax_ptr_const() const;
   
   NodePtr<const T> findMax_ptr_const(K key) const;
   
   // add/del
   
   struct Result
    {
     T *obj;
     bool new_flag;
     
     Result(T *obj_,bool new_flag_) : obj(obj_),new_flag(new_flag_) {}
     
     operator T * () const { return obj; }
    };
   
   template <class ... SS>
   Result find_or_add(K key,SS && ... ss);
   
   bool del(K key);
   
   bool delMin();
   
   bool delMax();
   
   template <class S>
   bool del(NodePtr<S> node_ptr);
   
   ulen erase();
   
   // apply
   
   template <class FuncInit>
   void applyIncr(FuncInit func_init);
   
   template <class FuncInit>
   void applyDecr(FuncInit func_init);
   
   template <class FuncInit>
   void applyIncr(FuncInit func_init) const;
   
   template <class FuncInit>
   void applyDecr(FuncInit func_init) const;
   
   template <class FuncInit>
   void applyIncr_const(FuncInit func_init) const;
   
   template <class FuncInit>
   void applyDecr_const(FuncInit func_init) const;
   
   // swap/move objects
   
   void objSwap(CompactRadixTreeMap<K,T> &obj);
   
   explicit CompactRadixTreeMap(ToMoveCtor<CompactRadixTreeMap<K,T> > obj);
 };