Priority scheduling algorithm using std::vector

Question

I'm learning priority scheduling algorithm and trying to implement it using std::vector. But the current performance of my code that's partially implemented is not that good since I'm performing sort operation every time I add a new process to std::vector list. Can somebody suggest ways I can improve my current partially implemented algorithm. This is my code:

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

void print_list(const std::vector<std::pair<int, int>>& pair_list) {
    for (const auto& pa : pair_list)
        std::cout << "process_ID: " << pa.first << ", " << "priority: " << pa.second << "\n";
    std::cout << std::endl;
}

void add_pro(int pro_ID, int pro_pri, std::vector<std::pair<int, int>>& pair_list) {
    pair_list.emplace_back(pro_ID, pro_pri);

    std::sort(pair_list.begin(), pair_list.end(), [=](std::pair<int, int>& a, std::pair<int, int>& b) {
        return a.second < b.second;
    });
}

bool check_pro_is_present(int pro_ID, const std::vector<std::pair<int, int>>& pair_list) {
    for (const auto& pa : pair_list) {
        if (pa.first == pro_ID)
            return true;
    }

    return false;
}

bool is_higher_pri_pro_present(int pro_ID, const std::vector<std::pair<int, int>>& pair_list) {
    if (pair_list.front().first == pro_ID)
        return false;

    return true;
}

int main() {
    std::vector<int> process_ID_list { 1345, 45, 5646, 52525, 55757, 23424, 68696, 55878, 667, 252 };
    std::vector<int> process_pri_list { 41, 334, 747, 41, 47, 7, 75, 544, 42, 6 };
    
    std::vector<std::pair<int, int>> pair_list;
    for (int i = 0; i < process_ID_list.size(); ++i) {
        int new_pro_ID = process_ID_list.at(i);
        int new_pro_pri = process_pri_list.at(i);

        if (!check_pro_is_present(new_pro_ID, pair_list))
            add_pro(new_pro_ID, new_pro_pri, pair_list);
        else
            std::cout << "process is already in list" << std::endl;

        print_list(pair_list);
    }

    int query_pro_ID = 1345;
    std::cout << std::boolalpha << is_higher_pri_pro_present(query_pro_ID, pair_list) << std::endl;

    return (EXIT_SUCCESS);
}

Answer 1

While comments have suggested more suitable types than std::vector, I'm going to assume that the use of this underlying type is a given, and suggest straightforward improvements without changing that.

The main performance concern is here:

void add_pro(int pro_ID, int pro_pri, std::vector<std::pair<int, int>>& pair_list) {
    pair_list.emplace_back(pro_ID, pro_pri);

    std::sort(pair_list.begin(), pair_list.end(), [=](std::pair<int, int>& a, std::pair<int, int>& b) {
        return a.second < b.second;
    });
}

It's wasteful to sort the vector every time we add an element, when we know it was sorted before we called this function. Instead, we need to insert the new element in the correct position.

void add_pro(int pro_ID, int pro_pri, std::vector<std::pair<int, int>>& pair_list)
{
    auto position = std::upper_bound(pair_list.begin(), pair_list.end(), pro_pri,
                                     [](auto pri, auto const& ele) { return pri < ele.second; });
    pair_list.emplace(position, pro_ID, pro_pri);
}

---

We use the type std::vector<std::pair<int, int>> a lot. It's worth giving it a name:

using priority_queue = std::vector<std::pair<int, int>>;

That makes changing the code easier, e.g. if we decide that process ids actually need to be unsigned long or something.

However, I observe that every function takes one of these as an argument. That suggests that we want a class with this vector as member, then convert those free functions to be members of that class.

---

Thank you for including the test program - that's always helpful in a review. There's a couple of small points:

for (int i = 0; i < process_ID_list.size(); ++i) {

We're mixing signed and unsigned types in this comparison (int and std::size_t). Obviously we should change int i to std::size_t i - and enable more compiler warnings.

       std::cout << "process is already in list" << std::endl;

Prefer to use std::cerr for error messages.

---

The pattern if (condition) return true; else return false; can simply be replaced with return condition. So:

bool is_higher_pri_pro_present(int pro_ID, const std::vector<std::pair<int, int>>& pair_list)
{
    return pair_list.front().first != pro_ID;
}

---

The loop in check_pro_is_present can be replaced with std::any_of:

bool check_pro_is_present(int pro_ID, const std::vector<std::pair<int, int>>& pair_list)
{
    return std::any_of(pair_list.begin(), pair_list.end(),
                       [pro_ID](auto const& e){ return e.first == pro_ID; });
}

---

Modified code

This is just a beginning - we'll probably want an initialiser-list constructor, and replace print() with operator<<(), but it's a start.

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

template<typename T, typename Priority = int>
class priority_queue
{
    std::vector<std::pair<T, Priority>> values = {};

public:
    void print(std::ostream &os) const {
        for (const auto& pa : values) {
            os << "process_ID: " << pa.first << ", "
               << "priority: " << pa.second << '\n';
        }
        std::cout << '\n';
    }

    void add(T t, Priority pri) {
        auto const position
            = std::upper_bound(values.begin(), values.end(),
                               pri,
                               [](auto const& pri, auto const& ele) { return pri < ele.second; });
        values.emplace(position, std::move(t), std::move(pri));
    }

    bool contains(int pro_ID) const
    {
        return std::any_of(values.begin(), values.end(),
                           [pro_ID](auto const& e){ return e.first == pro_ID; });
    }

    bool has_higher(int pro_ID) const
    {
        return values.front().first != pro_ID;
    }
};

int main()
{
    const std::pair<int,int> processes[]
        = { { 1345, 41 }, { 45, 334 }, { 5646, 747 },
            { 52525, 41 }, { 55757, 47 },
            { 23424, 7 }, { 68696, 75 }, { 55878, 544 },
            { 667, 42 }, { 252, 6 } };

    priority_queue<int, int> queue;
    for (auto const& p: processes) {
        if (queue.contains(p.first)) {
            std::cerr << p.first << " is already in list\n";
        } else {
            queue.add(p.first, p.second);
        }
        queue.print(std::cout);
    }

    int query_pro_ID = 1345;
    std::cout << std::boolalpha << queue.has_higher(query_pro_ID) << '\n';
}