23
\$\begingroup\$

I've decided to implement Python's any in C++. I've gone about this using templates to allow multiple types of data to be passed, instead of overloading the function multiple times. This is my first time using templates so I would really like feedback about my usage of them. I'm also fairly new with references and pointers, so I would like some criticism about my use of them as well. Of course, anything else is on the table and appreciated.

While writing this program, I realized std::any_of existed. So yes, I do know there's already a built-in method for this.

any.hpp

#ifndef ANY_HPP_INCLUDED
#define ANY_HPP_INCLUDED

/**
 * @author Ben Antonellis
**/

#include <vector>
#include <iostream>

/**
 * Returns True if any of the elements meet the callback functions parameters.
 * 
 * @param elements - A list of elements.
 * @param callback - Callback function to invoke on each element.
 * 
 * @return bool - True if parameters are met, False otherwise.
**/
template <typename List, typename Function>
bool any(List &elements, Function *callback) {
    for (auto element : elements) {
        if (callback(element)) {
            return true;
        }
    }
    return false;
}

#endif

And here's how I'm testing this function:

main.cpp

/**
 * @author Ben Antonellis
**/

#include "Any.hpp"

int main() {

    std::vector<double> doubleElements = {-1.0, -2.0, -3.0};
    std::vector<std::string> stringElements = {"Hello", "Goodbye", "Testing 123"};

    auto doubleFunc = [] (double number) {
        return number < 0;
    };
    auto stringFunc = [] (std::string string) {
        return string.length() >= 5;
    };

    /* Test Any Implementation */
    if (any(doubleElements, *doubleFunc)) {
        std::cout << "(any) Double Success." << std::endl;
    }
    if (any(stringElements, *stringFunc)) {
        std::cout << "(any) String Success." << std::endl;
    }

    return 0;
}

If you would like to compile and run, below is the script I'm using to compile and run this program.

run.sh

# Compile c++ program to .o file #
g++ -std=gnu++2a -c main.cpp # gnu++2a = Working draft for ISO C++ 2020 with GNU extensions #

# Compile .o file to executable #
g++ main.o -o app

# Run the executable #
./app

# Delete executable and .o files after running #
rm app main.o
\$\endgroup\$
  • 11
    \$\begingroup\$ Off-topic, but note that cppreference is a more up-to-date and (in general) high-quality community-driven documentation than cplusplus.com as far as I am concerned. \$\endgroup\$ – L. F. Mar 25 at 8:09
  • \$\begingroup\$ Agreed, I use cppreference almost exclusively. It ain't pretty, but it gets the job done :) \$\endgroup\$ – Will Crawford Mar 25 at 15:11
32
\$\begingroup\$

The algorithm looks correct.

Regarding the function signature, I'd make three changes:

  1. You're not modifying elements, so take it by constant reference rather than reference.
  2. You don't need to specify a pointer to Function, Function is already a template parameter, and non-pointers could be valid (ex: a class with a () operator).
  3. "callback" isn't a very useful name for this case. "predicate" would be better.

While this form is fine, I'd also include a version that takes a start/end iterator instead of a container.

Also, there's no reason to include vector or iostream in any.hpp - only include things that are necessary.

For completeness in the testing method, you should also test with an empty collection, and a collection with no matches.

| improve this answer | |
\$\endgroup\$
  • 2
    \$\begingroup\$ Although predicate is more specific, "callback" seems to have become a very common term to refer to the function passed to a higher-order function, regardless of its role in the algorithm. \$\endgroup\$ – Barmar Mar 25 at 16:29
  • 11
    \$\begingroup\$ @Barmar No, predicate implies both argument list and return type, and as such is idiomatic. \$\endgroup\$ – Captain Giraffe Mar 26 at 0:56
  • 5
    \$\begingroup\$ @Barmar: That also says predicate in the description. Callback is a broad term, as you note, and in C++ predicate is quite consistently used for any bool (T) functor. \$\endgroup\$ – MSalters Mar 26 at 12:19
  • 4
    \$\begingroup\$ @Barmar In they context of C++ (as well as other languages!) I'd expect a callback to be invoked predominantly for its side-effect. By contrast, and in addition to the other comments, I expect a predicate to be (logically) side-effect free. \$\endgroup\$ – Konrad Rudolph Mar 26 at 21:04
  • 4
    \$\begingroup\$ @Barmar C++ terminology is quite different from other programming languages ... In C++, "callback" is generally redefined to mean functions / function objects registered in event managers to react to certain events, or in similar contexts where the registered operations are invoked by external signals and mainly for side-effect; the one in ios_base is an example. Using callback when predicate is more appropriate sounds very anti-C++ish to my (possibly biased) C++-trained ears. \$\endgroup\$ – L. F. Mar 27 at 2:40
17
\$\begingroup\$

I think you did a pretty good job as a . In addition to what Errorsatz said:

  • Consider making element a const reference to prevent unnecessary copying: const auto& element : elements

  • You missed #include <string> in the test file.

  • std::endl flushes the buffer and causes performance degradation; use \n instead unless you need the flushing behavior.

  • Try to avoid compiler-specific nonstandard extensions, because they make your program non portable. -std=c++20 -pedantic-errors makes g++ go into conforming mode and disables these nonstandard extensions. It is also unnecessary to separate the compiling step from the linking step — g++ does it for you. And remember to turn on warnings! They help you spot many logical bugs in your program. My usual compiling directive looks like this:

    g++ main.cpp -o app -std=c++20 -Wall -Wextra -Werror -pedantic-errors
    

    (Sometimes I turn on -ftrapv to avoid inadvertently relying on integer overflow behavior as well.)

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

