3 ms·
AFAIR the deques in PFDS don't permit anything better than O(log n) random access -- and the ones that do that are hideously complicated (again AFAIR, it's been
by lomnakkus 12y ago
AFAIR the deques in PFDS don't permit anything better than O(log n) random access -- and the ones that do that are hideously complicated (again AFAIR, it's been years since I read it). Also, the thing is constants matter, and this is what the "log_32(n)" vs. "log(n)" discussion is driving at.
(You're still not going to get anywhere close to a linear scan of an array with directly embedded values, but there's just no way to achieve that kind of raw performance for pure functional data structures.)