app crash when there's more than 3000 entries in std::map ?

[mast4as]

Hi everyone

I have this strange behaviour happening with this code which I can't
explain. On my computer when I set nt with a value greater than 3000
it crashes. Is there a max number of keys I can use with a std::map ?

thanks a lot

#include <vector>
#include <iostream>
#include <map>

#include <string>


int main()
{
float t = clock();
int nt = 3000;
#if 1
hash_map<std::string, int, hash<std::string> > mymap;
for ( int i = 0; i < nt; ++i )
{
string tmp = "test" + i;
mymap[ tmp ] = i;
}
for ( int i = 0; i < 10e5; ++i )
{
int a = (int)(drand48() * nt);
string tmp = "test" + a;
hash_map<std::string, int, hash<std::string> >::iterator it =
mymap.find( tmp );
if ( it != mymap.end() )
{
}
else
{
printf("not found\n");
}
}
unsigned max_size = mymap.max_size();
printf("%d\n", max_size );

#else
std::map<std::string, int> mymap;
for ( int i = 0; i < nt; ++i )
{
string tmp = "test" + i;
mymap[ tmp ] = i;
}
for ( int i = 0; i < 10e5; ++i )
{
int a = (int)(drand48() * nt);
string tmp = "test" + a;
std::map<std::string, int>::iterator it = mymap.find( tmp );
if ( it != mymap.end() )
{
}
else
{
printf("not found\n");
}
}

unsigned max_size = mymap.max_size();
printf("%d\n", max_size );

#endif
printf("time %f\n", (clock() - t ) / float( CLOCKS_PER_SEC ) );

return 0;
}

#endif

 

[mast4as]

Sorry you need to add

#include <ext/hash_map>
using namespace __gnu_cxx;
namespace __gnu_cxx {

// hash specialisation to allow hashing of strings
template<>
struct hash<std::string>
{
size_t operator()(const std::string &__s) const { return
__stl_hash_string(__s.c_str()); }
};

} // namespace __gnu_cxx OR std

at the top if you want this to compile. But hash_map and map behaves
the same

using c++ (GCC) 4.1.2 20080704 (Red Hat 4.1.2-44)

 

[Jonathan Lee]

Hi everyone

I have this strange behaviour happening with this code which I can't
explain. On my computer when I set nt with a value greater than 3000
it crashes. Is there a max number of keys I can use with a std::map ?

It's because this doesn't do what you think it does:

                string tmp = "test" + i;

It does *not* make a string named "test1", "test2", etc.
Instead, it does pointer arithmetic on the const char*
that points to "test".

So
("test" + 0) is a pointer to the string "test"
("test" + 1) is a pointer to the string "est"
("test" + 2) is a pointer to the string "st"

etc.

Once i passes the null byte in the string literal, though,
you're into some random chunk of memory. All bets are off.
Eventually you're reading outside of memory that belongs
to your application and you get a segfault.

--Jonathan

 

[mast4as]

It's because this doesn't do what you think it does:


It does *not* make a string named "test1", "test2", etc.
Instead, it does pointer arithmetic on the const char*
that points to "test".

So
   ("test" + 0) is a pointer to the string "test"
   ("test" + 1) is a pointer to the string "est"
   ("test" + 2) is a pointer to the string "st"

etc.

Once i passes the null byte in the string literal, though,
you're into some random chunk of memory. All bets are off.
Eventually you're reading outside of memory that belongs
to your application and you get a segfault.

--Jonathan

Thanks a lot yes ... I just figured (long day at work ;-(

Thank you so much
std::string createRandomString()
{
char alpha[ 6 ] = { 'a', 'b', 'c', 'd', 'e', 'f' };
char str[ 10 ];
for ( int i = 0 ; i < 10 ; i++ )
{
int a = int(drand48()*5);
str[ i ] = a;
}
return std::string( str );
}

int main()
{
float t = clock();
int nt = 10000;
#if 1
hash_map<std::string, int, hash<std::string> > mymap;
for ( int i = 0; i < nt; ++i )
{
string tmp = createRandomString();
mymap[ tmp ] = i;
}
for ( int i = 0; i < 10e5; ++i )
{
int a = (int)(drand48() * nt);
string tmp = createRandomString();
hash_map<std::string, int, hash<std::string> >::iterator it =
mymap.find( tmp );
if ( it != mymap.end() )
{
}
else
{
//printf("not found\n");
}
}
unsigned max_size = mymap.max_size();
printf("%d\n", max_size );

#else
std::map<std::string, int> mymap;
for ( int i = 0; i < nt; ++i )
{
string tmp = createRandomString();
mymap[ tmp ] = i;
}
for ( int i = 0; i < 10e5; ++i )
{
int a = (int)(drand48() * nt);
string tmp = createRandomString();
std::map<std::string, int>::iterator it = mymap.find( tmp );
if ( it != mymap.end() )
{
}
else
{
//printf("not found\n");
}
}

unsigned max_size = mymap.max_size();
printf("%d\n", max_size );

#endif
printf("time %f\n", (clock() - t ) / float( CLOCKS_PER_SEC ) );

return 0;
}

#endif

 

[Jonathan Lee]

Thanks a lot yes ... I just figured (long day at work ;-(

Thank you so much
std::string createRandomString()
{
        char alpha[ 6 ] = { 'a', 'b', 'c', 'd', 'e', 'f' };
        char str[ 10 ];
        for ( int i = 0 ; i < 10 ; i++ )
        {
                int a = int(drand48()*5);
                str[ i ] = a;
        }
        return std::string( str );

}

No problem. BTW, if you want to avoid these random strings
you could probably use next_permutation from <algorithm>
to get some string names. Make a char array of distinct
letters, permute them, and use string::append to get your
dummy string.

(Not entirely related, just something I've found useful
before)

--Jonathan