AceCommon
1.5.2
Arduino library for low-level common functions and features with no external dependencies
|
Templatized implementation of linear search function over an array of things, which is not necessarily sorted. More...
#include <stdint.h>
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... | |
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.
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.
X | type of element in list |
list | sorted list of elements of type X (accepts both const array or a pointer to the array) |
size | number of elements |
x | element to search for |
Definition at line 91 of file linearSearch.h.
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.
X | type of element to look for, assumed to be cheap to copy (e.g. a primitive type like an 'int' or 'uint32_t') |
K | lambda expression or function pointer that returns the 'X' value at index 'i' |
Definition at line 67 of file linearSearch.h.