What happens when QMap reaches maximum items



  • Hi,

    this is a theoretical edge case which will actually never happen for my use case but it's something I've ignored for several years now and I don't think that's a good idea in general.

    Q: What happens when a QMap is full and one calls insert() ?


  • Moderators

    Looking at the source I think the map will fall into an inconsistent state.
    At first glance the insert seems to not care about the limit as it just inserts another node in a tree (pointer arithmetic and malloc mostly), but the methods like QMap::count() rely on ints so they will be susceptible to overflows.

    I guess to avoid such problems you would have to check the count before calling an insert.
    I might be missing something though. I'm not that proficient in Qt internals.



  • What exactly do you mean by "full"?

    If you run a 32 bit application, the your application will run out of memory before you can insert the last item anyway.
    As for a 64 bit application, I always assumed 'int' would be 64 bit, thereby again causing you to run out of memory long before the map is full.


  • Moderators

    @Asperamanca The maximum addressable process memory on a 32 bit system is about 3.something GB (with some OS tinkering) and maximum int will be about 2GB so (very) theoretically you could see an overflow before you run out of space. Of course the conditions for it are unrealistic outside of a lab experiment, but OP said it was a theoretical question.



  • @Chris-Kawa How so? A map entry needs at least one int-sized key and one int-sized value. Or can the map optimize away part of that?


  • Moderators

    Hm, I guess you're right. The QMap itself needs some memory apart from the data.

    But (again) theoretically, a map could be implemented as a bucket tree, and binary search instead of indexing within a single bucket. The keys don't need to be stored as they can be converted to in-place calculated hashes that would be looked up in the tree... or something like that :P
    The performance of such structure would be abysmal of course and there are problems like memory fragmentation, but for the purpose of discussion I believe it's possible to create it so that it would fit in the 2 -3.something memory gap above the int max value. I'm not gonna try to prove it though. It's too impractical to waste time on it even for fun and I may very well be wrong here :)



  • Thanks for your opinions, guys! So it's really safe to ignore this.


Log in to reply
 

Looks like your connection to Qt Forum was lost, please wait while we try to reconnect.