C++: Data structure for efficient insertion and retrieval of custom data

I'm having a situation in C++ (on Windows) where I need to keep a set of pair of int: pair where start values are unique (we need not be concerned with this). The operations required are:

  • insert pair
  • retrieve pair X: this should return the pair Y where Y's start < X's start < X's end < Y's end. If Y doesn't exist, return false.

The basic solution is to simply keep a set of pairs. For retrieval, we'll iterate sequentially through the set to check. This is O(n).

I'm looking for a better solution. I currently see 2 candidate data structures:

  1. Sorted vector
  2. STL's set (internally implemented as binary search tree?)

Sorted Vector: Pros: can customize the binary search to support the retrieval operation. This is O(logn) Cons: how to efficiently insert a new pair to maintain the sorted order. How to avoid a re-sorting cost of O(nlogn)?

Set: Pros: Easy insertion using the standard insert method. This is O(1)? Cons: How to avoid the sequential search? How to do better than O(n)?

Thanks for your advice.

I'm also open to any other structures that can efficiently (1st criterion is speed; 2nd is memory) support the 2 operations mentioned above.


It isn't clear whether the ranges can overlap, but if they can't, then this should work. I've included a complete example with tests.

#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <map>

struct RangeContainer {
  typedef std::map<int,int> RangeMap;
  typedef std::pair<int,int> Range;

  void insert(const Range &range)

  Range find(const Range &x) const
    RangeMap::const_iterator iter = range_map.upper_bound(x.second);
    if (iter==range_map.begin()) {
      return invalidRange();
    Range y = *iter;
    if (y.first<x.first && x.second<y.second) {
      return y;

    return invalidRange();

  static Range invalidRange()
    return Range(INT_MAX,INT_MIN);

  RangeMap range_map;

static void test1()
  RangeContainer c;
  typedef RangeContainer::Range Range;

int main(int argc,char **argv)
  return EXIT_SUCCESS;

Need Your Help

android Two buttons to webpage links

android eclipse button android-intent

I have been on this for a while now (3 days). I am trying to use Eclipse to make an android app. I want to have two image buttons. Each one linking to a different site. I haven't been able to do it...

How to include template within a directive template?

javascript angularjs templates angularjs-directive angularjs-ng-include

How can one include a .html template within an angular directive's template?