By einpoklum


2016-02-12 21:51:02 8 Comments

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

12 comments

@Ben Voigt 2016-02-12 22:03:47

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.

@SergeyA 2016-02-12 22:09:02

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

@Ben Voigt 2016-02-12 22:09:53

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

@Ben Voigt 2016-02-12 22:10:24

@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."

@Jarod42 2016-02-12 22:12:09

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

@SergeyA 2016-02-12 22:12:18

I somehow missed it. It really is guaranteed!

@Ben Voigt 2016-02-12 22:13:30

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

@SergeyA 2016-02-12 22:16:01

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.

@Yam Marcovic 2016-02-12 22:19:13

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.

@SergeyA 2016-02-12 22:23:45

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

@Ben Voigt 2016-02-12 22:26:18

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

@SergeyA 2016-02-12 22:29:09

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

@Ben Voigt 2016-02-12 22:30:27

@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".

@SergeyA 2016-02-12 22:33:37

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

@Ben Voigt 2016-02-12 22:34:05

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

@SergeyA 2016-02-12 22:36:05

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.

@Ben Voigt 2016-02-12 22:40:44

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

@SergeyA 2016-02-12 23:12:55

Yes, I think it is clearer now.

@Ben Voigt 2016-02-12 23:25:24

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

@einpoklum 2016-02-13 10:33:33

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

@Ben Voigt 2016-02-13 15:21:53

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

@rwst 2017-09-28 07:24:09

See stackoverflow.com/questions/25652505/… for a way to simulate ranges

@Jarod42 2016-02-12 22:07:47

My way (without additional branch) is:

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

@edc65 2016-02-12 23:12:31

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

@MtRoad 2016-02-19 02:01:59

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

@Frank Puffer 2016-02-20 09:47:50

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.

@underscore_d 2017-07-19 08:52:16

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.

@WeRelic 2016-02-13 19:30:15

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.

@einpoklum 2016-02-13 20:35:41

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

@WeRelic 2016-02-13 21:49:44

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.

@Jonathan 2016-02-14 07:52:54

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.

@WeRelic 2016-02-15 03:37:37

@Jonathan 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)

@JDługosz 2016-02-13 19:58:14

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

@sudo rm -rf slash 2016-02-13 15:14:56

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.

@Daniel Jour 2016-02-13 00:31:55

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

@phuclv 2016-02-13 00:53:47

how is this foreach?

@Daniel Jour 2016-02-13 01:04:51

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

@Bilal Akil 2016-02-13 01:56:08

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

@Yam Marcovic 2016-02-13 09:11:44

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

@einpoklum 2016-02-13 10:26:56

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.

@SergeyA 2016-02-13 13:08:39

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

@SergeyA 2016-02-13 13:21:33

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

@Daniel Jour 2016-02-13 13:24:07

@SergeyA 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?

@Daniel Jour 2016-02-13 13:27:04

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

@dev-masih 2016-02-13 13:42:25

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

@SergeyA 2016-02-13 13:52:34

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

@SergeyA 2016-02-13 13:58:39

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

@Ben Voigt 2016-02-13 15:26:03

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

@SergeyA 2016-02-13 16:29:13

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

@Daniel Jour 2016-02-13 17:39:21

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

@SergeyA 2016-02-13 18:08:17

Daniel, this is the branch )

@Daniel Jour 2016-02-13 18:22:26

@SergeyA 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 )

@Carsten S 2016-02-13 21:18:46

What not a simple goto?

@Maarten Hilferink 2016-02-13 08:44:33

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

@JDługosz 2016-02-13 20:02:07

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

@filipos 2016-02-13 03:43:43

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

@Ruslan 2016-02-13 21:52:00

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

@Mark Waterman 2016-02-12 22:39:41

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.

@einpoklum 2016-02-12 22:50:04

Have a look at ostream joiners.

@Mark Waterman 2016-02-12 23:15:01

@einpoklum 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.

@einpoklum 2016-02-13 10:24:10

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.

@MtRoad 2016-02-12 22:11:08

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

@einpoklum 2016-02-12 22:11:53

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

@MtRoad 2016-02-12 22:21:54

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

@Matteo Italia 2016-02-12 21:57:02

Typically I do it the opposite way:

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

@Ben Voigt 2016-02-12 21:58:18

You need an if/else to make that work

@SergeyA 2016-02-12 22:02:22

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

@Matteo Italia 2016-02-12 22:03:43

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

@Christophe 2016-02-12 22:04:22

first will never go false

@SergeyA 2016-02-12 22:05:49

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

@Matteo Italia 2016-02-12 22:06:18

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

@Matteo Italia 2016-02-12 22:10:51

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

@SergeyA 2016-02-12 22:19:37

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.

@Yam Marcovic 2016-02-12 22:51:29

@SergeyA 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.

@SergeyA 2016-02-12 23:14:13

@YamMarkovic, it might, but not necessarily will.

@Deduplicator 2016-02-12 23:40:49

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

@SergeyA 2016-02-13 01:15:00

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

@James Adkison 2016-02-12 21:54:40

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"

@Tommy 2016-02-12 21:56:58

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

@Ben Voigt 2016-02-12 21:57:20

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.

@James Adkison 2016-02-12 22:00:19

@einpoklum Yes, thank you. I fixed the typo.

@R_Kapp 2016-02-12 22:01:38

@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?

@Ben Voigt 2016-02-12 22:04:17

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

Related Questions

Sponsored Content

11 Answered Questions

20 Answered Questions

[SOLVED] What is the pythonic way to detect the last element in a 'for' loop?

9 Answered Questions

[SOLVED] Pretty-print C++ STL containers

8 Answered Questions

[SOLVED] Python "Every Other Element" Idiom

  • 2010-04-13 16:11:51
  • Matt Luongo
  • 27519 View
  • 38 Score
  • 8 Answer
  • Tags:   python idioms

18 Answered Questions

[SOLVED] Best Loop Idiom for special casing the last element

0 Answered Questions

Questions in soundex algorithm

  • 2017-11-11 10:32:51
  • Cantaff0rd
  • 96 View
  • 4 Score
  • 0 Answer
  • Tags:   c++ c++11 soundex

2 Answered Questions

[SOLVED] Exception Guard Idiom in Boost::Math::Quaternion

  • 2014-02-26 03:23:17
  • Escualo
  • 82 View
  • 2 Score
  • 2 Answer
  • Tags:   c++ boost idioms

4 Answered Questions

[SOLVED] Understanding std::atomic::compare_exchange_weak() in C++11

1 Answered Questions

[SOLVED] Failed to specialize function template

Sponsored Content