下面的 UtlHashMap 实现在 Visual Studio 2008 中编译但在 GCC 4.4 上给出以下错误
#include <list>
#include <vector>
static size_t DEFAULT_DIC_SIZE = 1023;
template <class K, class V>
class hash_map
{
public:
// for the iterator
// ??typedef V allocator_type;
typedef V value_type;
typedef V& reference;
typedef V* pointer;
typedef const V& const_reference;
typedef const V* const_pointer;
typedef ptrdiff_t difference_type;
typedef size_t size_type;
typedef std::pair<K,V* > KeyValuePair;
typedef std::pair<short,std::list<KeyValuePair > > AccessPair;
hash_map(unsigned (*hashFunc)(const K&), size_t size = DEFAULT_DIC_SIZE);
hash_map(const hash_map& right); // NOTE THIS WILL SHALLOW COPY DATA
~hash_map() {clearAndDestroy();}
//bool insert(const K* key, pointer value);
void insertKeyAndValue(K* key, pointer value);
//const K* findKey (const K* key) const;
pointer findValue(const K* key) const;
const K* findKeyAndValue(const K* key, V*& value);
bool isEmpty() const {return (items_ == 0);}
void clearAndDestroy();
unsigned long long buckets() const { return bucketsUsed_; }
unsigned long long items() const { return items_; }
K* remove (const K* key);
int cins;
clock_t tins;
int cnb;
clock_t tnb;
class iterator
{
public:
typedef V value_type;
typedef V& reference;
typedef V* pointer;
typedef const V& const_reference;
typedef const V* const_pointer;
typedef ptrdiff_t difference_type;
typedef size_t size_type;
//typedef forward_iterator_tag iterator_category;
typedef typename std::vector<AccessPair >::iterator vecIter;
typedef typename std::list<KeyValuePair >::iterator pairLIter;
iterator() {}
// construction also allowed with vector::iterator for implicit constructions
iterator(vecIter& vit, bool bend = false);
// copy constructor
iterator(const iterator& rhs): curBucket_(rhs.curBucket_), curData_(rhs.curData_), theend_(rhs.theend_) {}
virtual ~iterator() {}
iterator& operator=(const iterator& it);
iterator& operator=(const vecIter& vit);
bool operator==(const iterator& rhs) const ;
bool operator!=(const iterator& rhs) const ;
iterator& operator++();
iterator operator++(int);
reference operator*() { return *(curData_->second); }
pointer operator->() { return &(operator*()); }
K* key() const { return &(curData_->first); }
pointer value() const { return (curData_->second);}
protected:
vecIter curBucket_;
pairLIter curData_;
private:
bool theend_;
bool bucketEmpty ();
bool lastBucket ();
void moveOn();
};
class const_iterator : public iterator
{
public:
const_iterator () {}
const_iterator (const const_iterator& ci):iterator(ci) {}
const_iterator (const iterator& i):iterator(i) {}
const_iterator(const vecIter& vit, bool bend = false):iterator(const_cast<vecIter&>( vit),bend) {}
~const_iterator() {}
// these dynamic_cast to references are safe (aren't they? Must be we're making the call!)
const_iterator& operator=(const const_iterator& ci) {return dynamic_cast<const_iterator&>(iterator::operator=(ci));}
bool operator==(const const_iterator& ci) const {return iterator::operator==(ci);}
bool operator!=(const const_iterator& ci) const {return iterator::operator!=(ci);}
const_iterator& operator++() {return const_iterator(iterator::operator++());}
const_iterator operator++(int i) {return const_iterator(iterator::operator++(i)); }
const_reference operator*() const {return *(curData_->second);}
const_pointer operator->() const {return &(operator*());}
const K* key() const { return iterator::key(); }
const_pointer value() const { return iterator::value();}
};
const_iterator begin() const;
const_iterator end() const;
iterator begin() ;
iterator end();
private:
hash_map();
//void operator=();
mutable std::vector<AccessPair > buckets_;
size_t size_;
unsigned long long bucketsUsed_;
unsigned long long items_;
unsigned (*mHashFunc)(const K&);
};
template <class K, class V>
hash_map<K,V>::hash_map(unsigned (*hashFunc)(const K&), size_t size)
: size_ (size)
, mHashFunc (hashFunc)
, bucketsUsed_ (0)
, items_ (0)
{
if(size <= 0) size = 1;// protection against some rogue initialisation.
cins = tins = cnb = tnb = 0;
buckets_.resize(size);
buckets_[size-1].first = 2; //lets hope they are all set to 0
}
template <class K, class V>
hash_map<K,V>::hash_map(const hash_map& right)
{
buckets_ = right.buckets_;
items_ = right.items_;
bucketsUsed_ = right.bucketsUsed_;
size_ = right.size_;
}
template <class K, class V>
void hash_map<K,V>::insertKeyAndValue(K *key, V *value)
{
// get the hash value from key
long hashvalue = mHashFunc(*key);
// what bucket is it in
long bucketIdx = hashvalue%size_;
if (buckets_[bucketIdx].second.empty() )
{
++bucketsUsed_;
buckets_[bucketIdx].first += 1;
}
// do we want to prevent duplicate key being inserted????
// This will allow duplicate keys
buckets_[bucketIdx].second.push_back(std::pair<K,V*>(*key,value));
++items_;
}
template <class K, class V>
V* hash_map<K,V>::findValue(const K* key) const
{
// get the hash value from key
long hashvalue = mHashFunc(*key);
// what bucket is it in
long bucketIdx = hashvalue%size_;
if (!buckets_[bucketIdx].second.empty())
{
for (std::list<std::pair<K,V*> >::const_iterator it = buckets_[bucketIdx].second.begin();
it != buckets_[bucketIdx].second.end(); ++it)
{
if (it->first == *key)
{
return it->second;
}
}
}
return 0;
}
template <class K, class V>
const K* hash_map<K,V>::findKeyAndValue(const K* key, V*& value)
{
// get the hash value from key and what bucket is it in
long bucketIdx = mHashFunc(*key)%size_;
if (!buckets_[bucketIdx].second.empty())
{
for (std::list<std::pair<K,V*> >::const_iterator it = buckets_[bucketIdx].second.begin();
it != buckets_[bucketIdx].second.end(); ++it)
{
if (it->first == *key)
{
value = it->second;
return &(it->first);
}
}
}
return 0;
}
template <class K, class V>
K* hash_map<K,V>::remove (const K* key)
{
// get the hash value from key and what bucket is it in
long bucketIdx = mHashFunc(*key)%size_;
if (!buckets_[bucketIdx].second.empty())
{
for (std::list<std::pair<K,V*> >::iterator it = buckets_[bucketIdx].second.begin();
it != buckets_[bucketIdx].second.end(); ++it)
{
if (it->first == *key)
{
it = buckets_[bucketIdx].second.erase(it); // not sure if I need to delete it->second
--items_;
break; // arrhhhh!!!! need to add to a list to delete
}
}
if ((buckets_[bucketIdx]).second.empty())
{
--bucketsUsed_;
buckets_[bucketIdx].first -= 1;
}
}
return 0;
}
template <class K, class V>
void hash_map<K,V>::clearAndDestroy()
{
for (std::vector<AccessPair >::iterator it = buckets_.begin(); it != buckets_.end(); ++it)
{
if (it->second.empty() == false)
{
it->first -= 1;
it->second.clear(); // this destroys the contents
}
}
bucketsUsed_ = 0;
items_ = 0;
}
template <class K, class V>
typename hash_map<K,V>::const_iterator hash_map<K,V>::begin() const
{
hash_map<K,V>* ptr = const_cast<hash_map<K,V>*>(this);
hash_map<K,V>::iterator it = ptr->begin();
return const_iterator(it);
}
template <class K, class V>
inline typename hash_map<K,V>::const_iterator hash_map<K,V>::end() const
{
return const_iterator(buckets_.end(), true);
}
template <class K, class V>
typename hash_map<K,V>::iterator hash_map<K,V>::begin()
{
if (bucketsUsed_ == 0) return end();
for (std::vector<AccessPair >::iterator it = buckets_.begin(); it != buckets_.end(); ++it)
{
if (it->second.empty() == false) return iterator(it);
}
// should get here!
return end();
}
template <class K, class V>
inline typename hash_map<K,V>::iterator hash_map<K,V>::end()
{
std::vector<AccessPair >::iterator it = buckets_.end();
return iterator(it, true);
}
// --- definition for iterator methods -----
template <class K, class V>
inline hash_map<K,V>::iterator::iterator(vecIter& vit, bool bend)
: curBucket_ (vit)
, theend_(bend)
{
if (!bend) curData_ = curBucket_->second.begin();
}
template <class K, class V>
inline typename hash_map<K,V>::iterator& hash_map<K,V>::iterator::operator=(const typename hash_map<K,V>::iterator& it)
{
// this will break if there is nothing inserted at this position
curBucket_ = it.curBucket_;
curData_ = it.curData_;
theend_ = it.theend_;
return *this;
}
template <class K, class V>
inline typename hash_map<K,V>::iterator& hash_map<K,V>::iterator::operator=(const vecIter& vit)
{
curBucket_= vit;
curData_ = curBucket_->second.begin();
return *this
}
template <class K, class V>
bool hash_map<K,V>::iterator::operator==(const typename hash_map<K,V>::iterator& rhs) const
{
bool b = false; //(curBucket_== rhs.curBucket_ && !theend_ && curData_ == rhs.curData_);
if (curBucket_== rhs.curBucket_)
{
if (!theend_)
{
if (curData_ == rhs.curData_) b = true;
}
else
{
b = true;
}
}
return b;
}
template <class K, class V>
inline bool hash_map<K,V>::iterator::operator!=(const typename hash_map<K,V>::iterator& rhs) const
{
return !(*this==rhs);
}
template <class K, class V>
typename hash_map<K,V>::iterator& hash_map<K,V>::iterator::operator++()
{
// We don't know if we have been called by user or self recursively
// however we do know we cant be here is we had moved to the end of the map (beyong the last bucket)
if (!bucketEmpty())
{
// only inc data when we know bucket is not empty
++curData_;
if (curData_ == curBucket_->second.end())
{
// current bucket is not empty, but next data Item is null
moveOn();
}
}
else
{
// we can only be here if we called our selfs or were assigned to some random position in map (which may not be posible but....)
// 1. are we at the end now
moveOn();
}
return *this;
}
template <class K, class V>
inline typename hash_map<K,V>::iterator hash_map<K,V>::iterator::operator++(int)
{
iterator tmp(*this);
++(*this);
return tmp;
}
template <class K, class V>
inline bool hash_map<K,V>::iterator::bucketEmpty ()
{
if ((curBucket_->first & 1) == 0) return true;
return false;
}
template <class K, class V>
inline bool hash_map<K,V>::iterator::lastBucket ()
{
if ((curBucket_->first & 2) > 1) return true;
return false;
}
template <class K, class V>
inline void hash_map<K,V>::iterator::moveOn()
{
if (lastBucket())
{
// this is the last bucket, we need to mark it, so when we move on to next bucket (END),
// we do not attempt access any data items
theend_ = true;
}
++curBucket_;
if (!theend_)
{
// OK this is not the last bucket, but at the same time we do not want to return an empty bucket with no data
if (bucketEmpty())
{
++(*this);
}
else
{
// we have data we can return - hoora!
curData_ = curBucket_->second.begin();
}
}
}
UtlHashMap.h:102: error: ISO C++ forbids declaration of âvecIterâ with no type
UtlHashMap.h:102: error: expected â,â or â...â before â&â token
UtlHashMap.h: In constructor âjda::hash_map<K, V>::const_iterator::const_iterator(int)â:
UtlHashMap.h:102: error: expected type-specifier before âvecIterâ
UtlHashMap.h:102: error: expected â>â before âvecIterâ
UtlHashMap.h:102: error: expected â(â before âvecIterâ
UtlHashMap.h:102: error: expected primary-expression before â>â token
UtlHashMap.h:102: error: âvitâ was not declared in this scope
UtlHashMap.h:102: error: âbendâ was not declared in this scope
UtlHashMap.h:102: error: expected â{â at end of input
UtlHashMap.h: In member function âconst V& jda::hash_map<K, V>::const_iterator::operator*() constâ:
UtlHashMap.h:114: error: âcurData_â was not declared in this scope
UtlHashMap.h: In member function âV* jda::hash_map<K, V>::findValue(const K*) constâ:
UtlHashMap.h:195: error: expected â;â before âitâ
UtlHashMap.h:196: error: âitâ was not declared in this scope
UtlHashMap.h: In member function âconst K* jda::hash_map<K, V>::findKeyAndValue(const K*, V*&)â:
UtlHashMap.h:217: error: expected â;â before âitâ
UtlHashMap.h:218: error: âitâ was not declared in this scope
UtlHashMap.h: In member function âK* jda::hash_map<K, V>::remove(const K*)â:
UtlHashMap.h:238: error: expected â;â before âitâ
UtlHashMap.h:239: error: âitâ was not declared in this scope
UtlHashMap.h: In member function âvoid jda::hash_map<K, V>::clearAndDestroy()â:
UtlHashMap.h:263: error: expected â;â before âitâ
UtlHashMap.h:263: error: âitâ was not declared in this scope
UtlHashMap.h: In member function âjda::hash_map<K, V>::iterator jda::hash_map<K, V>::begin()â:
UtlHashMap.h:295: error: expected â;â before âitâ
UtlHashMap.h:295: error: âitâ was not declared in this scope
UtlHashMap.h: In member function âjda::hash_map<K, V>::iterator jda::hash_map<K, V>::end()â:
UtlHashMap.h:306: error: expected â;â before âitâ
UtlHashMap.h:307: error: âitâ was not declared in this scope
UtlHashMap.h: In member function âjda::hash_map<K, V>::iterator& jda::hash_map<K, V>::iterator::operator=(const typename std::vector<std::pair<short int, std::list<std::pair<K, V*>, std::allocator<std::pair<K, V*> > > >, std::allocator<std::pair<short int, std::list<std::pair<K, V*>, std::allocator<std::pair<K, V*> > > > > >::iterator&)â:
UtlHashMap.h:338: error: expected â;â before â}â token
最佳答案
我建议您根据 ISO C++ 2003 标准中的新模板规则检查模板的使用情况。
谢谢
关于c++ - 自定义 HashMap 在 Linux 上使用 gcc 给出编译错误，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/18998425/