/dev/random

Ordered Symbol Table ADT in C++ map

C++’s ordered std::map (usually implemented with red-black trees), satisfies the requirements for the Ordered Symbol Table abstract data type.

Some examples of how the ST interface might be mapped and take advantage of a wrapped std::map and make use of an ordered symbol table’s relative key ordering:

  // Largest key less than or equal to key
  const K* floor(K key) {
    if (isEmpty())
      return nullptr;

    // lower_bound returns iterator to first element not less than key
    auto candidate = map.lower_bound(key);
    if (candidate == map.begin())
      return &candidate->first;

    return &(--candidate)->first;
  }

  // Smallest key greater than or equal to key
  const K* ceiling(K key) {
    if (isEmpty())
      return nullptr;

    // upper_bound returns iterator to the first element greater than key
    return &map.upper_bound(key)->first;
  }

  // Number of keys less than key
  // i == rank(select(i)) for all 0 <= i <= size() - 1
  int rank(K key) {
    return std::distance(map.begin(), map.lower_bound(key));
  }

  // Key of rank k
  // key == select(rank(key)) for all keys in map
  const K* select(int k) {
    int low = 0;
    int high = size() - 1;

    // binary search
    while (low <= high) {
      auto it = map.begin();
      int mid = low + ((high - low) / 2);

      std::advance(it, mid);
      int rank = std::distance(map.begin(), it);

      if (rank < k) {
        low = mid + 1;  // look to the right
      } else if (rank > k) {
        high = mid - 1;  // look to the left
      } else {
        return &it->first;
      }
    }

    return nullptr;
  }

  // Number of keys in [low, high]
  int size(K low, K high) {
    auto begin = map.lower_bound(low);
    auto end = map.upper_bound(high);

    return std::distance(begin, end);
  }

  // Keys in [low, high], in sorted order
  std::vector<K> keys(K low, K high) {
    auto begin = map.lower_bound(low);
    auto end = map.upper_bound(high);

    std::vector<K> res;
    for (auto it = begin; it != end; ++it) {
      res.push_back(it->first);
    }

    return res;
  }