Re: __gnu_cxx::hash_map question, please help!!!
aaragon wrote:
Working for a while with the gnu hash map I found that I cannot remove
elements from the map whereas if I use a std::map there are no
problems. Is this a bug of the implementation or am I doing something
wrong?
The GNU hash map isn't really part of C++, but since it does
obey the same rules as std::map...
The function is very simple, and I added some code so I can use the
hash map with std::pair as keys (which are not given in the usual
keys).
It doesn't look simple to me:-).
The code I wrote for this is as follows:
namespace __gnu_cxx {
//! Structure used for hash tables of std::pair objects
template<> struct hash<std::pair<size_t,size_t> > {
size_t operator()(std::pair<size_t,size_t> __p) const {
std::size_t seed = 0;
boost::hash_combine(seed, __p.first);
boost::hash_combine(seed, __p.second);
return seed;
}
};
}
and then my class:
template<typename Value = double, typename Key =
std::pair<size_t,size_t>,
class ContainerPolicy = __gnu_cxx::hash_map<Key,Value> > class
SparseMatrix {
...
// some type defs, constructors, etc, etc...
...
...
void clean(ValueType);
};
template<typename V, typename K, class C> int SparseMatrix<V, K,
C>::clean(V tol) {
size_t count(0);
for(IteratorType it = values_.begin(); it!=values_.end(); ++it){
if(std::abs((*this)(it->first.first,it->first.second)) < tol ) {
// remove element from matrix
cout<<"erasing ("<<it->first.first<<","<<it->first.second<<") =
"<<(*this)(it->first.first,it->first.second)<<endl;
int what = values_.erase(it->first);
It's not too clear here, but assuming that values_ is a member
with the type ContainerPolicy (and that IteratorType is
ContainerPolicy::iterator, of course), you've just invalidated
"it", because you've erased the element it designates. The
result is undefined behavior, although if you're using g++ 4.x,
and have compiled with the usual options (in particular:
-D_GLIBCXX_CONCEPT_CHECKS -D_GLIBCXX_DEBUG
-D_GLIBCXX_DEBUG_PEDANTIC), you should get a runtime error when
you next try to increment the iterator. At least, that's what I
get with:
#include <map>
#include <string>
typedef std::map< std::string, int >
Map ;
void
cleanUp( Map& m, int i )
{
for ( Map::iterator it = m.begin() ;
it != m.end() ;
++ it ) {
if ( it->second == i ) {
m.erase( it->first ) ;
}
}
}
int
main()
{
Map m ;
m.insert( Map::value_type( "one", 1 ) ) ;
m.insert( Map::value_type( "two", 2 ) ) ;
m.insert( Map::value_type( "three", 3 ) ) ;
cleanUp( m, 2 ) ;
return 0 ;
}
Which, if I understand your code correctly, is an abstraction of
what you are trying to do. (VC++ also gives a runtime error.
With Sun CC, however, the code "works", in that there is no
error message, and the process returns a successful status; this
is also the results if I omit the debugging options with g++.)
cout<<"what -> "<<what<<endl;
++count;
}
}
return count;
}
The function clean just removes those elements from the matrix that
are smaller than a tolerance. Now, the output of using this function
with a 15x15 matrix is
erasing (0,7) = 0
what -> 1
erasing (6,1) = 2.27e-13
what -> 1
terminate called after throwing an instance of 'fea::RuntimeError'
what(): *** ERROR *** Matrix index (24,0) out of bounds.
The sparse matrix has 15 rows and 15 columns.
I have no idea what is happening here; I have no idea what
fea::RuntimeError is, for example. You really should simplify
before posting---if the problem isn't associated with template
instantiation, for example, get rid of the templates (which only
confuse). If you can trigger the problem using standard types
(rather than user defined types), do so. Etc.
But since your code has
undefined behavior, it's as legal as anything else. If you're
using __gnu_cxx::hash_map, then presumably, you're using g++, so
if you're invoking the compiler normally (with the usual 20 or
so options just about every compiler needs to be useful), you
should be getting something like:
error: attempt to increment a singular iterator.
followed by a lot of other information.
I throw a runtime error when the access to the matrix is out
of bounds. But the out of bounds happens only when removing an
element! So the only thing that comes to my mind, is that
there is a bug in the implementation of the hash table. Is it
correct???? removing and element from the hash table shouldn't
invalidate the iterators, right?
I don't know of a single container type where you can remove the
element designated by the iterator without invalidating the
iterator. Your code, at least if I've understood it correctly,
does exactly this, and doesn't work with std::map. I rather
doubt that the g++ hash_map offers stronger guarantees in this
respect that std::map.
--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orient=E9e objet/
Beratung in objektorientierter Datenverarbeitung
9 place S=E9mard, 78210 St.-Cyr-l'=C9cole, France, +33 (0)1 30 23 00 34