1

I'm trying to find a way to improve my answer here. Let's simplify the question to say: I want to partition the input container, lets call it foo, into a vector of vectors of size STEP, the last of these vectors shall have a smaller size if there were less than STEP elements remaining in the input container, let's call this partitioned container bar.

I don't want to iterate over my input or output range multiple times. The element of the problem I'm trying to solve are simply:

  1. Append bar with a constructed vector of size min(STEP, distance(it, foo.end())
  2. Have the it point to advance(it, size(bar.back())) after constructing the container
  3. Do this vector construction in-place

The translation of my answer to the confines of this problem is:

auto it = cbegin(foo);

for (auto i = size(foo); i > STEP; i -= STEP) {
    bar.push_back(decltype(bar)::value_type(STEP));
    for (auto internalIt = bar.back().begin(); internalIt != bar.back().end(); ++internalIt, ++it) {
        *internalIt = *it;
    }
}
bar.push_back(decltype(bar)::value_type(it, cend(foo)));

The problem is this line: bar.push_back(decltype(bar)::value_type(STEP)) I'm allocating the vector and 0-initializing it's components. Is there a better way to do this, under which I still would only iterate over the input and output ranges once?

Community
  • 1
  • 1
Jonathan Mee
  • 37,899
  • 23
  • 129
  • 288

1 Answers1

1
bar.push_back(decltype(bar)::value_type{}); // or bar.resize(bar.size() + 1); if you prefer
bar.back().reserve(STEP);
while (bar.back().size() < STEP) {
    bar.back().push_back(*it);
    ++it;
}

It's a stroke of bad luck that std::copy_n returns the advanced output iterator, when what you need to keep is the advanced input iterator, otherwise you could use that in place of the loop (using std::back_inserter to get the destination iterator).

Feel free to use a counter variable if you're concerned about the performance of bar.back().size()!

Steve Jessop
  • 273,490
  • 39
  • 460
  • 699
  • LOL, I actually had `copy_n` in my code and couldn't figure out why my input iterator wasn't getting advanced till I looked at it and realized it took the iterator by value. Anyway, you're suggesting that, an empty construction, allocation of space, and a `back_inserter` are better than construction with space allocated and direct assignment? – Jonathan Mee May 19 '16 at 17:07
  • OK, so I've benchmarked it and can confirm that construct, allocate, and insert is always slower than construct with allocation and assign: http://coliru.stacked-crooked.com/a/206b8278ff67817f By the way, I don't know what's up with Coliru, but I don't trust it's results because they are always in 10,000 increments. But if you copy this and run locally you can confirm my assessment. – Jonathan Mee May 20 '16 at 12:08
  • @JonathanMee: it's "better" only in the sense you asked for, that it only runs over each sub-vector of the results vector `bar` once, whereas your code runs over it twice (once to zero-initialize and once to assign). I didn't even consider whether it has better or worse runtime on any particular `vector` implementation, my remark about the performance of `bar.back().size()` was just an afterthought. With a sufficiently atrocious memory cache, such that the cost of a cache miss is truly exorbitant, and a big enough `STEP` to blow cache, we could arrange for this to run faster than your code ;-) – Steve Jessop May 20 '16 at 12:20
  • You're suggesting that if the vector that was allocated was large enough to cause a cache miss, my code would be more expensive because it must iterate through, 0 initializing the values, then it must iterate through assigning the values? I don't think that's the case. The compiler is smart enough to know that I'm doing a `calloc` and request 0 initialized memory: http://stackoverflow.com/a/2688522/2642059 – Jonathan Mee May 20 '16 at 12:40
  • @JonathanMee: depending on `value_type` it might not be a calloc (because it might not actually be zero initialization although I've called it that). But fair enough. – Steve Jessop May 20 '16 at 12:44
  • And I guess now that I'm thinking about it, `STEP` is constant. I'd really expect the compiler to roll this into initialization, perhaps it's just not smart enough to? – Jonathan Mee May 20 '16 at 12:50