Introduction

Getting Started

Programming Guides

API Reference

Additional Resources

DownwardStack.h
1 #pragma once
2 #include <vector>
3 
4 template <typename T>
5 class DownwardStack {
6 public:
7  DownwardStack(size_t initialCapacity = 0)
8  : pos(0)
9  {
10  Reserve(initialCapacity);
11  }
12 
13  void Reserve(size_t const amount)
14  {
15  if (items.size() < amount) {
16  size_t const oldSize = items.size();
17  size_t const newSpace = amount - oldSize;
18 
19  items.resize(amount);
20  T * data = items.data();
21 
22  assert(newSpace >= oldSize);
23  std::copy(
24  data + pos,
25  data + oldSize,
26  data + pos + newSpace);
27 
28  pos += newSpace;
29  }
30  }
31 
32  void Push(T const & item)
33  {
34  if (pos == 0) {
35  Reserve(std::max<size_t>(8, 2 * items.size()));
36  }
37  --pos;
38  items.data()[pos] = item;
39  }
40 
41  void Pop()
42  {
43  assert(Size() > 0);
44  Peek() = T();
45  ++pos;
46  }
47 
48  size_t Size() const
49  {
50  return items.size() - pos;
51  }
52 
53  T & Peek()
54  {
55  assert(Size() > 0);
56  return items.data()[pos];
57  }
58 
59  T const & Peek() const
60  {
61  assert(Size() > 0);
62  return items.data()[pos];
63  }
64 
65 private:
66  std::vector<T> items;
67  size_t pos;
68 };
Definition: DownwardStack.h:5