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


M

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
 
Ad

Advertisements

M

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)
 
J

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
 
M

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
 
Ad

Advertisements

J

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
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Top