CODEWITHSUNDEEP
c++c++11
Super-intelligent Shade
Super-intelligent Shade

Reputation: 6449

Using ranges with std::set

I'd like to initialize std::set with several ranges of numbers. I would like to do it efficiently (minimal copying), without using boost and with good code readability for the end-user (myself :) at the moment).

Following is what I've come up with so far, but I can see a number of inefficiencies and wanted to get pointers on whether it is possible and how to fix them. Specific questions are below the code.

#include <iostream>
#include <set>

typedef std::set<int> codes;

template<typename T>
inline codes operator|(codes&& x, T&& y)
{
    codes c(std::move(x));
    c.insert(y.begin(), y.end());
    return c;
}

template<typename T>
inline codes operator|(const codes& x, T&& y)
{
    codes c(std::forward<T>(y));
    c.insert(x.begin(), x.end());
    return c;
}

inline codes range(int min, int max)
{
    codes c;
    for(int ri = min; ri < max; ++ri) c.insert(ri);
    return c;
}

void print_set(const std::string& name, const codes& set)
{
    std::cout << name << " = ";
    for(int ri: set) std::cout << ri << ' ';
    std::cout << std::endl;
}

int main()
{
    codes r1 = { 1, 2, 3 };
    codes r2 = range(5, 10);
    codes r3 = r1 | r2;
    codes r4 = r2 | range(15, 20);
    codes r5 = range(1, 10) | r1;
    codes r6 = range(1, 5) | range(10, 15);

    print_set("r1", r1);
    print_set("r2", r2);
    print_set("r3", r3);
    print_set("r4", r4);
    print_set("r5", r5);
    print_set("r6", r6);

    return 0;
}

  1. I wrote the operator| as templates to deal with various combinations of r- and l-value references. However, the operator|(&& x, && y) version still has to copy the elements from y. Is it possible to avoid it?

  2. The range function executes at run-time. Is it possible to write a constexpr version that runs at compile-time?

  3. Anybody sees any other things that can be optimized?

  4. Should I use an entirely different approach?

The key things are:

a) The code should be easily readable. In other words it should somewhat resemble the mathematical expression, eg: foo = [a, b) | [c, d)

b) The program will run on an embedded system, so code footprint and efficiency is important (hence, no boost).

Upvotes: 0

Views: 3000

Answers (1)

Drew Dormann
Drew Dormann

Reputation: 63775

All of this:

template<typename T>
inline codes operator|(codes&& x, T&& y)
{
    codes c(std::move(x));
    c.insert(y.begin(), y.end());
    return c;
}

template<typename T>
inline codes operator|(const codes& x, T&& y)
{
    codes c(std::forward<T>(y));
    c.insert(x.begin(), x.end());
    return c;
}

Could be written as:

template<typename T>
inline codes operator|(codes x, T&& y)
{
    using std::begin;
    using std::end;
    x.insert( begin(y), end(y) );
    return x;
}

Passing codes x by value will implement the correct and already-well-tested std::set constructors for both lvalues and rvalues.

Upvotes: 4

Related Questions