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.

Overview

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 and function descriptions are here: https://plflib.org/list.htm

Issues
  • 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.

    opened by HSNB 5
  • 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.

    opened by TPS 5
  • 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.

    opened by HSNB 4
  • 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.

    opened by degski 4
  • 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.

    opened by Eremiell 4
  • 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.

    opened by gharveymn 3
  • 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
    		}
    
    opened by tsung-wei-huang 3
  • 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

    opened by dinghram 3
  • 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.

    opened by dinghram 2
  • 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.

    opened by dinghram 2
  • 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.

    opened by jdmairs 2
  • 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;
    }
    
    opened by cscrimge 2
Benchmarking a trivial replacement for std::vector

std::vector replacement benchmark Dependencies You'll need gnuplot and bash to run ./bench.sh. In addition to that, you'll need to have gcc and clang

Dale Weiler 8 Jul 2, 2022
C++ hash map and hash set which preserve the order of insertion

C++ hash map and hash set which preserves the order of insertion The ordered-map library provides a hash map and a hash set which preserve the order o

Thibaut Goetghebuer-Planchon 354 Jul 17, 2022
What the Package Does (One Line, Title Case)

inside The goal of insidecpp11 is to do fast point in polygon classification, with cpp11. We are comparing a few ways of implementing this, essentiall

diminutive 3 Feb 11, 2022
What the Package Does (One Line, Title Case)

--- output: github_document --- <!-- README.md is generated from README.Rmd. Please edit that file --> ```{r, include = FALSE} knitr::opts_chunk$set

diminutive 2 Feb 11, 2022
libsais is a library for linear time suffix array and burrows wheeler transform construction based on induced sorting algorithm.

libsais libsais is a library for fast (see Benchmarks below) linear time suffix array and Burrows-Wheeler transform construction based on induced sort

Ilya Grebnov 93 Jul 26, 2022
Sorting data on a stack with a limited set of instructions

push_swap Sorting data on a stack with a limited set of instructions Final Score: 125/100 Average 100 set speed: 575 Actions (Minimum 490 / Maximum 61

null 13 Jun 28, 2022
Repository containing all the sorting algorithms.

Sorting-Algorithms Repository containing all the sorting algorithms. Bubble Sort Bubble Sort is a simple algorithm which is used to sort a given set o

Rimpi Rani Baruah 3 Aug 29, 2021
A collection of multiple types of lists used during pentesting, collected in one place. List types include usernames, passwords, combos, wordlist and may more..

Access list is a collection of multiple types of lists used during pentesting, collected in one place, created by Undercode This list include a collec

UNDERCODE UTILITIES 7 Jan 6, 2022
A C++ data container replicating std::queue functionality but with better performance.

A data container replicating std::queue functionality but with better performance than standard library containers in a queue context. C++98/03/11/14/etc-compatible.

Matt Bentley 22 May 14, 2022
A C++ data container replicating std::stack functionality but with better performance than standard library containers in a stack context.

plf::stack A data container replicating std::stack functionality but with better performance than standard library containers in a stack context. C++9

Matt Bentley 48 Jul 24, 2022
Variant - C++17 `std::variant` for C++11/14/17

MPark.Variant C++17 std::variant for C++11/14/17 Introduction MPark.Variant is an implementation of C++17 std::variant for C++11/14/17. Based on my im

Michael Park 558 Aug 5, 2022
Finite State Machine implementation using std::variant

mp::fsm Implementation of Finite State Machine presented by me on CppCon 2018 in a talk Effective replacement of dynamic polymorphism with std::varian

Mateusz Pusz 63 Aug 3, 2022
Linear Linked List Library

list.h Implementations for singly-linked and doubly-linked list functions. Basic Working Example #include <stdio.h> #include <stdlib.h> #include "list

Nick Bulischeck 42 Jul 22, 2022
Tuplex is a parallel big data processing framework that runs data science pipelines written in Python at the speed of compiled code

Tuplex is a parallel big data processing framework that runs data science pipelines written in Python at the speed of compiled code. Tuplex has similar Python APIs to Apache Spark or Dask, but rather than invoking the Python interpreter, Tuplex generates optimized LLVM bytecode for the given pipeline and input data set.

Tuplex 781 Aug 1, 2022
Total 21 math problem solved by c language with 4 types of functional reference. Also added circular repeated linked list system of Data structure.

C-ProblemSolve Total 21 math problem solved by c language with 4 types of functional reference. Also added circular repeated linked list system of Dat

MH Miyazi 3 Aug 28, 2021
Own implementation of a linked list stack in C++.

Linked-List-Stack-CPP Own implementation of a linked list stack in C++. This is my manual implementation of a linked list stack. This stack is abstrac

Adam Peters 1 Oct 21, 2021
linked list implementation (C++)

linked-list linked list implementation (C++) author's name: Artem Kolpakov date: 06/06/2021 Hello there! Here is important information about my linked

Artem Kolpakov 1 Dec 28, 2021
HashTableBenchmark - A simple cross-platform speed & memory-efficiency benchmark for the most common hash-table implementations in the C++ world

Hash-Tables Benchmarks This repository contains a bunch of extendable benchmarks mostly for following containers: std:unordered_map from STL. google::

Unum 8 Jul 11, 2022
Data Structure Studying Group: array, linked list, stack, queue, deque, tree, graph. Summary of these concepts are descripted in the markdown files.

DATA_STRUCTURE STUDY ?? CURRICULUM ✔️ Day1 array linked list ✔️ Day2 circular linked list double linked list polynomial addtion reverse linked list ✔️

Soyeon Kim 3 Jul 22, 2022