Idiom for iterating "between each consecutive pair of elements" [duplicate]

Question

Everyone encounters this issue at some point:

for(const auto& item : items) {
    cout << item << separator;
}

... and you get an extra separator you don't want at the end. Sometime it's not printing, but, say, performing some other action, but such that consecutive actions of the same type require some separator action - but the last doesn't.

Now, if you work with old-school for loops and an array, you would do

for(int i = 0; i < num_items; i++)
    cout << items[i];
    if (i < num_items - 1) { cout << separator; }
}

(or you could special-case the last item out of the loop.) If you have anything that admits non-destructive iterators, even if you don't know its size, you can do:

for(auto it = items.cbegin(); it != items.cend(); it++) {
    cout << *it;
    if (std::next(it) != items.cend()) { cout << separator; }
}

I dislike the aesthetics of the last two, and like ranged for loops. Can I obtain the same effect as with the last two but using more spiffy C++11ish constructs?

---

To expand the question further (beyond, say, this one), I'll say I would also like not to expressly have special-case the first or the last element. That's an "implementation detail" which I don't want to be bothered with. So, in imaginary-future-C++, maybe something like:

for(const auto& item : items) {
    cout << item;
} and_between {
    cout << separator;
}

Hannelorehanner

If you wanted to take a page from the functional programming book, you can always use the accumulate method, although this tends to be overkill a lot of the time – Herculie

C++ does not have algorithmic join. This is a huge shame. – Cosper

@KevinW., fold is not going to help you - it will apply operation for every element, including the first and the last. – Cosper

or https://mcmap.net/q/103925/-last-element-in-foreach – Nephridium

@Cosper if you notice, the c++ implementation of accumulate takes in 3 arguments in addition to the joining method, so you just join from the second element to the last element and have the first element as the base element. It would work just fine this way. In fact, separating something with a delimiter is literally one of the examples in the link. – Herculie

@KevinW., nope - because it won't work with empty containers or containers of one element. – Cosper

@SergeyA: I agree you can't call std::accumulate when your container is empty, but one element should be just fine (the single element gets passed as init, and begin == end initially, resulting in no folds) – Ring

@BenVoigt, but the operation won't be performed on this element! – Cosper

@SergeyA: Naturally not, because if there is only one element, it is the last! – Ring

Answer 1

My way (without additional branch) is:

const auto separator = "WhatYouWantHere";
const auto* sep = "";
for(const auto& item : items) {
    std::cout << sep << item;
    sep = separator;
}

Baran

This is of course the more obvious, simpler and cleaner way – Aceous

Ridiculously concise and elegant. The type of code I hope to write one day. – Coenocyte

Yes, it's simple and clever. I can well imagine to use this method the next time I have this kind of task. But then, it comes at the cost of introducing an additional (mutable) variable and assigning a value to it at every iteration. – Octavia

If somebody was using this in a context where separator needed to be an std::string instead of a char const*, directly transplanting this pattern would incur expensive copy each iteration. That could be avoided as follows: also have an empty constant std::string, make sep a pointer to that first, output *sep, and finally make sep a pointer to separator before the next iteration. – Biographical

Answer 2

Excluding an end element from iteration is the sort of thing that Ranges proposal is designed to make easy. (Note that there are better ways to solve the specific task of string joining, breaking an element off from iteration just creates more special cases to worry about, such as when the collection was already empty.)

While we wait for a standardized Ranges paradigm, we can do it with the existing ranged-for with a little helper class.

template<typename T> struct trim_last
{
    T& inner;

    friend auto begin( const trim_last& outer )
    { using std::begin;
      return begin(outer.inner); }

    friend auto end( const trim_last& outer )
    { using std::end;
      auto e = end(outer.inner); if(e != begin(outer)) --e; return e; }
};

template<typename T> trim_last<T> skip_last( T& inner ) { return { inner }; }

and now you can write

for(const auto& item : skip_last(items)) {
    cout << item << separator;
}

