A drop-in replacement for std::list with 293% faster insertion, 57% faster erasure, 17% faster iteration and 77% faster sorting on average. 20-24% speed increase in use-case testing.

plf_list

A drop-in replacement for std::list with (on average):

  • 293% faster insertion
  • 57% faster erasure
  • 17% faster iteration
  • 77% faster sorting
  • 70% faster reversal
  • 91% faster remove/remove_if
  • 63% faster unique
  • 811% faster clear (1147900% for trivially-destructible types)
  • 1248% faster destruction (6350% for trivially-destructible types)
  • 20-24% faster performance overall in ordered use-case benchmarking(insertion, erasure and iteration on the fly and over time)

(Benchmarks performed on a haswell-based CPU under GCC 8.1: http://www.plflib.org/benchmarks_haswell_gcc.htm Insertion, erasure, and iteration percentages obtained as average of performance across 5 types from char to very large struct) plf::list is C++98/03/11/14/etc compatible.

Documentation here: https://plflib.org/list.htm

Comments
  • PLF_CPP20_SUPPORT bugs insert due to multiple reasons. On Visual Studio latest version

    PLF_CPP20_SUPPORT bugs insert due to multiple reasons. On Visual Studio latest version

    with PLF_CPP20_SUPPORT enabled these issues occur:

    1. insert() returns void (should be iterator)
    2. insert() gives me other vague errors about not being able to find matching parameters, probably due to the iterator parameters that I don't fill in my code as that's not normally required.

    I have to comment out PLF_CPP20_SUPPORT to make it compile.

  • License: Rename / Duplicate?

    License: Rename / Duplicate?

    @mattreecebentley Per https://help.github.com/articles/adding-a-license-to-a-repository/ , ifF you rename or duplicate (or perhaps quicker, commit directly from https://choosealicense.com/licenses/zlib/ ) your current license file to LICENSE or LICENSE.md, GitHub interface will pick it up, & show your repo license type in the header & searches that restrict to open-source licenses.

  • shrink_to_fit is bugged

    shrink_to_fit is bugged

    	plf::list<int> wow;
    	wow.push_back(1);
    	wow.push_back(7);
    	wow.push_back(3);
    	wow.push_back(5);
    	wow.push_back(4);
    	const auto size1 = wow.size(); //5
    
    	wow.shrink_to_fit();
    	const auto size2 = wow.size(); //0
    
    	wow.resize(4);
    	const auto size3 = wow.size(); //4
    
    	wow.shrink_to_fit();
    	const auto size4 = wow.size(); //0
    

    As you can see, shrink_to_fit() is not behaving properly.

  • non-const unordered_find_single()

    non-const unordered_find_single()

    iterator unordered_find_single(const element_type &element_to_match) PLF_LIST_NOEXCEPT
    

    ~~I would expect this function to be marked const, if it [the function] cannot be marked const because of some internal (state?), the function should be declared const and the internal (state) mutable.~~

    This function must be marked const.

  • Fix wrong emplace_back and _front returns

    Fix wrong emplace_back and _front returns

    Iterators were dereferenced and then extraneosly referenced again on return from emplace_back and emplace_front. This commit ommits the needless reference which caused code to not compile.

  • make plf::list::erase compatible with std::list::erase

    make plf::list::erase compatible with std::list::erase

    The standard specifies that the ranged version of erase should return the iterator following the last removed element. This should rectify that. I've also slightly modified the tests involving erase for this. Looks good on GCC, Clang and MSVC.

  • Move constructor crashed

    Move constructor crashed

    Hi I suspected the move semantics are not handled properly. We are using your project but it crashed when constructing a list with move constructor.

    		list(list &&source) PLF_LIST_NOEXCEPT:
    			element_allocator_type(source),
    			groups(std::move(source.groups)),
    			end_node(std::move(source.end_node)),
    			last_endpoint(std::move(source.last_endpoint)),
    			end_iterator(reinterpret_cast<node_pointer_type>(&end_node)),
    			begin_iterator((source.begin_iterator.node_pointer == source.end_iterator.node_pointer) ? reinterpret_cast<node_pointer_type>(&end_node) : std::move(source.begin_iterator)),
    			node_pointer_allocator_pair(source.node_pointer_allocator_pair.total_number_of_elements),
    			node_allocator_pair(source.node_allocator_pair.number_of_erased_nodes)
    		{
    			end_node.previous->next = begin_iterator.node_pointer->previous = end_iterator.node_pointer;
    			source.groups.blank();
    			source.node_pointer_allocator_pair.total_number_of_elements = 0;
                            
                            source.reset();   // NEED to clean out source to avoid crash
    		}
    
  • iterator operators not returning iterator reference

    iterator operators not returning iterator reference

    For parity with std::list, (at least in Visual Studio), the following should return a reference to the list_iterator, rather than a copy:

    inline PLF_LIST_FORCE_INLINE list_iterator operator ++ () PLF_LIST_NOEXCEPT inline PLF_LIST_FORCE_INLINE list_iterator operator -- () PLF_LIST_NOEXCEPT inline list_iterator operator = (const list_iterator &rh) PLF_LIST_NOEXCEPT inline list_iterator operator = (const list_iterator &&rh) PLF_LIST_NOEXCEPT

    inline PLF_LIST_FORCE_INLINE list_reverse_iterator operator ++ () PLF_LIST_NOEXCEPT inline PLF_LIST_FORCE_INLINE list_reverse_iterator operator -- () PLF_LIST_NOEXCEPT inline list_reverse_iterator operator = (const list_reverse_iterator &rh) PLF_LIST_NOEXCEPT inline list_reverse_iterator operator = (const list_reverse_iterator &&rh) PLF_LIST_NOEXCEPT

  • Cannot use non-const functors for sort

    Cannot use non-const functors for sort

    With std::list, I can use a functor with a non-const operator() when sorting. This can be helpful when the compare has to build some temporary data per item (like a display name), caching the value internally so that it doesn't have to build the display name every time that record is compared during the sort.

    This can be fixed by adding a second, non-const operator() in sort_dereferencer with the same code as the const version. I am not sure this works on all compilers/platforms.

  • Compile warning

    Compile warning

    On Visual Studio 2017, I get the warning: warning C4458: declaration of 'end_node' hides class member

    on this line: inline PLF_LIST_FORCE_INLINE void destroy_all_node_pointers(group_pointer_type const group_to_process, const node_pointer_type end_node) PLF_LIST_NOEXCEPT

    If you rename end_node parameter, this warning goes away.

  • plf_list.remove() leaves an element stuck in the list

    plf_list.remove() leaves an element stuck in the list

    Add the following test to plf_list_test_suite.cpp (remove ( ==5))

    list1.remove(4) failpass("should be empty list", 0 == list1.size())

    Also replicated by: plf::list<int*> x; int a; int b; x.push_back(&a); x.push_back(&b); x.remove(&a); x.remove(&b); failpass("should be empty" 0 == x.size())

    Love the list, we are seeing a 16% increase in performance. Luckily our own unittest alerted us to this problem.

  • splicing the last element to the end drops it

    splicing the last element to the end drops it

    Calling splice() to move the last element to the end drops it

    #include <iostream>
    #include "plf_list.h"
    
    void print(const plf::list<int>& list1)
    {
      for (auto& elem : list1)
      {
        std::cout << elem << ' ';
      }
      std::cout << std::endl;
    }
    
    int main()
    {
      plf::list<int> list1 = { 1, 2, 3, 4, 5 };
    
      // Outputs "1 2 3 4 5 "
      print(list1);
    
      // This *should* be a no-op:
      list1.splice(list1.end(), std::prev(list1.end()));
    
      // Outputs "1 2 3 4"
      print(list1);
    
      return 0;
    }
    
C++ implementation of a fast hash map and hash set using hopscotch hashing

A C++ implementation of a fast hash map and hash set using hopscotch hashing The hopscotch-map library is a C++ implementation of a fast hash map and

Aug 9, 2022
A c++ toolbox of locality-sensitive hashing (LSH), provides several popular LSH algorithms, also support python and matlab.

LSHBOX-0.9 A C++ Toolbox of Locality-Sensitive Hashing for Large Scale Image Retrieval, Also Support Python and MATLAB. Change Log 2015.07.04 A new LS

Aug 11, 2022
­čĆůState-of-the-art learned data structure that enables fast lookup, predecessor, range searches and updates in arrays of billions of items using orders of magnitude less space than traditional indexes

The Piecewise Geometric Model index (PGM-index) is a data structure that enables fast lookup, predecessor, range searches and updates in arrays of bil

Aug 7, 2022
ring-span lite - A C++yy-like ring_span type for C++98, C++11 and later in a single-file header-only library

ring-span lite: A circular buffer view for C++98 and later Contents Example usage In a nutshell Dependencies Installation Synopsis Reported to work wi

May 23, 2022
C++ implementation of a fast hash map and hash set using robin hood hashing

A C++ implementation of a fast hash map and hash set using robin hood hashing The robin-map library is a C++ implementation of a fast hash map and has

Aug 1, 2022
A drop-in replacement for std::list with 293% faster insertion, 57% faster erasure, 17% faster iteration and 77% faster sorting on average. 20-24% speed increase in use-case testing.

plf::list A drop-in replacement for std::list with (on average): 293% faster insertion 57% faster erasure 17% faster iteration 77% faster sorting 70%

Jul 25, 2022
A faster drop-in replacement for giflib. It uses more RAM, but you get more speed.

GIFLIB-Turbo What is it? A faster drop-in replacement for GIFLIB Why did you write it? Starting in the late 80's, I was fascinated with computer graph

Jun 9, 2022
Given a set of images, LeastAverageImage generates the least average -- the opposite of the average.
Given a set of images, LeastAverageImage generates the least average -- the opposite of the average.

LeastAverageImage Given a set of images, LeastAverageImage generates the least average -- the opposite of the average. More information about the prog

Apr 12, 2022
Improved and configurable drop-in replacement to std::function that supports move only types, multiple overloads and more

fu2::function an improved drop-in replacement to std::function Provides improved implementations of std::function: copyable fu2::function move-only fu

Aug 3, 2022
D2R mod generator. Provide quick tool to generate .txt files to change game balance: increase drop, monster density or even randomize items.
D2R mod generator. Provide quick tool to generate .txt files to change game balance: increase drop, monster density or even randomize items.

Diablo 2 mod generator Generator is inspired by d2modmaker. It provides fast and easy way to create mod without any modding knowledge. Features includ

Jul 28, 2022
By putting in a lot of speed, the speed sequence is sorted and divided, three types of speed interval distribution maps are generated.(including broken line graph,histogram and curve graph)

Auto-drawing-speed-range-map By putting in a lot of speed, the speed sequence is sorted and divided, three types of speed interval distribution maps a

May 14, 2022
mold is a faster drop-in replacement for existing Unix linkers
mold is a faster drop-in replacement for existing Unix linkers

mold: A Modern Linker mold is a faster drop-in replacement for existing Unix linkers. It is several times faster than LLVM lld linker, the second-fast

Aug 11, 2022
Bitset Sort, a faster std::sort replacement.

Bitset Sort Bitset Sort is a variant of quick sort, specifically BlockQuickSort. Bitset Sort uses a carefully written partition function to let the co

Jul 7, 2022
SIDKick -- the first complete SID 6581/8580-drop-in-replacement that you can build yourself
SIDKick -- the first complete SID 6581/8580-drop-in-replacement that you can build yourself

.- the first complete SID-drop-in-replacement that you can build yourself -. SIDKick is a drop-in replacement for the SID sound chips used in C64s and

Aug 2, 2022
An Aspiring Drop-In Replacement for Pandas at Scale
An Aspiring Drop-In Replacement for Pandas at Scale

Legate Pandas Legate Pandas is a distributed and accelerated drop-in replacement of Pandas. Legate Pandas enables high-performance, scalable execution

Aug 9, 2022
An Aspiring Drop-In Replacement for NumPy at Scale
An Aspiring Drop-In Replacement for NumPy at Scale

Legate NumPy Legate NumPy is a Legate library that aims to provide a distributed and accelerated drop-in replacement for the NumPy API on top of the L

Aug 4, 2022
A simple "no frills" drop-in replacement PCB for the KBDfans 67mkII / 67lite
 A simple

67mk_E A simple "no frills" drop-in replacement PCB for the KBDfans 67mkII / 67lite KiCAD PCB files Gerbers for PCB production JLCPCB BOM JLCPCB CPL V

May 20, 2022
Amiga 1200 keyboard MPU drop-in replacement pcb
Amiga 1200 keyboard MPU drop-in replacement pcb

A1200_keyb_MPU Amiga 1200 keyboard MPU drop-in replacement pcb As the 68HC05 (p/n 391508-01) used in the Amiga 1200 is getting to be very expensive, I

Jun 22, 2022