Dumping the contents inside the following objects.

[lilzz]

I would like to dump the content inside the object tmp_np which is a UllmanSet which if you know a key then you know the position and if you know the position , you know the key. Is there a standard C++ container that's similar to the Ullmanset. Ullmanset 's index starts at 0 and Ullmanset1's index start at 1.

and also dump the content of frontierq which is a PriorityQ class.
The priority queue is implemented as followed. I like to print out the values inside the queue using std::cout.

Code: Select all

UllmanSet tmp_np;

template<unsigned B>
class BasedUllmanSet
{
  size_t n;
  std::vector<int> key;
  BasedVector<unsigned, B> pos;

public:
  BasedUllmanSet()
    : n(0)
  {}
  BasedUllmanSet(size_t cap)
    : n(0), key(cap), pos(cap)
  {}

  size_t capacity() const { return key.size(); }
  size_t size() const { return n; }
  bool empty() const { return n == 0; }
  void clear() { n = 0; }
  void resize(size_t cap)
  {
    key.resize(cap);
    pos.resize(cap);
    n = 0;
  }

  bool contains(int k) const
  {
    unsigned p = pos[k];
    return (p < n
            && key[p] == k);
  }











      PriorityQ<std::pair<int, int>, Comp> frontierq;

    class Comp
    {
    public:
      Comp() {}

      bool operator()(const std::pair<int, int> &lhs,
                      const std::pair<int, int> &rhs) const
      {
        return (lhs.second > rhs.second
                || (lhs.second == rhs.second
                    && lhs.first > rhs.first));
      }
    };

    class PriorityQ
    {
    public:
      Comp comp;
      std::vector<T> v;
      unsigned n;

    public:
      PriorityQ() : n(0) {}
      PriorityQ(Comp comp_) : comp(comp_), n(0) {}

      size_t size() const { return n; }
      void clear() { n = 0; }
      bool empty() { return n == 0; }

      void push(const T &x)
      {
        assert(v.size() >= n);
        if (v.size() == n)
          v.push_back(x);
        else
          v[n] = x;
        ++n;
        std::push_heap(&v[0], &v[n], comp);
      }
      const T &pop()
      {
        assert(n > 0);
        std::pop_heap(&v[0], &v[n], comp);
        --n;
        return v[n];
      }
      const T &top()
      {
        assert(n > 0);
        return v[0];
      }
    };

[AndyD]

Dump UllmanSet tmp_np;

Code: Select all

for (int i = 0 ; i < tmp_np.size() ; ++i)
{
    std::cout << tmp_nm.ith(i) << "\n";
}

Using the supplied interface, there is no way to iterate through PriorityQ without removing the items from the queue.

Code: Select all

PriorityQ<std::pair<int, int>, Comp> frontierq;

for (int i = 0 ; i < frontierq.n ; ++i)
{
    auto pair = frontierq.v[i];
    std::cout << pair.first << ", " << pair.second << "\n";
}

...Is there a standard C++ container that's similar to the Ullmanset...

Yes, std::set<int> ... The Ullmanset is a set, which is optimized for lookup. However, it is a set. There is a difference between interface and implementation.