Demo: http://rextester.com/MFH77611

For skip_last that works with ranged-for, a Bidirectional iterator is needed, for similar skip_first it is sufficient to have a Forward iterator.

Ring

What does e - (b != e) mean? Does it imply conversion of bool true to 1? This is not guaranteed. – Cosper

@SergeyA: Means that an input list of zero elements creates an output of zero elements, instead of breaking. – Ring

@SergeyA: Of course that's guaranteed, has been ever since the first time C was standardized. See [conv.prom] for the current C++ wording: " A prvalue of type bool can be converted to a prvalue of type int, with false becoming zero and true becoming one." – Ring

OP wants a join in fact, not skipping last element. (just the last separator should be kept). – Baran

I somehow missed it. It really is guaranteed! – Cosper

@Jarod42: You could indeed write a join function using this skip_last (or corresponding skip_first), but this is far more powerful – Ring

I also agree with @Jarod42. While you can add code to take care of the last element, that would be another if statement to care for empty containers - and the whole thing looses beauty. – Cosper

This is the most elegant and flexible approach, I think. You stick a bunch of these helpers into a library and no one cares what's written inside them, so long as it performs reasonably well. The goal here seems to be ease of use and elegance. I personally have never looked at the code for any library's std::transform(), but I've used it plenty and it was more elegant and expressive than pushing to a container in a loop. – Nitrobenzene

@YamMarcovic, if you are to incapsulate this into library join, you can as well right this function with an if inside it - and no need for skip_last. – Cosper

@SergeyA: Sure, it is not the only way to solve concatenation without trailing separator. OP has an X-Y problem. But the question that OP asked, "for each except the last", is interesting and useful, and this answer provides that. – Ring

@BenVoigt, it is definitely not XY problem! The need to write values with comas in between them is omnipresent. I myself just recently had to do this :) And the lack of (algorithmic) join is frustrating. And unfortunately, your code does not solve the actual problem, instead, it solves another problem, and while your solution can be used for the actual problem, it is not complete and does not have benefits in this scenario. – Cosper

@SergeyA: It is XY problem. X is "write values with commas between them", Y is "stop the loop one item early". Your comments that you can do X without Y are correct... but Y is still useful for other problems and the technique is good to share. My code solves the problem asked about, namely "for each (ranged for loop) except the last". – Ring

Who said anything about 'stopping the loop one item early' but you? – Cosper

@SergeyA: Did you ever read the title of the question? – Ring

The first name of the title has nothing to do with the actual question, so I kinda mentally skipped it. But yes, taken literally, your answer has merits - but I still believe it does not go with the spirit of the question. – Cosper

@SergeyA: I added a parenthetical challenging the XY problem in the question, does that help? – Ring

Yes, I think it is clearer now. – Cosper

@Deduplicator: Putting the definitions out-of-class would have required a lot more template <typename T> cruft. Thanks for removing the iterator subtraction that needs random-access. – Ring

@BenVoigt: I think you'd better make your trim last have cbegin() and cend() rather than begin() and end(). or maybe both. After all, trim_last would likely be used more for reading than for updating. – Hannelorehanner

@einpoklum: You could make a good argument that ranged-for in general is used more for reading than updating... yet the Standard committee chose to allow write access to the elements (not to the container) and leave it up to the programmer to choose read-only access (by-value iteration variable, or const reference) or write (non-const reference). My solution preserves that feature. – Ring

See #25653005 for a way to simulate ranges – Suzysuzzy

Answer 3

Do you know Duff's device?

int main() {
  int const items[] = {21, 42, 63};
  int const * item = items;
  int const * const end = items + sizeof(items) / sizeof(items[0]);
  // the device:
  switch (1) {
    case 0: do { cout << ", ";
    default: cout << *item; ++item; } while (item != end);
  }

  cout << endl << "I'm so sorry" << endl;
  return 0;
}

(Live)

Hopefully I didn't ruin everyone's day. If you don't want to either then never use this.

