Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Rather than library knowledge, I submit it's basic algorithmic and data structure knowledge. Perhaps one could argue it's knowing how that algorithmic and data structure knowledge maps to actual libraries.

By the way, std::list::size() is defined to be O(1) (see http://www.kuzbass.ru:8086/docs/isocpp/lib-containers.html#l...). While it's possible, of course, to define a linked-list where the size operation is O(n), that's not an implementation of std::list. Hence, there was no difference when std::list::empty() was used - although I agree it's better to use it, since it's more meaningful.



In a confusing bit of ISO trivia, std::list implementations can do either - the standards draw a distinction between "should" and "shall". If an implementation "shall" do something, it's a requirement, and if it "should" do something, it's the preferred choice among several. The size() function only "should" be constant time. In fact, in GCC (which I assume is the Google compiler of choice), std::list::size() is O(n) (http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/a0142...).




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: