Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
C++ Ranges
#include <cstdint>
#include <iostream>
template <typename T>
class DInputRange
{
public:
struct iterator
{
const T* r;
iterator(T* rng) : r(rng) {}
auto operator*() -> decltype(r->front()) const { return static_cast<const T*>(r)->front(); }
void operator++() { ((T*)r)->popFront(); }
bool operator!=(iterator) const { return !static_cast<const T*>(r)->empty(); }
};
iterator begin() { return static_cast<T*>(this); }
iterator end() { return nullptr; }
};
int bitcount(uint64_t v)
{
#ifdef _MSC_VER
unsigned long r = 0;
_BitScanForward64(&r, v);
return (int)r;
#else
return __builtin_ctzll(v);
#endif
}
// D-style input range, consumes input
class DBitRange : public DInputRange<DBitRange>
{
public:
explicit DBitRange(uint64_t& b) : b_{ b } {}
bool empty() const { return b_ == 0; }
void popFront() { b_ &= b_ - 1; }
int front() const { return bitcount(b_); }
private:
uint64_t& b_;
};
void C_style(uint64_t primes) {
for (; primes != 0; primes &= primes - 1)
std::cout << bitcount(primes) << ", ";
std::cout << "\n";
}
void D_style(uint64_t primes) {
for (auto bitrange = DBitRange{ primes }; !bitrange.empty(); bitrange.popFront())
std::cout << bitrange.front() << ", ";
std::cout << "\n";
}
void CPP_style(uint64_t primes) {
for (auto b : DBitRange{ primes })
std::cout << b << ", ";
std::cout << "\n";
}
#if 1
int main()
{
int vals[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61 };
uint64_t primes = 0, primes2;
for (auto v : vals)
primes ^= 1ull << v;
primes2 = primes;
// C-style iteration over bitmap
for (auto bitmap = primes; bitmap != 0; bitmap &= bitmap - 1)
std::cout << bitcount(bitmap) << ", ";
std::cout << "\n";
// D-style iteration over bitmap
// translates 1-on-1 to C code, no proxy iterators and references
for (auto bitrange = DBitRange{ primes }; !bitrange.empty(); bitrange.popFront())
std::cout << bitrange.front() << ", ";
std::cout << "\n";
// CHALLENGE: define C++ range-based for iteration over bitmap
// that translates 1-on-1 into the equivalent C/D code
for (auto b : DBitRange{ primes2 })
std::cout << b << ", ";
std::cout << "\n";
}
#endif
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.