Re: Problems removing an element from a std::set using a reverse_iterator

On Jul 23, 7:03 pm, Greg Herlihy <gre...@pacbell.net> wrote:


I won't argue with your statement of conciseness and correctness, but
I don't agree regarding efficiency. The reason is simple; to find the
lower bound requires logarithmic time. If removing from right to left,
finding the upper bound requires constant time. It seems to me that
everything beyond that point would be essentially equivalent.

However, this is a nice theory, but it's needs to be demonstrated. I
wrote up a test driver to measure the speed efficiency of both
approaches. I ran my driver using a variety of configurations, and
removing using a reverse_iterator is more efficient every time (see
below for the source code for the test driver).

Now, if this is true, then by using your argument (regarding optimized
use of a particular container), I should be using a reverse_iterator
in my algorithm implementation. Unfortunately, Meyers' preferred
technique for doing so doesn't work (again, his other technique *does*
work), at least not on my compiler (g++ 3.4.2). You say that Meyers'
advice is not flawed, so then it seems to indicate that there is a
problem with g++. Do you agree?

Here's the test driver:

**********************************************************************
#include <set>
#include <iostream>

#include <sys/time.h>

using namespace std;

double
diffMs(
  const struct timeval& t1,
  const struct timeval& t2)
{
  return(1000.0 * (t2.tv_sec - t1.tv_sec) + 0.001 * (t2.tv_usec -
t1.tv_usec));
}

int
main(
  int argc,
  char** argv)
{
  typedef std::set<unsigned int> UIntSet;

  UIntSet uis;

  static const unsigned int UPPER_BOUND = 10000000U;

  cout << "Inserting " << UPPER_BOUND << " elements ..." << endl;

  for(unsigned int i = 0U ; i < UPPER_BOUND ; ++i)
  {
    (void)uis.insert(uis.end(), i);
  }

  static const unsigned int THRESHOLD = UPPER_BOUND - 5U;

  struct timeval t_start;

  struct timeval t_stop;

  cout << endl << "Erasing elements: " << flush;

  (void)gettimeofday(&t_start, static_cast<struct timezone*>(0));

#if 1

  for(UIntSet::reverse_iterator ri = uis.rbegin() ;
      ri != uis.rend() ;)
  {
    if((*ri) < THRESHOLD)
    {
      break;
    }

    uis.erase(--(ri.base()));
  }

#else

  uis.erase(uis.lower_bound(THRESHOLD), uis.end());

#endif

  (void)gettimeofday(&t_stop, static_cast<struct timezone*>(0));

  cout << diffMs(t_start, t_stop) << " (ms)" << endl;

  cout << endl << "Program exiting ..." << endl;

  return(0);
}

**********************************************************************

--
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated. First time posters: Do this! ]