(mumble) I'm so sorry ...

---

The device handling empty containers (ranges):

template<typename Iterator, typename Fn1, typename Fn2>
void for_the_device(Iterator from, Iterator to, Fn1 always, Fn2 butFirst) {
  switch ((from == to) ? 1 : 2) {
    case 0:
      do {
        butFirst(*from);
    case 2:
        always(*from); ++from;
      } while (from != to);
    default: // reached directly when from == to
      break;
  }
}

Live test:

int main() {
  int const items[] = {21, 42, 63};
  int const * const end = items + sizeof(items) / sizeof(items[0]);
  for_the_device(items, end,
    [](auto const & i) { cout << i;},
    [](auto const & i) { cout << ", ";});
  cout << endl << "I'm (still) so sorry" << endl;
  // Now on an empty range
  for_the_device(end, end,
    [](auto const & i) { cout << i;},
    [](auto const & i) { cout << ", ";});
  cout << "Incredibly sorry." << endl;
  return 0;
}

Alejandrinaalejandro

how is this foreach? – Kelle

It's not foreach but doing something for each element. A loop's a loop, most of the time. – Alejandrinaalejandro

I could've lived a long and blissful life without ever knowing of this. Thank you. – Crossarm

The complexity of the emotional response that this answer provokes... – Nitrobenzene

I did know about Duff's device, but many thanks for showing that it applies here. It is an elegant tool for a more civilized age... ok, maybe a less-civilized age. – Hannelorehanner

The funniest thing is that the boolean flag approach effectively is optimized into the device by gcc. – Cosper

The problem with this particular device is incorrect handling of empty containers. One extra branch is needed. – Cosper

@Cosper cool, I didn't know that. What I'd be guessing is that the device is rather hard for the optimiser to do loop unrolling. Do you know whether this is true? – Alejandrinaalejandro

@Cosper To handle the empty case using container.size() with appropriate targets in the switch should work. – Alejandrinaalejandro

WOW!! This is a time that some code lines makes me have a heart attack. – Ruffner

@DanielJour, I do not immediately see how you can handle empty size in switch. Care to edit your answer to include the code? – Cosper

@DanielJour, in my scenarios, neither compiler attempted a loop unrolling even with straightforward loop. So I think even less so with the device. It is also interesting that of gcc, clang and ICC only gcc recognized the nature of the flag and removed it. 2 other compilers obediently used a register and a branch. Which is just an extra score for gcc. – Cosper

@Sergey: Replace the switch guts with while (1) { cout << ", "; case 1: if (item == end) break; cout << *item; } – Ring

@BenVoigt, this is a branch I was talking about. I though, Daniel meant branchless fix. – Cosper

@Cosper I added an example of how I'd modify the device to handle empty ranges (i.e. empty containers). – Alejandrinaalejandro

Daniel, this is the branch ) – Cosper

@Cosper Ah, you meant with only a single branch all over, I thought you meant without additional branch in the loop. I'd guess without using (possibly costly) assignments this won't be possible. (I tried some manual goto foo, but got sick of it :D ) – Alejandrinaalejandro

What not a simple goto? – Situla

Answer 4

I don't know of any special idioms for this. However, I prefer to special case the first and then perform the operation on the remaining items.

#include <iostream>
#include <vector>

int main()
{
    std::vector<int> values = { 1, 2, 3, 4, 5 };

    std::cout << "\"";
    if (!values.empty())
    {
        std::cout << values[0];

        for (size_t i = 1; i < values.size(); ++i)
        {
            std::cout << ", " << values[i];
        }
    }
    std::cout << "\"\n";

    return 0;
}

Output: "1, 2, 3, 4, 5"

Dystopia

Exactly the same reaction here; also fits well in any language that can head and tail a list. – Accumulator

Important to note that that loop can be written as for( const auto& item : skip_first(values) )... in order to meet the requirements of the question. – Ring

@Hannelorehanner Yes, thank you. I fixed the typo. – Dystopia

