C++ API for returning sequences in a generic way

Question

If I am writing a library and I have a function that needs to return a sequence of values, I could do something like:

std::vector<int> get_sequence();

However, this requires the library user to use the std::vector<> container rather than allowing them to use whatever container they want to use. In addition, it can add an extra copy of the returned array (depending on whether the compiler could optimize this or not) that might have a negative impact on performance.

You could theoretically enable the use of arbitrary containers (and avoid the unnecessary extra copying) by making a templated function that takes a start and an end iter:

template<class T_iter> void get_sequence(T_iter begin, T_iter end);

The function would then store the sequence values in the range given by the iterators. But the problem with this is that it requires you to know the size of the sequence so you have enough elements between begin and end to store all of the values in the sequence.

I thought about an interface such as:

template<T_insertIter> get_sequence(T_insertIter inserter);

which requires that the T_insertIter be an insert iterator (e.g. created with std::back_inserter(my_vector)), but this seems way too easy to misuse since the compiler would happily accept a non-insert iterator but would behave incorrectly at run-time.

So is there a best practice for designing generic interfaces that return sequences of arbitrary length?

Answer 1

std::list<int> is slightly nicer, IMO. Note that this would not require an extra copy of the data in the list, as it's only pointers being copied.

It depends entirely on your consumers. If you can expect them to be C++ developers, give them one of the std container classes, I say.

The only other thing that occurs to me is that you'd do this:

void get_sequence(std::tr1::function<void(int)> f);

Then the caller can use std::tr1::bind to make your get_sequence function call whatever function on whatever object (or not) that they want. You just keep calling f for each element you're creating.

Answer 2

You could do something like

template<typename container>
container get_sequence();

and require that the supplied container type conforms to some standard interface (like having a member push_back and maybe reserve, so that the user of your interface can use vector/deque/list).

Answer 3

You can statically dispatch on the type of iterator using iterator_traits

Something like this :

template<T_insertIter> get_sequence(T_insertIter inserter)
{
   return get_sequence(inserter, typename iterator_traits<Iterator>::iterator_category());
}

template<T_insertIter> get_sequence(T_insertIter inserter, input_iterator_tag);

Answer 4

Have get_sequence return a (custom) forward_iterator class that generates the sequence on-demand. (It could also be a more advanced iterator type like bidirectional_iterator if that's practical for your sequence.)

Then the user can copy the sequence into whatever container type they want. Or, they can just loop directly on your iterator and skip the container entirely.

You will need some sort of end iterator. Without knowing exactly how you're generating the sequence, it's hard to say exactly how you should implement that. One way would be for your iterator class to have a static member function that returned an end iterator, like:

static const my_itr& end() { static const my_itr e(...); return e; };

where ... represents whatever parameters you need to create the end iterator (which might use a private constructor). Then your loop would look like:

for (my_itr i = get_sequence(); i != my_itr::end(); ++i) { ... }

Here's a trivial example of a forward iterator class that generates a sequence of consecutive integers. Obviously, this could easily be turned into a bidirectional or random access iterator, but I wanted to keep the example small.

#include <iterator>

class integer_sequence_itr
  : public std::iterator<std::forward_iterator_tag, int>
{
 private:
  int i;

 public:
  explicit integer_sequence_itr(int start) : i(start) {};

  const int& operator*()  const { return i; };
  const int* operator->() const { return &i; };

  integer_sequence_itr& operator++() { ++i; return *this; };
  integer_sequence_itr  operator++(int)
    { integer_sequence_itr copy(*this); ++i; return copy; };

  inline bool operator==(const integer_sequence_itr& rhs) const
    { return i == rhs.i; };

  inline bool operator!=(const integer_sequence_itr& rhs) const
    { return i != rhs.i; };
}; // end integer_sequence_itr

//Example:  Print the integers from 1 to 10.
#include <iostream>

int main()
{
  const integer_sequence_itr stop(11);

  for (integer_sequence_itr i(1); i != stop; ++i)
    std::cout << *i << std::endl;

  return 0;
} // end main

Answer 5

One thing to pay extra attention to is if you by library mean a DLL or similar. Then there might be problems if the library consumer, say an application, is built with another compiler than the library itself.

Consider the case where you in your example return a std::vector<> by value. Memory will then be allocated in the context of the library, but deallocated in the context of the application. Two different compilers might allocate/deallocate differently and so havoc might occur.

Answer 6

Err... Just my two cents, but:

void get_sequence(std::vector<int> & p_aInt);

This would remove the potential return by copy problem. Now, if you really want to avoid imposing a container, you could try something like:

template <typename T>
void get_sequence(T & p_aInt)
{
    p_aInt.push_back(25) ; // Or whatever you need to add
}

This would compile only for vectors, lists and deque (and similar containers). Should you want a larget set of possible containers, the code would be:

template <typename T>
void get_sequence(T & p_aInt)
{
    p_aInt.insert(p_aInt.end(), 25) ; // Or whatever you need to add
}

But as said by other posts, you should accept to limit your interface to one kind of containers only.

Answer 7

If your already manage memory for your sequence, you can return a pair of iterators for the caller to use in for loop or an algorithm call.

If the returned sequence needs to manage its own memory, then things are more convoluted. You can use @paercebal's solution, or you can implement your own iterators that hold shared_ptr to the sequence they are iterating.

Answer 8

For outputting sequences, I see two options. The first is something like

template <typename OutputIter>
void generate_sequence(OutputIter out)
{
    //...
    while (...) { *out = ...; ++out; }
}

The second is something like

struct sequence_generator
{
    bool has_next() { ... }
    your_type next() { mutate_state(); return next_value; }

private:
    // some state
};

that you would want to turn into a standard C++ iterator (using boost::iterator_facade for convenience) to use it in standard algorithms (copy, transform, ...).

Have also a look at boost::transform_iterator, combined with some iterator returning integers in sequence.

Answer 9

You could pass a functor to your function which accepts a single value. The functor would then be responsible for storing the value in whatever container you are using at the time.

struct vector_adder {
  vector_adder(std::vector<int>& v) : v(v) {}
  void operator()(int n) { v.push_back(n); }
  std::vector<int>& v;
};

void gen_sequence(boost::function< void(int) > f) {
  ...
  f(n);
  ...
}

main() {
  std::vector<int> vi;
  gen_sequence(vector_adder(vi));
}

Note: I'm using boost.function here to define the functor parameter. You don't need boost to be able to do this. It just makes it a lot simpler.

You could also use a function pointer instead of a functor, but I don't recommend it. It's error prone and there's no easy way to bind data to it.

Also, if your compiler supports C++0x lambda functions, you can simplify the code by eliminating the explicit functor definition:

main() {
  std::vector<int> ui;
  gen_sequence([&](int n)->void{ui.push_back(n);});
}

(I'm still using VS2008 so I'm not sure if I got the lambda syntax right)