How to search for an integer within a nested class with the binary_search STL function?

Question

How to search for an integer within a nested class with the binary_search STL function? Is it possible to do a binary search on the vector vITems to search for the product class ID? Currently, I have to populate a std::vector<Product> vProd array inside the Order class to use the binary_search function.

I did a lot of research on the subject, but I was unsuccessful in solving the problem.

 #include <iostream>
    #include <algorithm>
    #include <vector>

    class Product {
    public:

        int Id;
        std::string Name;

        Product(int idProd, const std::string &nameProd) : Id(idProd), Name(nameProd) {}
        Product(int idProd) : Id(idProd)  {} // Required for lambda function to work on binary_search function
    };

    class Item {
    public:

        Product Prod;
        int Number;

        Item(Product &prod, int numProd) : Prod(prod), Number(numProd) {}
    };

    class Order{
    private:
        std::vector<Item> vItems;

    public:

        bool consultProd(int idProd) const {
            std::vector<Product> vProd;
            size_t total = vItems.size();

            for(size_t i = 0; i < total; i++)
                vProd.push_back(vItems[i].Prod);


            bool yesId = binary_search( vProd.begin(), vProd.end(), idProd,
                                   []( const Product &p1, const Product &p2)
                                    {
                                        return p1.Id < p2.Id;
                                    } );

            return yesId;
        }


        void setItem(Item &it){
            vItems.push_back(it);
        }

    };


    int main()
    {
        //----------------------------------------------------------------
        Product p1(1, "aaa"), p2(2, "bbb"), p3(3, "ccc"), p4(4, "ddd");

        Item it1(p1, 1), it2(p2, 3), it3(p3, 3), it4(p4, 7);

        Order ord;

        ord.setItem(it1);
        ord.setItem(it2);
        ord.setItem(it3);
        ord.setItem(it4);
        //----------------------------------------------------------------

        if( !ord.consultProd(2) )
            ord.setItem(it2);
        else
          std::cout << "Warning: Product already included in the order.\n";

        system("pause");


        return 0;
}

Answer 1

You can use std::lower_bound:

const auto item_it = std::lower_bound(vItems.begin(), vItems.end(), idProd,
    [](const Item& item, int id) { return item.Prod.Id < id; });

const bool yesId = (item_it != vItems.end() && item_it->Prod.Id == idProd);
return yesId;

Note that [vItems.begin(), vItems.end()) should represent a valid range of items sorted by Prod.Id or at least partitioned with respect to Prod.Id < idProd. If this condition is not fulfilled, the behaviour of std::lower_bound is undefined.

---

What is the correct way to do this ordering?

If the range is not sorted, the correct way is to use std::find_if:

const auto item_it = std::find_if(vItems.begin(), vItems.end(), 
    [idProd](const Item& item) { return item.Prod.Id == idProd; });

const bool yesId = (item_it != vItems.end());

Sorting before each binary search doesn't make sense: binary search takes O(log n) time, but sorting takes O(n log n) time. This is worse than linear time complexity O(n) provided by std::find_if.

Answer 2

With helper:

template<class... Ts> struct overloaded : Ts... { using Ts::operator()...; };
template<class... Ts> overloaded(Ts...) -> overloaded<Ts...>;

You might do with custom comparer:

bool consultProd(int idProd) const {
    return binary_search(
        vItems.begin(),
        vItems.end(),
        idProd,
        overloaded{[](int id, const Item& item) { return id < item.Prod.Id; },
                   [](const Item& item, int id) { return item.Prod.Id < id; }
                  });
}

Demo