@BenVoigt: Is skip_first a (hypothetical) function that we'd have to define, or is there a C++ function that does what would be needed? – Calvincalvina

@R_Kapp: I was busy writing it, see my answer. – Ring

Answer 5

Typically I do it the opposite way:

bool first=true;
for(const auto& item : items) {
    if(!first) cout<<separator;
    first = false;
    cout << item;
}

Thadeus

You need an if/else to make that work – Ring

@BenVoigt, why? It works perfectly well without else in this case. However, it has an unpleasant branch on every iteration - in extreme cases can be a performance hit (can't imagine any real ones, though). – Cosper

@SergeyA: well predicted branches are essentially free (and this one is perfectly predicted after a few iterations), I wouldn't worry about it. – Thadeus

first will never go false – Wingless

MatteoItalia, neither would I. I was making a general statement. It also has unpleasant assignment. – Cosper

@Cristophe: ops, forgot the assignment in the braces, sorry, fixed. – Thadeus

@SergeyA: disputable; at low level it's essentially free too, and compared to all other solutions I find this both easier to write and less visually cluttered. But that's of course a stylistical matter. – Thadeus

I disagree with being 'free'. If compiler optimizes it to register storage, it will be free. But if not, on cache coherent systems it would be rather expensive memory write. – Cosper

@Cosper It doesn't even need to be in a register. Compiler can actually make the first one a special case and take it out of the loop. – Nitrobenzene

@YamMarkovic, it might, but not necessarily will. – Cosper

@Cosper I would be surprised if the compiler didn't optimize away that flag. – Elston

@Deduplicator, I tested it on Clang and gcc. gcc completely removes the flag altogether - just orders jmps to make sure it is called only once, but clang goes by the book, checking it on every iteration (puts in register in my test, though). – Cosper

Answer 6

I like plain control structures.

if (first == last) return;

while (true) {
  std::cout << *first;
  ++first;
  if (first == last) break;
  std::cout << separator;
}

Depending on your taste, you can put the increment and test in a single line:

...
while (true) {
  std::cout << *first;
  if (++first == last) break;
  std::cout << separator;
}

Eligibility

A step further, and this would have been written in assembly. – Kline

Answer 7

int a[3] = {1,2,3};
int size = 3;
int i = 0;

do {
    std::cout << a[i];
} while (++i < size && std::cout << ", ");

Output:

1, 2, 3 

The goal is to use the way && is evaluated. If the first condition is true, it evaluates the second. If it is not true, then the second condition is skipped.

Apropos

Answer 8

I don't thing you can get around having a special case somewhere... For example, Boost's String Algorithms Library has a join algorithm. If you look at its implementation, you'll see a special case for the first item (no proceeding delimitier) and a then delimiter is added before each subsequent element.

Affer

Have a look at ostream joiners. – Hannelorehanner

@Hannelorehanner thanks, I didn't know that was coming. Reinforces that there's no algorithm(/iterator) will get around having a special case: for ostream_joiner it's embodied in the boolean that tracks whether you're about to write the first element. Basic thesis is that when you're joining N elements this way (where N > 1), you're not doing the same operation N times--you've got one element that must be handled differently. – Affer

Ok, yes, but it's not the coding using those joiner that has to track anything. See also @MaartenHilferink 's answer. The principle of "the best line of code is the one you don't have to write yourself", as others have quipped here. – Hannelorehanner

Answer 9

You could define a function for_each_and_join that takes two functors as argument. The first functor does work with each element, the second works with each pair of adjacent elements:

#include <iostream>
#include <vector>

template <typename Iter, typename FEach, typename FJoin>
void for_each_and_join(Iter iter, Iter end, FEach&& feach, FJoin&& fjoin)
{
    if (iter == end)
        return;

    while (true) {
        feach(*iter);
        Iter curr = iter;
        if (++iter == end)
            return;
        fjoin(*curr, *iter);
    }
}

int main() {
    std::vector<int> values = { 1, 2, 3, 4, 5 };
    for_each_and_join(values.begin(), values.end()
    ,  [](auto v) { std::cout << v; }
    ,  [](auto, auto) { std::cout << ","; }
    );
}

Live example: http://ideone.com/fR5S9H

Humblebee

You really can do without the first function. The concept of a monoid lets you kick things off with a special empty value for the "left" and the first real element for "right". – Linctus

Answer 10

I don't know about "idiomatic", but C++11 provides std::prev and std::next functions for bidirectional iterators.

int main() {
    vector<int> items = {0, 1, 2, 3, 4};
    string separator(",");

    // Guard to prevent possible segfault on prev(items.cend())
    if(items.size() > 0) {
        for(auto it = items.cbegin(); it != prev(items.cend()); it++) {
            cout << (*it) << separator;
        }
        cout << (*prev(items.cend()));
    }
}

Coenocyte

Way way too many lines of code my friend :-) ... and I don't want to have to check the size of items either. – Hannelorehanner

