Skip to content

JCash/containers

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

67 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Build Status macOS / Linux / Windows
master Build Status
dev Build Status

Containers

A collection of header only containers that I use

Disclaimer

This software is supplied "AS IS" without any warranties and support

License

The MIT license

A fast and small C++ implementation of a hash table

  • ~260 lines of code
  • Open addressing
  • Robin Hood collision resolving
  • Backward shift deletion
  • On par with Google's dense_hash_map

The jc::lower_bound and jc::upper_bound are about 1.6x - 2.3x faster than their STL counter parts.

The radix sort is a stable sort, which requires an output buffer of the same length. It is ~70 lines of code. It is 12%-25% faster than ska::sort

A fast and small C++ container for storing dynamic arrays.

  • ~140 lines of code
  • ~3x faster than std::vector, and ~2x faster than eastl::vector when using "push_back"
  • Otherwise same performance as the others
  • Header only C/C++ bit array

A small C++ ring buffer

  • ~120 lines of code
  • Can be resized (using realloc and copying items)

See benchmark page for more stats.

Performance examples for jc::HashTable.
Timings insert_random size=152 Timings get_random size=152

Performance examples for jc::Array.(See benchmark page for more stats)
Timings get_random size=8 Timings push_back size=8

Usage

jc::HashTable

struct SPod
{
    int     i;
    float   f;
};
typedef jc::HashTable<uint32_t, SPod> hashtable_t;

uint32_t numelements    = 1000; // The maximum number of entries to store
uint32_t load_factor    = 85; // percent
uint32_t tablesize      = uint32_t(numelements / (load_factor/100.0f));
uint32_t sizeneeded     = hashtable_t::CalcSize(tablesize);

void* mem = malloc(sizeneeded);

hashtable_t ht;
ht.Create(numelements, mem);

SPod value = { 1, 2.0f };
ht.Put(17, value);

Spod* pval = ht.Get(17);
assert( pval->i == 1 );
assert( pval->f == 2.0f );

hashtable_t it = ht.Begin();
hashtable_t itend = ht.End();
for(; it != itend; ++it)
{
    printf("key: %u  value: %d, %f\n", *it.GetKey(), it.GetValue()->i, it.GetValue()->f);
}

ht.Erase(17);

free(mem);

jc::Array

#include <jc/array.h>

jc::Array<int> a;
a.SetCapacity(4);
for(size_t i = 0; i < a.Capacity(); ++i)
    a.Push(i);

a.EraseSwap(0); // 0,1,2,3 -> 3,1,2

size_t sum = 0;
for(size_t i = 0; i < a.Size(); ++i)
    sum += a[i];

jc::RingBuffer

#include <jc/ringbuffer.h>

jc::RingBuffer<int> a;
a.SetCapacity(4);
for(size_t i = 0; i < a.Capacity(); ++i)
    a.Push(i);
// [0,1,2,3]

print("%d", a.Pop()); // -> 0
// [1,2,3]

a.Push(4);
// [1,2,3,4]

// Buffer is full.
// Either increase size...
if (a.Full())
    a.SetCapacity(6);
// [1,2,3,4]

a.Push(5);
a.Push(6);
// [1,2,3,4,5,6]

// ... or, if full again, use the PushUnchecked()
a.PushUnchecked(7);
// [2,3,4,5,6,7]

// Loop over the items
for(int i = 0; i < a.Size(); ++i)
    print("%d", a[i]);

About

A collection of containers that I use

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published