ders::hash_vec< Key, Val, KeyHash, KeyEql > Class Template Reference

Associative hash container. More...

#include <hash_vec.hpp>

List of all members.

Public Member Functions
	hash_vec (int rsrv, const KeyHash &kh=KeyHash(), const KeyEql &ke=KeyEql())
	~hash_vec ()
int	size () const
int	capacity () const
void	reserve (int n)
const Key &	key (int pos) const
Val &	val (int pos)
const Val &	val (int pos) const
int	insert (const Key &k, const Val &v)
int	find (const Key &k) const
void	erase (int pos)

---

Detailed Description

template<class Key, class Val, class KeyHash = key_hash<Key>, class KeyEql = key_eql<Key>>
class ders::hash_vec< Key, Val, KeyHash, KeyEql >

Associative hash container.

Definition at line 140 of file hash_vec.hpp.

---

Constructor & Destructor Documentation

template<class Key, class Val, class KeyHash, class KeyEql>

ders::hash_vec< Key, Val, KeyHash, KeyEql >::hash_vec	(	int	rsrv,
		const KeyHash &	kh = KeyHash(),
		const KeyEql &	ke = KeyEql()
	)			[inline]

Definition at line 180 of file hash_vec.hpp.

              : khash(kh), keql(ke), hndx(0), nds(rsrv)
{
 hndx=static_cast<int*>(operator new(sizeof(int)*nds.resd));
 fill_n(hndx, nds.resd, -1);
}

template<class Key, class Val, class KeyHash = key_hash<Key>, class KeyEql = key_eql<Key>>

ders::hash_vec< Key, Val, KeyHash, KeyEql >::~hash_vec

(

)

[inline]

Definition at line 157 of file hash_vec.hpp.

{ operator delete(hndx); }

---

Member Function Documentation

template<class Key, class Val, class KeyHash = key_hash<Key>, class KeyEql = key_eql<Key>>

int ders::hash_vec< Key, Val, KeyHash, KeyEql >::size

(

)

const [inline]

Definition at line 159 of file hash_vec.hpp.

{ return nds.used; }

template<class Key, class Val, class KeyHash = key_hash<Key>, class KeyEql = key_eql<Key>>

int ders::hash_vec< Key, Val, KeyHash, KeyEql >::capacity

(

)

const [inline]

Definition at line 160 of file hash_vec.hpp.

{ return nds.resd; }

template<class Key, class Val, class KeyHash, class KeyEql>

void ders::hash_vec< Key, Val, KeyHash, KeyEql >::reserve

(

int

n

)

[inline]

Definition at line 188 of file hash_vec.hpp.

{
 assert(n>0);
 if (nds.resd>=n) return;

 int* hndx2=static_cast<int*>(operator new(sizeof(int)*n));

 typedef typename nodes::node node;
 node* nodes2;
 try { nodes2=static_cast<node*>(operator new(sizeof(node)*n)); }
 catch (...) {
       operator delete(hndx);
       throw;
 }

 fill_n(hndx2, n, -1);

 memcpy(nodes2, nds.nodes, sizeof(*nodes2)*nds.used);
 for (int i=0; i<nds.used; i++) nodes2[i].next=-1;

 for (int i=0; i<nds.used; i++) {
     int* pnode=hndx2+khash(nodes2[i].key)%n;
     nodes2[i].next=*pnode;
     *pnode=i;
 }

 operator delete(hndx);
 hndx=hndx2;

 operator delete(nds.nodes);
 nds.nodes=nodes2;
 nds.resd=n;
}

template<class Key, class Val, class KeyHash, class KeyEql>

const Key & ders::hash_vec< Key, Val, KeyHash, KeyEql >::key

(

int

pos

)

const [inline]

Definition at line 223 of file hash_vec.hpp.

{
 assert(pos>=0 && pos<size());
 return nds.nodes[pos].key;
}

template<class Key, class Val, class KeyHash, class KeyEql>

Val & ders::hash_vec< Key, Val, KeyHash, KeyEql >::val

(

int

pos

)

[inline]

Definition at line 230 of file hash_vec.hpp.

{
 assert(pos>=0 && pos<size());
 return nds.nodes[pos].val;
}

template<class Key, class Val, class KeyHash, class KeyEql>

const Val & ders::hash_vec< Key, Val, KeyHash, KeyEql >::val

(

int

pos

)

const [inline]

Definition at line 237 of file hash_vec.hpp.

{
 assert(pos>=0 && pos<size());
 return nds.nodes[pos].val;
}

template<class Key, class Val, class KeyHash, class KeyEql>

int ders::hash_vec< Key, Val, KeyHash, KeyEql >::insert	(	const Key &	k,
		const Val &	v
	)			[inline]

Definition at line 244 of file hash_vec.hpp.

{
 assert(nds.used<=nds.resd);
 if (nds.used==nds.resd) reserve(nds.resd*2+1);

 int* pnode=find(root(k), k);
 if (*pnode!=-1) return -1;

 nds.create_at(nds.used, k, v);
 return *pnode=nds.used++;
}

template<class Key, class Val, class KeyHash = key_hash<Key>, class KeyEql = key_eql<Key>>

int ders::hash_vec< Key, Val, KeyHash, KeyEql >::find

(

const Key &

k

)

const [inline]

Definition at line 168 of file hash_vec.hpp.

{ return *find(root(k), k); }

template<class Key, class Val, class KeyHash, class KeyEql>

void ders::hash_vec< Key, Val, KeyHash, KeyEql >::erase

(

int

pos

)

[inline]

Definition at line 257 of file hash_vec.hpp.

{
 assert(pos>=0 && pos<size());

 const Key& k=nds.nodes[pos].key;
 int* pnode=find(root(k), k);
 assert(*pnode==pos);

 int tail=nds.nodes[pos].next;

 nds.destroy_at(pos);
 *pnode=-1;

 if (tail!=-1) {
    int* ptr=root(nds.nodes[tail].key);
    while (*ptr!=-1) ptr=&nds.nodes[*ptr].next;

    *ptr=tail;
 }

 int last=nds.used-1;
 if (pos!=last) {
    const Key& lkey=nds.nodes[last].key;
    int* nlast=find(root(lkey), lkey);
    assert(*nlast==last);

    nds.move_to(pos, last);
    *nlast=pos;
 }

 nds.used--;
}

---

The documentation for this class was generated from the following file:

• hash_vec.hpp