@einpoklum, I agree with your sentiment. "The best line of code is one you don't have to write." I was just trying to give you something using new C++11 fancy tools. – Coenocyte

Answer 11

Heres a little trick I like to use:

For bi-directionally iterable objects: for ( auto it = items.begin(); it != items.end(); it++ ) { std::cout << *it << (it == items.end()-1 ? "" : sep); };

Using the ternary ? operator I compare the current position of the iterator against the item.end()-1 call. Since the iterator returned by item.end() refers to the position after the last element, we decrement it once to get our actual last element.

If this item isn't the last element in the iterable, we return our separator (defined elsewhere), or if it is the last element, we return an empty string.

For single direction iterables (tested with std::forward_list): for ( auto it = items.begin(); it != items.end(); it++ ) { std::cout << *it << (std::distance( it, items.end() ) == 1 ? "" : sep); };

Here, we're replacing the previous ternary condition with a call to std::distance using the current iterator location, and the end of the iterable.

Note, this version works with both bidirectional iterables as well as single direction iterables.

EDIT: I realize you dislike the .begin() and .end() type iteration, but if you're looking to keep the LOC count down, you're probably going to have to eschew range based iteration in this case.

The "Trick" is simply wrapping the comparison logic within a single ternary expression, if your comparison logic is relatively simple.

Butylene

I don't really see where the trick is. Also, you assume items is bidirectionally iterable. – Hannelorehanner

Edited to account for single direction iterables. Your question didn't specify them as a constraint, but it's worth accounting for. The second example will work with both. – Butylene

In the single-direction iterables example, won't it run at O(n^2) complexity? I'd imagine that std::distance has not way to know the answer other than iterating all the way to end, and you're doing it in every loop iteration. – Wellworn

@Wellworn True, it's not the most efficient. I suppose it could be improved by storing the length of the iterable in an int before the loop and converting the iterator position to an int type somehow then comparing the values. That would bring it closer to O(n), right? (Sorry if I'm off, I'm not great with big O notation, it's something I'm working on) – Butylene

Answer 12

I like the boost::join function. So for more general behavior, you want a function that is called for each pair of items and can have a persistent state. You'd use it as a funcgion call with a lambda:

foreachpair (range, [](auto left, auto right){ whatever });

Now you can get back to a regular range-based for loop by using range filters!

for (auto pair : collection|aspairs) {
    Do-something_with (pair.first);
}

In this idea, pair is set to a pair of adjecent elements of the original collection. If you have "abcde" then on the first iteration you are given first='a' and second='b'; next time through first='b' and second='c'; etc.

You can use a similar filter approach to prepare a tuple that tags each iteration item with an enumeration for /first/middle/last/ iteration and then do a switch inside the loop.

To simply leave off the last element, use a range filter for all-but-last. I don't know if that's already in Boost.Range or what might be supplied with Rangev3 in progress, but that's the general approach to making the regular loop do tricks and making it "neat".

Theurich