Vector back inserter example + algorithm

The problem is pretty simple: there is a list of time ranges for meetings and need to show the meetings as continuous block in calendar.

70940aec3ea953621db1b8faf619a5ca_2

As per modern c++ I have used std::back_inserter_iterator for vector instead of passing vector by value or by reference. This approach is much cleaner, modern and saves a lot of copying of data compared to old style.

// i/p: [(0, 1), (3, 5), (4, 8), (10, 12), (9, 10)]
// o/p: [(0, 1), (3, 8), (9, 12)]

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

struct Meeting; // define meeting

using it = std::vector<Meeting>::iterator;
// use an back inserter iterator to pass as function argument instead
// of passing vector by reference or creating vector on heap
using bi = std::back_insert_iterator<std::vector<Meeting>>;

struct Meeting{
  int start_time, end_time;
  // default constructor
  Meeting() = default;
 // parameterized constructor
  Meeting(int start_time, int end_time):start_time{start_time},end_time{end_date}{}
  
  // override < operator used for sorting.
  bool operator <(const Meeting &other) const{
    return start_date < other.start_date;
  }

static void merge(it start, it finish, bi merged_meeting_bi){
  int start_time = start->start_time;
  int end_time = start->end_time;
  while(start < finish){
    start++;
    if(start->start_time > end_time){
      merged_meeting_bi = {start_time, end_time}; // create meeting using parameterized constructor
      start_time = start->start_time; 
      end_time = start->end_time;
    }else{
      end_time = std::max(start->end_time, end_time);
     }
   }
  }
};

int main(){
  std::vector<Meeting> meetings{{0, 1}, {3, 5}, {4, 8}, {10, 12}, {9, 10}};
  std::vector<Meeting> merged_meetings;
  auto bi = std::back_insert_iterator<std::vector<Meeting>>(merged_meetings);
  auto start = meetings.begin();
  auto finish = meetings.end();
  // sort by first time
  std::sort(start, finish);
  
for(const auto &meeting : meetings){
std::cout << meeting.start_time << ' ' << meeting.end_time << '\n';
}
Meeting::merge(start, finish, bi);

for(const auto & meeting: merged_meetings){
std::cout << meeting.start_time << ' ' << meeting.end_time << '\n';
}
return 0;
}

Author: Saurabh Purnaye

Sr. Developer @NYSE @ICE_Markets. Low Latency Trading, Linux, C++, Python, Ruby. pursuing certificate in #QuantFinance and Passed CFA L1

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s