Show HN: A header only C++11 LRU Cache template class, with no dependencies

Not really sure why they reimplemented std::list. Also that NoCopy base class adds a vptr for no reason. And so do all those other virtual destructors. I personally wouldn't trust this code at first glance.

the kv::List is not intended as a generic linked list implementation like std::list.

The reason for the specific implementation is to get constant time removal and remove-add_to_end operations. Truth be told, it is a hold-over from the previous implementation. I shall be writing benchmarks for this next up and shall revisit the decision on whether or not to use std::list soon-ish :)

The : private NoCopy is just to block the copy constructors.

quinnftw 3585 days ago

Personally I would use a macro such as:

    #define DISALLOW_COPY_AND_ASSIGN(TypeName) \
    TypeName(TypeName&) = delete;              \
    void operator=(TypeName) = delete;

Introducing a virtual base class for disabling copying introduces a vtable and un-needed inheritance.

_lbaq 3585 days ago

>The : private NoCopy is just to block the copy constructors.

If its C++11 why not just use the delete keyword to prevent auto generating members ?

http://en.cppreference.com/w/cpp/container/list:

Someone 3585 days ago

"The reason for the specific implementation is to get constant time removal and remove-add_to_end operations"

"std::list is a container that supports constant time insertion and removal of elements from anywhere in the container."

'The : private NoCopy is just to block the copy constructors."

But does it need a virtual destructor?

You could have used std::list iterators instead of raw pointers to a node in the map to implement that.

now i remember why I went with the old linked list implementation.

with the std::list, everytime I refreshed a node... i did a copy.

basically to the tune of list.push_back(*iter) where as I wanted to keep it as a simple unlink and relink of the node

copy of the comment: https://news.ycombinator.com/item?id=12391069

To swap nodes in the list you need to use splice like this:

keys_.splice(keys_.begin(), keys_, iter->second);

Where iter is from the cache lookup.

yeah, saw the gist posted by quinnftw. that actually is a better way to do what I'm doing. Will update that along with the

cache.remove(const Key& k, F deleteCallback) method.

Thanks for the feedback

https://gist.github.com/Quinny/09e34afb1d187e43dea2f3c3b0c04...

quinnftw 3585 days ago

Or if you want a non-obfuscated version

Use splice to move items to the front of the list without copying in the find method.

https://gist.github.com/Quinny/09e34afb1d187e43dea2f3c3b0c04...

ah, now I remember why I had carried on with the linked list from the old c++ codebase

the key refresh in std::list required a copy of the std::pair, where as I wished to keep it as an unlink / relink

cjhanks 3585 days ago

One of two (or both) things would need to be changed for it to be generally useful:

- The return value should be a WeakPtr, not a bool and a reference. This allows for data to not be duplicated by all of the different `getter` threads. A WeakPtr<Type> is kind of C++'s equivalent of a Maybe<Type>.

- The getter function also need to be passed a functor capable of generating the object, which then creates a `named lock` that /only/ other threads requesting that key. This duplicates multiple logical copies of the same item from being created (this is important when the creation is expensive, presumably the core reason for using an LRU cache).

edit: formatting, I am not familiar with HN syntax.

psranga 3585 days ago

This line bothered me more than it should :)

    typedef std::string String;

when

    using std::string;

would have done just as well.

Yes, I noticed the capitalization change. But why do you want to change the name of a fundamental type?

Can someone explain how this is headers-only? C/C++ are not my forte, but my limited interpretation of a "headers only" thing would be more along the lines of: it's only type definitions and preprocessor macros.

It looks like there's plenty of actual method implementations being filled out there, but they just happen to be in a .hpp file instead of a .cpp file.

socmag 3585 days ago

It means all the code is defined in-line in the header file, inside the class definition, instead of the more traditional method of using a header and an associated cpp file.

A lot of the C++ standard library (STL) and Boost are header only (but not all)

This means to use the code, all you need to do is #include the header file wherever you need it, rather than including a header file and either building a separate static/shared library for the cpp file, or including it in your own build.

So that's really convenient.

Another thing that happens is that the by doing this, the compiler can potentially do a lot better job of optimizing the code by inlining parts of the library straight into your calling function.

With static libraries it is possible to get some optimizations like this made at link time, since link time code generation is a requirement for templates, but that's not possible with shared libraries since you are forced to call through an exported function entry point by their very nature.

Header only libraries are typical for containers or light weight libraries where the cost of inclusion and possible code duplication of code is worth the performance gains, and certainly very popular where templates are involved.

tl;dr, header only is cool just because they are so easy to consume and don't need a make file. Just #include and you are done.

Gotcha. Thanks for the detailed explanation.

header-only usually means there's one or more .h/.hpp files that you can include in your source. There's no source file or library to compile and include

e.g. if I had Hello.h and Hello.cpp, you'd need to either add Hello.cpp to your make/build or build a library and link to it.

Header-only version means all you do is

#include "Hello.h"

and you're all set to go.

So in this case, headers-only is really just an approach to avoid compiling a separate library? More akin to literally including the source code in your source code, in the eyes on the compiler. All in the same object/library.

mostly: yes! :)

Also, keep in mind that most of the library is templates, which need to go in the header files.

BTW, most of boost is header-only :) e.g. boost/noncopyable.hpp would give you a header only equivalent of the NoCopy class I wrote.

I've always felt weird about having to include some big-arse library for just using a simple container, so for things like this I prefer to write header-only versions.

Cool. Thanks for the edification.

aldanor 3585 days ago

Benchmarks / comparison to using other container types would be nice to have

yup! that's next up. :)

WesternStar 3585 days ago

Looks like your insert function is missing an else . You're creating a new node when each time you find an existing node in the map.

thanks. fixed

So it's C++11 but still uses naked pointers...

the naked pointers are inside an internal kv namespace and are a convenience/carry over from the previous implementation (I've covered the justification for the way it's written in a comment above).

the TL;DR is that it is written the way it is to achieve constant time remove/remove_and_add_to_end operations which is not an erase+append but more like an unlink/relink operation.