return a == b;
}
static inline unsigned int hash(const void *a) {
- return (intptr_t)a;
+ return (uintptr_t)a;
}
};
int do_insert(const K &key, int &hash)
{
if (hashtable.empty()) {
- entries.push_back(entry_t(std::pair<K, T>(key, T()), -1));
+ entries.emplace_back(std::pair<K, T>(key, T()), -1);
do_rehash();
hash = do_hash(key);
} else {
- entries.push_back(entry_t(std::pair<K, T>(key, T()), hashtable[hash]));
+ entries.emplace_back(std::pair<K, T>(key, T()), hashtable[hash]);
hashtable[hash] = entries.size() - 1;
}
return entries.size() - 1;
int do_insert(const std::pair<K, T> &value, int &hash)
{
if (hashtable.empty()) {
- entries.push_back(entry_t(value, -1));
+ entries.emplace_back(value, -1);
do_rehash();
hash = do_hash(value.first);
} else {
- entries.push_back(entry_t(value, hashtable[hash]));
+ entries.emplace_back(value, hashtable[hash]);
+ hashtable[hash] = entries.size() - 1;
+ }
+ return entries.size() - 1;
+ }
+
+ int do_insert(std::pair<K, T> &&rvalue, int &hash)
+ {
+ if (hashtable.empty()) {
+ auto key = rvalue.first;
+ entries.emplace_back(std::forward<std::pair<K, T>>(rvalue), -1);
+ do_rehash();
+ hash = do_hash(key);
+ } else {
+ entries.emplace_back(std::forward<std::pair<K, T>>(rvalue), hashtable[hash]);
hashtable[hash] = entries.size() - 1;
}
return entries.size() - 1;
return std::pair<iterator, bool>(iterator(this, i), true);
}
+ std::pair<iterator, bool> insert(std::pair<K, T> &&rvalue)
+ {
+ int hash = do_hash(rvalue.first);
+ int i = do_lookup(rvalue.first, hash);
+ if (i >= 0)
+ return std::pair<iterator, bool>(iterator(this, i), false);
+ i = do_insert(std::forward<std::pair<K, T>>(rvalue), hash);
+ return std::pair<iterator, bool>(iterator(this, i), true);
+ }
+
+ std::pair<iterator, bool> emplace(K const &key, T const &value)
+ {
+ int hash = do_hash(key);
+ int i = do_lookup(key, hash);
+ if (i >= 0)
+ return std::pair<iterator, bool>(iterator(this, i), false);
+ i = do_insert(std::make_pair(key, value), hash);
+ return std::pair<iterator, bool>(iterator(this, i), true);
+ }
+
+ std::pair<iterator, bool> emplace(K const &key, T &&rvalue)
+ {
+ int hash = do_hash(key);
+ int i = do_lookup(key, hash);
+ if (i >= 0)
+ return std::pair<iterator, bool>(iterator(this, i), false);
+ i = do_insert(std::make_pair(key, std::forward<T>(rvalue)), hash);
+ return std::pair<iterator, bool>(iterator(this, i), true);
+ }
+
+ std::pair<iterator, bool> emplace(K &&rkey, T const &value)
+ {
+ int hash = do_hash(rkey);
+ int i = do_lookup(rkey, hash);
+ if (i >= 0)
+ return std::pair<iterator, bool>(iterator(this, i), false);
+ i = do_insert(std::make_pair(std::forward<K>(rkey), value), hash);
+ return std::pair<iterator, bool>(iterator(this, i), true);
+ }
+
+ std::pair<iterator, bool> emplace(K &&rkey, T &&rvalue)
+ {
+ int hash = do_hash(rkey);
+ int i = do_lookup(rkey, hash);
+ if (i >= 0)
+ return std::pair<iterator, bool>(iterator(this, i), false);
+ i = do_insert(std::make_pair(std::forward<K>(rkey), std::forward<T>(rvalue)), hash);
+ return std::pair<iterator, bool>(iterator(this, i), true);
+ }
+
int erase(const K &key)
{
int hash = do_hash(key);
return entries[i].udata.second;
}
- T at(const K &key, const T &defval) const
+ const T& at(const K &key, const T &defval) const
{
int hash = do_hash(key);
int i = do_lookup(key, hash);
void clear() { hashtable.clear(); entries.clear(); }
iterator begin() { return iterator(this, int(entries.size())-1); }
+ iterator element(int n) { return iterator(this, int(entries.size())-1-n); }
iterator end() { return iterator(nullptr, -1); }
const_iterator begin() const { return const_iterator(this, int(entries.size())-1); }
+ const_iterator element(int n) const { return const_iterator(this, int(entries.size())-1-n); }
const_iterator end() const { return const_iterator(nullptr, -1); }
};
entry_t() { }
entry_t(const K &udata, int next) : udata(udata), next(next) { }
+ entry_t(K &&udata, int next) : udata(std::move(udata)), next(next) { }
};
std::vector<int> hashtable;
int do_insert(const K &value, int &hash)
{
if (hashtable.empty()) {
- entries.push_back(entry_t(value, -1));
+ entries.emplace_back(value, -1);
do_rehash();
hash = do_hash(value);
} else {
- entries.push_back(entry_t(value, hashtable[hash]));
+ entries.emplace_back(value, hashtable[hash]);
+ hashtable[hash] = entries.size() - 1;
+ }
+ return entries.size() - 1;
+ }
+
+ int do_insert(K &&rvalue, int &hash)
+ {
+ if (hashtable.empty()) {
+ entries.emplace_back(std::forward<K>(rvalue), -1);
+ do_rehash();
+ hash = do_hash(rvalue);
+ } else {
+ entries.emplace_back(std::forward<K>(rvalue), hashtable[hash]);
hashtable[hash] = entries.size() - 1;
}
return entries.size() - 1;
return std::pair<iterator, bool>(iterator(this, i), true);
}
+ std::pair<iterator, bool> insert(K &&rvalue)
+ {
+ int hash = do_hash(rvalue);
+ int i = do_lookup(rvalue, hash);
+ if (i >= 0)
+ return std::pair<iterator, bool>(iterator(this, i), false);
+ i = do_insert(std::forward<K>(rvalue), hash);
+ return std::pair<iterator, bool>(iterator(this, i), true);
+ }
+
+ template<typename... Args>
+ std::pair<iterator, bool> emplace(Args&&... args)
+ {
+ return insert(K(std::forward<Args>(args)...));
+ }
+
int erase(const K &key)
{
int hash = do_hash(key);
return !operator==(other);
}
+ bool hash() const {
+ unsigned int hashval = mkhash_init;
+ for (auto &it : entries)
+ hashval ^= ops.hash(it.udata);
+ return hashval;
+ }
+
void reserve(size_t n) { entries.reserve(n); }
size_t size() const { return entries.size(); }
bool empty() const { return entries.empty(); }
void clear() { hashtable.clear(); entries.clear(); }
iterator begin() { return iterator(this, int(entries.size())-1); }
+ iterator element(int n) { return iterator(this, int(entries.size())-1-n); }
iterator end() { return iterator(nullptr, -1); }
const_iterator begin() const { return const_iterator(this, int(entries.size())-1); }
+ const_iterator element(int n) const { return const_iterator(this, int(entries.size())-1-n); }
const_iterator end() const { return const_iterator(nullptr, -1); }
};
pool<K, OPS> database;
public:
- typedef typename pool<K, OPS>::const_iterator const_iterator;
+ class const_iterator : public std::iterator<std::forward_iterator_tag, K>
+ {
+ friend class idict;
+ protected:
+ const idict &container;
+ int index;
+ const_iterator(const idict &container, int index) : container(container), index(index) { }
+ public:
+ const_iterator() { }
+ const_iterator operator++() { index++; return *this; }
+ bool operator==(const const_iterator &other) const { return index == other.index; }
+ bool operator!=(const const_iterator &other) const { return index != other.index; }
+ const K &operator*() const { return container[index]; }
+ const K *operator->() const { return &container[index]; }
+ };
int operator()(const K &key)
{
bool empty() const { return database.empty(); }
void clear() { database.clear(); }
- const_iterator begin() const { return database.begin(); }
- const_iterator end() const { return database.end(); }
+ const_iterator begin() const { return const_iterator(*this, offset); }
+ const_iterator element(int n) const { return const_iterator(*this, n); }
+ const_iterator end() const { return const_iterator(*this, offset + size()); }
};
template<typename K, typename OPS>
void clear() { database.clear(); parents.clear(); }
const_iterator begin() const { return database.begin(); }
+ const_iterator element(int n) const { return database.element(n); }
const_iterator end() const { return database.end(); }
};