C++11 auto iterator type with std::begin(), std::end() issue

Question

I have some private class member, representing random access array of std::deque containing some data:

std::vector<std::deque<SomeDataClass> > someMember;

I would like to provide a public class method which returns iterable data structure, containing all data elements from my array of deques:

std::deque<SomeDataClass> someMethod();

I would like this method go through all the deques in vector and copy every element on it's way to local std::deque, eventually returning this local std::deque by value. I'm trying to implement this method using C++11 auto and std::begin(), std::end():

std::deque<SomeDataClass> MyClassName::someMethod(){
    std::deque<DirectedEdge> allDataItems;
    std::deque<DirectedEdge>::iterator deqIter = allDataItems.begin();
    for(auto it = std::begin(someMember); it != std::end(someMember); ++it){
        std::copy(std::begin(*it), std::end(*it), deqIter);
    }

    return allDataItems;
}

I receive data access violation unhandled exception error on runtime in deque header. What is a mistake?

Solution 1

std::copy() requires the destination range to be large enough to hold the copy, but allDataItems is empty. You'd have to reserve space in allDataItems in advance (but that's not possible with std::deque). You should use a std::back_inserter (defined in <iterator>) instead:

std::deque<SomeDataClass> MyClassName::someMethod(){
    std::deque<DirectedEdge> allDataItems;
    for(auto it = std::begin(someMember); it < std::end(someMember); ++it){
        std::copy(std::begin(*it), std::end(*it), std::back_inserter(allDataItems));
    }

    return allDataItems;
}

Solution 2

Here is an idomatic C+11 way to do it:

std::deque<SomeDataClass> MyClassName::someMethod() {
  std::deque<DirectedEdge> allDataItems;

  for( auto const& dq : someMember ) {
    allDataItems.insert( allDataItems.end(), std::begin(dq), std::end(dq) );
  }
  return allDataItems;
}

another way would be to write a concatinate function:

struct concatenate {
  template<typename Dest, typename Src>
  Dest&& operator()( Dest&& d, Src const& s ) const {
    using std::begin; using std::end;
    typename std::decay<Dest>::type retval = std::forward<Dest>(d);
    retval.insert( end(retval), begin(s), end(s) );
    return std::move(retval);
  }
};
std::deque<SomeDataClass> MyClassName::someMethod() {
  using std::begin; using std::end; // enable ADL
  return std::accumulate(
    begin(someMember), end(someMember),
    std::deque<DirectedEdge>(), concatenate()
  );
}

which is pretty cute. If you don't like std::accumulate,

std::deque<SomeDataClass> MyClassName::someMethod() {
  std::deque<DirectedEdge> allDataItems;

  for( auto const& dq : someMember ) {
    allDataItems = concatenate( std::move(allDataItems), dq );
  }
  return allDataItems;
}

both of which are roughly equivalently efficient.

Comments

[chris]

Consider doing allDataItems.insert(std::end(allDataItems), ...); instead. I'd say it's usually better to use members when possible.

[Angew is no longer proud of SO]

@chris You can make that a separate answer, so the OP can decide which they like better.

[chris]

Just add it to yours and then there's an even better answer :)

[Yakk - Adam Nevraumont]

!= works instead of < and means that if someMember wasn't a random-access container, the code would still work. And if you don't need the iterator, for( auto const& x : someMember ) is clearer and shorter.

[Yakk - Adam Nevraumont]

@benvoigt renamed function to merriam_webster as requested.