There have been a few times that I needed 2 vectors to be … merged… and they had to be ordered.
It’s simple when you have a plain old type, and are using the back_inserter to append the contents of each vector to the end of the merged vector, but what if you want to use your custom class? And what if you need a custom means to sort the merged vector?
You can use a predicate function to put the items in the correct order in the merged vector.
The format for the predicate function is bool FunctionName(const T& a, const T& b) where T is the custom type that you are working with.
In the example I provide, I’m using a lambda, and the custom class is task:
// Returns ?true if the first argument should be ordered before the second argument
auto cmp = [](const std::shared_ptr<task> &a, const std::shared_ptr<task> &b) -> bool {
// returns ?true if the first argument is less than (i.e. is ordered before) the second.
if (a->get_due_by() == b->get_due_by())
return a->get_priority() > b->get_priority();
return (a->get_due_by() < b->get_due_by());
};The example I wrote up is a simple todo list, with 2 vectors, one holding my personal tasks and a second holding work tasks.
I sort both of the vectors before merging them, which is actually an important step:
std::sort(personal_tasks.begin(), personal_tasks.end(), cmp);
std::sort(work_tasks.begin(), work_tasks.end(), cmp);And then to merge the 2 vectors, you use the templated merge function:
// Create another vector, which is big enough to accept the 2 vectors.
todos_t merged_tasks(personal_tasks.size() + work_tasks.size(), std::shared_ptr<task>());
std::merge(personal_tasks.begin(), personal_tasks.end(), work_tasks.begin(), work_tasks.end(), merged_tasks.begin(), cmp);That’s about it.
Below is the complete source file.
I used CMake to build the project. For those who don’t know how to use CMake, there are a lot of resources on the internet to use it.
#include <algorithm>
#include <iostream>
#include <iterator>
#include <memory>
#include <vector>
/************************************************************************/
enum class priority_t : int
{
unknown = 0,
low,
medium,
high
};
/************************************************************************/
std::string get_priority_name(const priority_t &priority)
{
switch (priority)
{
case priority_t::unknown:
return "Unknown";
case priority_t::low:
return "Low";
case priority_t::medium:
return "Medium";
case priority_t::high:
return "High";
default:
return "";
}
}
/************************************************************************/
class task
{
public:
task(const std::string &desc, const time_t &due_by, const priority_t &priority)
: m_desc(desc), m_due_by(due_by), m_priority(priority)
{
;
}
~task() { ; }
std::string_view get_desc() const { return m_desc; }
time_t get_due_by() const { return m_due_by; }
priority_t get_priority() const { return m_priority; }
private:
task() { ; }
std::string m_desc;
time_t m_due_by;
priority_t m_priority = priority_t::unknown;
};
using todos_t = std::vector<std::shared_ptr<task>>;
/************************************************************************
Creates a time_t using the supplied hour and minute.
The date will be set to the current date.
*/
time_t create_time(const int hour, const int minute)
{
// Get the current UTC time
time_t result;
time(&result);
// Set up a tm struct so that we can mod the hour and minutes
struct tm *timeinfo;
timeinfo = localtime(&result);
timeinfo->tm_hour = hour;
timeinfo->tm_min = minute;
// Fill in the struct and return the time_t
return mktime(timeinfo);
}
/************************************************************************
Helper function to reduce the clutter in the code.
This is just an example, so we are using the current year-month-day.
*/
void add_task(todos_t &container, const std::string desc, const int hour, const int minute, const priority_t priority)
{
container.push_back(std::make_shared<task>(desc, create_time(hour, minute), priority));
}
/************************************************************************/
int main(int, char **)
{
todos_t personal_tasks;
add_task(personal_tasks, "Meditate (3)", 12, 30, priority_t::medium);
add_task(personal_tasks, "Answer emails (3)", 12, 30, priority_t::low);
add_task(personal_tasks, "Go to gym (0)", 7, 30, priority_t::high);
todos_t work_tasks;
add_task(work_tasks, "Respond to Slack messages (1)", 9, 00, priority_t::low);
add_task(work_tasks, "Gossip at watercooler (4)", 13, 00, priority_t::unknown);
add_task(work_tasks, "Implement new qsort that is actually readable (2)", 11, 00, priority_t::medium);
// Returns ?true if the first argument is less than (i.e. is ordered before) the second.
auto cmp = [](const std::shared_ptr<task> &a, const std::shared_ptr<task> &b) -> bool {
// returns ?true if the first argument is less than (i.e. is ordered before) the second.
if (a->get_due_by() == b->get_due_by())
return a->get_priority() > b->get_priority();
return (a->get_due_by() < b->get_due_by());
};
std::sort(personal_tasks.begin(), personal_tasks.end(), cmp);
std::sort(work_tasks.begin(), work_tasks.end(), cmp);
// Create another vector, which is big enough to accept the 2 vectors.
todos_t merged_tasks(personal_tasks.size() + work_tasks.size(), std::shared_ptr<task>());
std::merge(personal_tasks.begin(), personal_tasks.end(), work_tasks.begin(), work_tasks.end(), merged_tasks.begin(), cmp);
printf("%-60s %-20s %-20s \n", "Desc", "Priority", "Datetime");
for (const auto &item : merged_tasks)
{
time_t val = item->get_due_by();
printf("%-60s %-20s %-20s", item->get_desc().data(), get_priority_name(item->get_priority()).c_str(), ctime(&val));
}
}Here is a minimal CMakeLists.txt file to build the above code:
cmake_minimum_required(VERSION 3.0.0)
project(merge_example VERSION 0.1.0)
set(CMAKE_C_STANDARD 11)
set(CMAKE_CXX_STANDARD 20)
include(CTest)
enable_testing()
add_executable(merge_example main.cpp)
set(CPACK_PROJECT_NAME ${PROJECT_NAME})
set(CPACK_PROJECT_VERSION ${PROJECT_VERSION})
include(CPack)