I think Keyle's answer (among others) brings home a basic point: a huge amount depends on how you do things. That link gave two answers for C++, but I have a hard time believing that anybody would normally write C++ that's much like either one. My first attempt would look something like this:
#include <iostream>
#include <vector>
#include <time.h>
class person {
int count_;
static int current_;
public:
person() : count_(++current_) {}
int count() { return count_; }
};
int person::current_ = 0;
typedef std::vector<person> plist;
class chain {
plist people_;
void check_wrap(std::vector<person>::iterator &p) {
if (p==people_.end())
p = people_.begin();
}
void advance(std::vector<person>::iterator &p, int places) {
for (int i=0; i<places; i++)
check_wrap(++p);
}
public:
chain(int length) : people_(length) {}
person *kill(int n) {
plist::iterator current = people_.begin();
while (people_.size()>1) {
advance(current, n);
current = people_.erase(current);
check_wrap(current);
}
return &(*current);
}
};
int main() {
const int ITER = 1000000;
clock_t start = clock();
for(int i = 0 ; i <ITER; i++) {
chain c(40);
c.kill(3);
}
clock_t end = clock();
std::cout << "Time per iterator: " << (((end - start) /(double)CLOCKS_PER_SEC/ITER)*1000000 << " microseconds.\n";
return 0;
}
(For portability I've used clock() instead of gettimeofday, but anybody who wants can easily change that back).
There are a couple of points about this that strike me as interesting. First, the code has gotten a lot shorter -- in fact, competitive as the shortest code shown. Second, the code has gotten quite a bit faster -- probably faster than anything but the specially optimiz
answered 2009-11-06T11:22:16.313