I see some of the issues include copying the data and passing by reference or const reference. Might I suggest following the STL's method of using iterators?

Your any function is essentially std::find_if using a container instead of iterators.

Rewriting it to use std::find_if reveals the differences:

template<typename List, typename Predicate>
bool any(List&& list, Predicate&& pred)
{
    return std::find_if(
                        begin(list),
                        end(list), 
                        std::forward<Predicate>(pred))
           != end(list);
}

Some of the issues I see with your initial implementation are:

  • Passing list as a non-const reference. This is fixed as in MSalters answer and shown above.
  • Passing the predicate as a pointer. We're using templates here, so let the predicate be anything it wants without being converted to a function pointer.
  • Reimplementing std::find_if (though I understand wanting to learn!)

My recommended method of implementing this without std::find_if is:

template<typename List, typename Predicate>
bool any(List&& list, Predicate&& pred)
{
    for(auto&& element : list) {
        if(pred(element))
            return true;
    }
    return false;
}
| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

Your header guard is:

#ifndef ANY_HPP_INCLUDED

The style I most commonly see in modern code is

#ifndef INCLUDED_ANY_HPP

(or, just leave off the _HPP part). The reason is that technically, C and C++ reserve all uppercase names matching E[A-Z].* to the implementation, for macros like EINVAL and EPERM. Of course in practice your implementation won't have a macro named EGG_HPP_INCLUDED; but it's theoretically safer, and just as easy, to write INCLUDED_EGG_HPP and eliminate that consideration entirely. Names beginning with I aren't reserved to the implementation.


template <typename List, typename Function>
bool any(List &elements, Function *callback) {

You should certainly pass elements by const reference, since you aren't planning to modify it. Consider this use-case:

std::vector<int> getPrimesBetween(int, int);
bool isOdd(int);
bool b = any(getPrimesBetween(3, 100), isOdd);

Since getPrimesBetween(3, 100) is an rvalue expression, your template taking by lvalue reference won't work.


Similarly, taking callback by pointer is weird. Take callbacks either by value (STL style) or by const reference (to avoid unnecessary copying). Consider:

std::vector<int> primes;
auto isOdd = [](int x) { return x % 2 != 0; };
bool b = any(primes, isOdd);

This won't compile with your template, because decltype(isOdd) is a class type (an unnamed lambda class type) that doesn't pattern-match against Function *.

You solve this in a very strange way that is nevertheless kind of cute:

bool b = any(primes, *isOdd);

What you probably meant to type here was &isOdd, not *isOdd. However, the latter also works, because the lambda type has no operator*, and therefore it undergoes implicit conversion to a scalar type so it can use the built-in *. The only implicit conversion available is the implicit conversion to a function-pointer type. So you convert the lambda to a function pointer, dereference the pointer to get a function reference, and then pass that function by value to your template, which decays it back into a function pointer, which happily pattern-matches against Function *.

Observe the difference between &isOdd and *isOdd here: https://godbolt.org/z/ehdbvw

Specifically, &isOdd and &isEven have different types, but *isOdd and *isEven have the same type.

By taking only function pointers, you're also preventing your template from ever being used with stateful lambdas:

auto isDivisibleBy(int n) { return [n](int x) { return x % n != 0; }; }
bool b1 = any(primes, isDivisibleBy(3));  // ERROR during deduction
auto isThreeven = isDivisibleBy(3);
bool b2 = any(primes, *isThreeven);  // ERROR no such operator
bool b3 = any(primes, &isThreeven);  // ERROR during instantiation

    for (auto element : elements) {

Since you don't intend to modify the elements, you might take them by const&; but actually you should take them by auto&&, because auto&& Always Works.


Putting it all together, you'd end up with something like

template<class List, class Function>
bool any(const List& elements, const Function& callback) {
    for (auto&& element : elements) {
        if (callback(element)) {
            return true;
        }
    }
    return false;
}

Personally I might use the names Range, Callable, and pred[icate] in place of List, Function, and callback... but I guess just putting that in writing makes it pretty plain which one of us has been steeped too long in the unhealthy waters of STL jargon. :)

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Errorsatz already mentioned the Functor type, but I'd like to argue for Functor&&.

As for testing, this is a case where you literally want to test edge cases. I.e. where the first or only the last element has the desired property. Two additional special cases to test would be a single element, matching or not matching. (Zero-one-many rule of thumb; your tests both have many=3 elements)

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ I don't think using perfect forwarding is appropriate in this case - the function object is called multiple times. Using a forwarding reference to capture rvalues and call the function object unforwarded (i.e., as an lvalue) is fine though. \$\endgroup\$ – L. F. Mar 28 at 4:06
2
\$\begingroup\$

I see one place where you could use a C++ comment:

    /* Test Any Implementation */

Because this comment only spans one line, I generally prefer to use a C++ comment instead:

    // Test Any Implementation
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.