AceCommon  1.4.5
Arduino library for low-level common functions and features with no external dependencies
Functions
linearSearch.h File Reference
#include <stdint.h>
Include dependency graph for linearSearch.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Functions

template<typename X , typename K >
size_t ace_common::linearSearchByKey (size_t size, const X &x, K &&key)
 Perform a linear search for element 'x' on an abstract list of records. More...
 
template<typename X >
size_t ace_common::linearSearch (const X list[], size_t size, const X &x)
 Simplified version of linearSearchByKey() where the elements of the array and the searched element are both of type X. More...
 

Detailed Description

Templatized implementation of linear search function over an array of things, which is not necessarily sorted. If the array is sorted, you should consider using the binarySearchByKey() function instead.

Initially, I wrote a version of this for AceTime/src/ace_time/ZoneRegistrar, which got copied to AceTime/src/ace_time/LinkRegistrar, at which point it made sense to extract it into a templatized function to avoid multiple copies.

Normally, I wouldn't consider a linear search function to be worthy of extraction into a library but this file is conceptually similar to the binarySearch.h file.

Definition in file linearSearch.h.

Function Documentation

◆ linearSearch()

template<typename X >
size_t ace_common::linearSearch ( const X  list[],
size_t  size,
const X &  x 
)

Simplified version of linearSearchByKey() where the elements of the array and the searched element are both of type X.

So the key lambda expression can be just list[i].

This function assumes that 'operator==()' for type X is defined.

Template Parameters
Xtype of element in list
Parameters
listsorted list of elements of type X (accepts both const array or a pointer to the array)
sizenumber of elements
xelement to search for

Definition at line 91 of file linearSearch.h.

◆ linearSearchByKey()

template<typename X , typename K >
size_t ace_common::linearSearchByKey ( size_t  size,
const X &  x,
K &&  key 
)

Perform a linear search for element 'x' on an abstract list of records.

The 'key' is a function or lambda expression that retrieves the value of 'X' at index 'i' in the records.

This function assumes that 'operator==()' for the value type of key is defined.

Performance Note: Many compilers (all?) are not able to opimize away the function call overhead of the lambda expression. If performance is critical, you should copy and modify this code instead.

Template Parameters
Xtype of element to look for, assumed to be cheap to copy (e.g. a primitive type like an 'int' or 'uint32_t')
Klambda expression or function pointer that returns the 'X' value at index 'i'

Definition at line 67 of file linearSearch.h.