Skip to content

Instantly share code, notes, and snippets.

@lallousx86
Created June 13, 2017 01:23
Show Gist options
  • Save lallousx86/7ee67f56e7c92ff172f550d7dcd29a2e to your computer and use it in GitHub Desktop.
Save lallousx86/7ee67f56e7c92ff172f550d7dcd29a2e to your computer and use it in GitHub Desktop.
std::map's lower_bound() test
// Test std::map's lower_bound()
#include <stdio.h>
#include <map>
#include <iostream>
struct range_t
{
unsigned long a;
unsigned long b;
bool contains(unsigned long x)
{
return x >= a && x <= b;
}
};
typedef std::map<unsigned long, range_t *> eud_items_lookup_t;
range_t test_items[] =
{
{5, 8},
{10, 12},
{14, 18},
{22, 26}
};
int main()
{
// Convert to map
eud_items_lookup_t lookup;
for (auto &item : test_items)
lookup[item.a] = &item;
auto items_end = std::end(lookup);
unsigned long fk;
while (true)
{
std::cin >> fk;
if (fk == 0)
break;
// return an entry whose key is not less than the search key
auto lb = lookup.lower_bound(fk);
// Two cases:
// 1. No key greater then fk
// 2. Did not find the exact key
if (lb == items_end || lb->second->a != fk)
{
// Check the previous element
--lb;
if (lb == items_end || !lb->second->contains(fk))
{
printf("not found\n");
continue;
}
}
printf("%d - %d\n",
lb->second->a,
lb->second->b);
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment