Coding

Using C++ std::merge

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)

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.