the difference between for(char& c : s) and for(char c : s)?

Question

This is a problem on leetcode

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

And this is a solution:

class Solution {
public:
    bool isValid(string s) {
        stack<char> paren;
        for (char& c : s) {
            switch (c) {
                case '(': 
                case '{': 
                case '[': paren.push(c); break;
                case ')': if (paren.empty() || paren.top()!='(') return false; else paren.pop(); break;
                case '}': if (paren.empty() || paren.top()!='{') return false; else paren.pop(); break;
                case ']': if (paren.empty() || paren.top()!='[') return false; else paren.pop(); break;
                default: ; // pass
            }
        }
        return paren.empty() ;
    }
};

This is another solution:

class Solution {
public:
    bool isValid(string s) {
        stack<char> paren;
        for (char c : s) {
            switch (c) {
                case '(': 
                case '{': 
                case '[': paren.push(c); break;
                case ')': if (paren.empty() || paren.top()!='(') return false; else paren.pop(); break;
                case '}': if (paren.empty() || paren.top()!='{') return false; else paren.pop(); break;
                case ']': if (paren.empty() || paren.top()!='[') return false; else paren.pop(); break;
                default: ; // pass
            }
        }
        return paren.empty() ;
    }
};

The only difference between two solution is

for (char& c : s)

in the first solution and

for (char c : s)

in the second solution. However, the first solution only take 3ms and the second takes 6ms. So why the first solution is faster than the second solution?

One is like the parameter to the function `void foo(char&);` and the other is like `foo(char);` — Eljay, Feb 27 '18 at 00:32
Perhaps taking the function argument by constant reference (i.e. `bool isValid(string const&s)`) whereby avoiding a copy, will give you somewhat more speedup. Another thing to speed it up would be to reserve the memory for the stack (to be identical to that of the input string), avoiding re-allocations in the `push()`. — Walter, Feb 27 '18 at 00:41

Arnav Borborah · Accepted Answer · 2018-02-27T01:02:09.350

10

for (char c : s)

This creates a copy of each element in s and stores it in c. This means that modifying c does not modify s.

for (char& c : s)

This does NOT create a copy of each element in s but instead directly references and stores it in c as an alias. This means that modifying c does modify s.

Since copying can be an expensive operation, the peformance of it is slower versus referencing (even with built in types when optimizations are not present), which avoids a copy.

If you want to prevent from unknowingly modifying the string, then you can use a const reference, i.e:

for (const char& c : s)

edited Feb 27 '18 at 01:02

answered Feb 27 '18 at 00:34

Arnav Borborah

11,357
8
43
88

1

One would have thought that any level of optimisation should avoid the copy for this simple code, or not? – Walter Feb 27 '18 at 00:38
3

"the peformance of it is slower versus referencing", this is not always true, especially for build-in types. – songyuanyao Feb 27 '18 at 00:42
Thanks! I'm new to the coding and I find that I have so much to learn! – edjoker Feb 27 '18 at 00:42
@songyuanyao That presumably depends strongly on the level of optimisation, doesn't it? – Walter Feb 27 '18 at 00:44
1

@Walter Yes of course and before that performance measurement should be performed. But as a common recommendation which I learned from *Effective C++* it's "[to use pass by const ref for all types, except for builtin types (char, int, double, etc.)](https://stackoverflow.com/a/270435/3309790)". – songyuanyao Feb 27 '18 at 00:48
@songyuanyao That may well be true, but not in this case, where I am going solely off OP noticing a difference in time. – Arnav Borborah Feb 27 '18 at 01:20

the difference between for(char& c : s) and for(char c : s)?

1 Answers1