title: How can I count the number of comparisons? (Hash Table)
body: <p>OK, so I am working from the book "Data Structures and other objects using C++ 4th Ed".  I am making a hash table that accepts the keys and hashes them into the correct spots using open addressing to resolve collisions. The code below is what I currently have.</p>
  
  <p>The Header File</p>
  
  <pre><code>#ifndef TABLE1_H
  #define TABLE1_H
  #include &lt;cstdlib&gt;    // Provides size_t
  
  
  {
  template &lt;class RecordType&gt;
  class table
  {
  public:
      // MEMBER CONSTANT -- See Appendix E if this fails to compile.
      static const std::size_t CAPACITY = 811;
      // CONSTRUCTOR
      table( );
      // MODIFICATION MEMBER FUNCTIONS
      void insert(const RecordType&amp; entry);
      void remove(int key);
      // CONSTANT MEMBER FUNCTIONS
      bool is_present(int key) const;
      void find(int key, bool&amp; found, RecordType&amp; result) const;
      std::size_t size( ) const { return used; }
  private:
      // MEMBER CONSTANTS -- These are used in the key field of special records.
      static const int NEVER_USED = -1;
      static const int PREVIOUSLY_USED = -2;
      // MEMBER VARIABLES
      RecordType data[CAPACITY];
      std::size_t used;
      // HELPER FUNCTIONS
      std::size_t hash(int key) const;
      std::size_t next_index(std::size_t index) const;
      void find_index(int key, bool&amp; found, std::size_t&amp; index) const;
      bool never_used(std::size_t index) const;
      bool is_vacant(std::size_t index) const;
  };
  }
  #include "table1.template" // Include the implementation.
  #endif
  </code></pre>
  
  <p>And the Template Class</p>
  
  <pre><code>template &lt;class RecordType&gt;
  const std::size_t table&lt;RecordType&gt;::CAPACITY; 
  
  template &lt;class RecordType&gt;
  const int table&lt;RecordType&gt;::NEVER_USED;
  
  template &lt;class RecordType&gt;
  const int table&lt;RecordType&gt;::PREVIOUSLY_USED;
  
  template &lt;class RecordType&gt;
  table&lt;RecordType&gt;::table( )
  {
      std::size_t i;
  
      used = 0;
      for (i = 0; i &lt; CAPACITY; ++i)
          data[i].key = NEVER_USED;  // Indicates a spot that's never been used.
  }
  
  template &lt;class RecordType&gt;
  void table&lt;RecordType&gt;::insert(const RecordType&amp; entry)
  // Library facilities used: cassert
  {
      bool already_present;   // True if entry.key is already in the table
      std::size_t index;        // data[index] is location for the new entry
  
      assert(entry.key &gt;= 0);
  
      // Set index so that data[index] is the spot to place the new entry.
      find_index(entry.key, already_present, index);
  
      // If the key wasn't already there, then find the location for the new entry.
      if (!already_present)
      {
          assert(size( ) &lt; CAPACITY);
          index = hash(entry.key);
          while (!is_vacant(index))
              index = next_index(index);
          ++used;
      }
  
      data[index] = entry;
  }
  
  template &lt;class RecordType&gt;
  void table&lt;RecordType&gt;::remove(int key)
  // Library facilities used: cassert
  {
      bool found;        // True if key occurs somewhere in the table
      std::size_t index;   // Spot where data[index].key == key
  
      assert(key &gt;= 0);
  
      find_index(key, found, index);
      if (found)
      {   // The key was found, so remove this record and reduce used by 1.
          data[index].key = PREVIOUSLY_USED; // Indicates a spot that's no longer in use.
          --used;
      }
  }
  
  template &lt;class RecordType&gt;
  bool table&lt;RecordType&gt;::is_present(int key) const
  // Library facilities used: assert.h
  {
      bool found;
      std::size_t index;
  
      assert(key &gt;= 0);
  
      find_index(key, found, index);
      return found;
  }
  
  template &lt;class RecordType&gt;
  void table&lt;RecordType&gt;::find(int key, bool&amp; found, RecordType&amp; result) const
  // Library facilities used: cassert.h
  {
      std::size_t index;
  
      assert(key &gt;= 0);
  
      find_index(key, found, index);
      if (found)
          result = data[index];
  }
  
  template &lt;class RecordType&gt;
  inline std::size_t table&lt;RecordType&gt;::hash(int key) const
  {
      return (key % CAPACITY);
  }
  
  template &lt;class RecordType&gt;
  inline std::size_t table&lt;RecordType&gt;::next_index(std::size_t index) const
  // Library facilities used: cstdlib
  {
      return ((index+1) % CAPACITY);
  }
  
  template &lt;class RecordType&gt;
  void table&lt;RecordType&gt;::find_index(int key, bool&amp; found, std::size_t&amp; i) const
  // Library facilities used: cstdlib
  {
  std::size_t count; // Number of entries that have been examined
  
  count = 0;
  i = hash(key);
  while((count &lt; CAPACITY) &amp;&amp; (data[i].key != NEVER_USED) &amp;&amp; (data[i].key != key))
  {
      ++count;
      i = next_index(i);
  }
  found = (data[i].key == key);
      // Tried adding  Counter = Counter +1.
      // Failed, reason in comments.
  }
  
  template &lt;class RecordType&gt;
  inline bool table&lt;RecordType&gt;::never_used(std::size_t index) const
  {
  return (data[index].key == NEVER_USED);
  }
  
  template &lt;class RecordType&gt;
  inline bool table&lt;RecordType&gt;::is_vacant(std::size_t index) const
  {
  return (data[index].key == NEVER_USED) || (data[index].key == PREVIOUSLY_USED);
  }
  </code></pre>
  
  <p>My question that I was hoping I could get some help with is, How would I keep track of the number of comparisons made to find each value in the table?  </p>
  
  <p>So far, I tried making a private member variable and increasing it for each iteration through the find_index loop, but that didn't work. My overall goal is to eventually graph the average number of comparisons Vs. the table density.  </p>