Как искать целое число во вложенном классе с функцией STL binary_search? - PullRequest
Новая
       7

Как искать целое число во вложенном классе с функцией STL binary_search?

0 голосов
/ 16 января 2020

Как найти целое число во вложенном классе с помощью функции binary_search STL? Можно ли выполнить бинарный поиск по вектору vITems для поиска идентификатора класса продукта? В настоящее время я должен заполнить массив std::vector<Product> vProd внутри класса Order, чтобы использовать функцию binary_search.

Я провел много исследований по этому вопросу, но мне не удалось решить эту проблему. 

 #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;
}

Ответы [ 2 ]

1 голос
/ 16 января 2020

Вы можете использовать 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;

Обратите внимание, что [vItems.begin(), vItems.end()) должен представлять действительный диапазон элементов, отсортированных по Prod.Id или по крайней мере разделенных по Prod.Id < idProd. Если это условие не выполняется, поведение std::lower_bound не определено.

Как правильно выполнить этот порядок?

Если диапазон не сортируется, правильный способ - использовать 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());

Сортировка перед каждым двоичным поиском не имеет смысла: двоичный поиск занимает O(log n) времени, но сортировка занимает O(n log n) время. Это хуже, чем линейная сложность времени O(n), предоставляемая std::find_if.

1 голос
/ 16 января 2020

С помощником: 

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

Вы можете сделать с пользовательским компаратором: 

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; }
                  });
}

Демо

...