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?

Alerion

Answer 1

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

Darrel

This is an interesting solution, however, won't work for certain cases. It will work nicely if you have the whole sequence cached in the class or if it's cheap to generate a single item in the sequence. Otherwise it could be quite inefficient. – Alerion

A forward iterator alone doesn't give the user a way to check for the end of the sequence. Returning a range would work though (i.e. an iterator pair giving begin and end). – Oxysalt

This is the best solution: provide begin() and end() functions to return your own iterator. If you don't have the whole sequence cached and it's not cheap to generate a single item, then you'll have to add extra information into your iterator type to ease single item generation. Iterator can be much more than pointer, if it helps. – Interurban

Answer 2

Why do you need your interface to be container-independent? Scott Meyers in his "Effective STL" gives a good reasoning for not trying to make your code container-independent, no matter how strong the temptation is. Basically, containers are intended for completely different usage: you probably don't want to store your output in map or set (they're not interval containers), so you're left with vector, list and deque, and why do you wish to have vector where you need list and vice versa? They're completely different, and you'll have better results using all the features of one of them than trying to make both work. Well, just consider reading "Effective STL": it's worth your time.

If you know something about your container, though, you may consider doing something like

template void get_sequence(T_Container & container)
{
  //...
  container.assign(iter1, iter2);
  //...
}

or maybe

template void get_sequence(T_Container & container)
{
  //...
  container.resize(size);
  //use push_back or whatever
  //...
}

or even control what you do with a strategy, like

class AssignStrategy // for stl
{
public:
  template
  void fill(T_Container & container, T_Container::iterator it1, T_Container::iterator it2){
    container.assign(it1, it2);
  }
};

class ReserveStrategy // for vectors and stuff
{
public:
  template
  void fill(T_Container & container, T_Container::iterator it1, T_Container::iterator it2){
    container.reserve(it2 - it1);
    while(it1 != it2)
      container.push_back(*it1++);
  }
};


template 
void get_sequence(T_Container & container)
{
  //...
  T_FillStrategy::fill(container, iter1, iter2);
  //...
}

Shaun

Sure, I agree with the basic point, but the standard library is not the only supplier of container classes. For example, somebody using the library in conjunction with Qt might wish to use QVector instead of std::vector, etc. my goal wasn't really to support completely different types of containers. – Alerion

Sure, I agree with your basic point, but I really wish the Qt folks would start using std. /me grins. – Unstoppable

Answer 3

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.

Gastrin

Answer 4

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.

Embrue

Slightly Out of Topic: In C++, you have good chances to have the guarantee the libraries you are writing will be compiled with the same compiler used for the client application, or would not be exposing templated or inlined code in your interface (In some past job, we produced three binaries for each library we wrote, one per compiler we needed to support). – Gastrin

Answer 5

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.

Quar

Answer 6

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 usestd::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.

Unstoppable

vector also only contains a pointer to the data, and still the whole content has to be copied so as to prevent aliasing. The same is true for lists. Furthermore, why is it “nicer, IMO”? This isn’t subjective at all! Lists are well-suited when needing fast insertion and deletion in the middle, and basically for nothing else. – Pearlypearman

Answer 7

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).

Beating

Answer 8

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);

Dermatogen

Answer 9

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.

Lechery

The second is nothing else than a C++ iterator with another syntax. Why not use the established syntax? – Pearlypearman

because it is terribly difficult to get right. But I mention boost::iterator_facade. – Lechery

Answer 10

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)

Vida