I need to move backwards through an array, so I have code like this:
for (int i = myArray.Length - 1; i >= 0; i--)
{
// Do something
myArray[i] = 42;
}
Is there a better way of doing this?
Update: I was hoping that maybe C# had some built-in mechanism for this like:
foreachbackwards (int i in myArray)
{
// so easy
}
Update 2: There are better ways. Rune takes the prize with:
for (int i = myArray.Length; i-- > 0; )
{
//do something
}
//or
for (int i = myArray.Length; i --> 0; )
{
// do something
}
which looks even better in regular C (thanks to Twotymz):
for (int i = lengthOfArray; i--; )
{
//do something
}
For C++:
As mentioned by others, when possible (i.e. when you only want each element at a time) it is strongly preferable to use iterators to both be explicit and avoid common pitfalls. Modern C++ has a more concise syntax for that with auto
:
std::vector<int> vec = {1,2,3,4};
for (auto it = vec.rbegin(); it != vec.rend(); ++it) {
std::cout<<*it<<" ";
}
prints 4 3 2 1
.
You can also modify the value during the loop:
std::vector<int> vec = {1,2,3,4};
for (auto it = vec.rbegin(); it != vec.rend(); ++it) {
*it = *it + 10;
std::cout<<*it<<" ";
}
leading to 14 13 12 11
being printed and {11, 12, 13, 14}
being in the std::vector
afterwards.
If you don't plan on modifying the value during the loop, you should make sure that you get an error when you try to do that by accident, similarly to how one might write for(const auto& element : vec)
. This is possible like this:
std::vector<int> vec = {1,2,3,4};
for (auto it = vec.crbegin(); it != vec.crend(); ++it) { // used crbegin()/crend() here...
*it = *it + 10; // ... so that this is a compile-time error
std::cout<<*it<<" ";
}
The compiler error in this case for me is:
/tmp/main.cpp:20:9: error: assignment of read-only location ‘it.std::reverse_iterator<__gnu_cxx::__normal_iterator<const int*, std::vector<int> > >::operator*()’
20 | *it = *it + 10;
| ~~~~^~~~~~~~~~
Also note that you should make sure not to use different iterator types together:
std::vector<int> vec = {1,2,3,4};
for (auto it = vec.rbegin(); it != vec.end(); ++it) { // mixed rbegin() and end()
std::cout<<*it<<" ";
}
leads to the verbose error:
/tmp/main.cpp: In function ‘int main()’:
/tmp/main.cpp:19:33: error: no match for ‘operator!=’ (operand types are ‘std::reverse_iterator<__gnu_cxx::__normal_iterator<int*, std::vector<int> > >’ and ‘std::vector<int>::iterator’ {aka ‘__gnu_cxx::__normal_iterator<int*, std::vector<int> >’})
19 | for (auto it = vec.rbegin(); it != vec.end(); ++it) {
| ~~ ^~ ~~~~~~~~~
| | |
| | std::vector<int>::iterator {aka __gnu_cxx::__normal_iterator<int*, std::vector<int> >}
| std::reverse_iterator<__gnu_cxx::__normal_iterator<int*, std::vector<int> > >
If you have C-style arrays on the stack, you can do things like this:
int vec[] = {1,2,3,4};
for (auto it = std::crbegin(vec); it != std::crend(vec); ++it) {
std::cout<<*it<<" ";
}
If you really need the index, consider the following options:
void loop_reverse(std::vector<int>& vec) {
if (vec.size() > static_cast<size_t>(std::numeric_limits<int>::max())) {
throw std::invalid_argument("Input too large");
}
const int sz = static_cast<int>(vec.size());
for(int i=sz-1; i >= 0; --i) {
// do something with i
}
}
void loop_reverse2(std::vector<int>& vec) {
for(size_t i=vec.size(); i-- > 0;) { // reverse indices from N-1 to 0
// do something with i
}
}
void loop_reverse3(std::vector<int>& vec) {
for(size_t offset=0; offset < vec.size(); ++offset) {
const size_t i = vec.size()-1-offset; // reverse indices from N-1 to 0
// do something with i
}
}
In C#, using Visual Studio 2005 or later, type 'forr' and hit [TAB] [TAB]. This will expand to a for
loop that goes backwards through a collection.
It's so easy to get wrong (at least for me), that I thought putting this snippet in would be a good idea.
That said, I like Array.Reverse()
/ Enumerable.Reverse()
and then iterate forwards better - they more clearly state intent.
The best way to do that in C++ is probably to use iterator (or better, range) adaptors, which will lazily transform the sequence as it is being traversed.
Basically,
vector<value_type> range;
foreach(value_type v, range | reversed)
cout << v;
Displays the range "range" (here, it's empty, but i'm fairly sure you can add elements yourself) in reverse order. Of course simply iterating the range is not much use, but passing that new range to algorithms and stuff is pretty cool.
This mechanism can also be used for much more powerful uses:
range | transformed(f) | filtered(p) | reversed
Will lazily compute the range "range", where function "f" is applied to all elements, elements for which "p" is not true are removed, and finally the resulting range is reversed.
Pipe syntax is the most readable IMO, given it's infix. The Boost.Range library update pending review implements this, but it's pretty simple to do it yourself also. It's even more cool with a lambda DSEL to generate the function f and the predicate p in-line.
In C++ you basicially have the choice between iterating using iterators, or indices.
Depending on whether you have a plain array, or a std::vector
, you use different techniques.
C++ allows you to do this using std::reverse_iterator:
for(std::vector<T>::reverse_iterator it = v.rbegin(); it != v.rend(); ++it) {
/* std::cout << *it; ... */
}
The unsigned integral type returned by std::vector<T>::size
is not always std::size_t
. It can be greater or less. This is crucial for the loop to work.
for(std::vector<int>::size_type i = someVector.size() - 1;
i != (std::vector<int>::size_type) -1; i--) {
/* std::cout << someVector[i]; ... */
}
It works, since unsigned integral types values are defined by means of modulo their count of bits. Thus, if you are setting -N
, you end up at (2 ^ BIT_SIZE) -N
We are using std::reverse_iterator
to do the iterating.
for(std::reverse_iterator<element_type*> it(a + sizeof a / sizeof *a), itb(a);
it != itb;
++it) {
/* std::cout << *it; .... */
}
We can safely use std::size_t
here, as opposed to above, since sizeof
always returns std::size_t
by definition.
for(std::size_t i = (sizeof a / sizeof *a) - 1; i != (std::size_t) -1; i--) {
/* std::cout << a[i]; ... */
}
Actually the above way of determining the size of an array sucks. If a is actually a pointer instead of an array (which happens quite often, and beginners will confuse it), it will silently fail. A better way is to use the following, which will fail at compile time, if given a pointer:
template<typename T, std::size_t N> char (& array_size(T(&)[N]) )[N];
It works by getting the size of the passed array first, and then declaring to return a reference to an array of type char of the same size. char
is defined to have sizeof
of: 1. So the returned array will have a sizeof
of: N * 1, which is what we are looking for, with only compile time evaluation and zero runtime overhead.
Instead of doing
(sizeof a / sizeof *a)
Change your code so that it now does
(sizeof array_size(a))
// this is how I always do it
for (i = n; --i >= 0;){
...
}
NOTE: This post ended up being far more detailed and therefore off topic, I apologize.
That being said my peers read it and believe it is valuable 'somewhere'. This thread is not the place. I would appreciate your feedback on where this should go (I am new to the site).
Anyway this is the C# version in .NET 3.5 which is amazing in that it works on any collection type using the defined semantics. This is a default measure (reuse!) not performance or CPU cycle minimization in most common dev scenario although that never seems to be what happens in the real world (premature optimization).
*** Extension method working over any collection type and taking an action delegate expecting a single value of the type, all executed over each item in reverse **
Requres 3.5:
public static void PerformOverReversed<T>(this IEnumerable<T> sequenceToReverse, Action<T> doForEachReversed)
{
foreach (var contextItem in sequenceToReverse.Reverse())
doForEachReversed(contextItem);
}
Older .NET versions or do you want to understand Linq internals better? Read on.. Or not..
ASSUMPTION: In the .NET type system the Array type inherits from the IEnumerable interface (not the generic IEnumerable only IEnumerable).
This is all you need to iterate from beginning to end, however you want to move in the opposite direction. As IEnumerable works on Array of type 'object' any type is valid,
CRITICAL MEASURE: We assume if you can process any sequence in reverse order that is 'better' then only being able to do it on integers.
Solution a for .NET CLR 2.0-3.0:
Description: We will accept any IEnumerable implementing instance with the mandate that each instance it contains is of the same type. So if we recieve an array the entire array contains instances of type X. If any other instances are of a type !=X an exception is thrown:
A singleton service:
public class ReverserService { private ReverserService() { }
/// <summary>
/// Most importantly uses yield command for efficiency
/// </summary>
/// <param name="enumerableInstance"></param>
/// <returns></returns>
public static IEnumerable ToReveresed(IEnumerable enumerableInstance)
{
if (enumerableInstance == null)
{
throw new ArgumentNullException("enumerableInstance");
}
// First we need to move forwarad and create a temp
// copy of a type that allows us to move backwards
// We can use ArrayList for this as the concrete
// type
IList reversedEnumerable = new ArrayList();
IEnumerator tempEnumerator = enumerableInstance.GetEnumerator();
while (tempEnumerator.MoveNext())
{
reversedEnumerable.Add(tempEnumerator.Current);
}
// Now we do the standard reverse over this using yield to return
// the result
// NOTE: This is an immutable result by design. That is
// a design goal for this simple question as well as most other set related
// requirements, which is why Linq results are immutable for example
// In fact this is foundational code to understand Linq
for (var i = reversedEnumerable.Count - 1; i >= 0; i--)
{
yield return reversedEnumerable[i];
}
}
}
public static class ExtensionMethods
{
public static IEnumerable ToReveresed(this IEnumerable enumerableInstance)
{
return ReverserService.ToReveresed(enumerableInstance);
}
}
[TestFixture] public class Testing123 {
/// <summary>
/// .NET 1.1 CLR
/// </summary>
[Test]
public void Tester_fornet_1_dot_1()
{
const int initialSize = 1000;
// Create the baseline data
int[] myArray = new int[initialSize];
for (var i = 0; i < initialSize; i++)
{
myArray[i] = i + 1;
}
IEnumerable _revered = ReverserService.ToReveresed(myArray);
Assert.IsTrue(TestAndGetResult(_revered).Equals(1000));
}
[Test]
public void tester_why_this_is_good()
{
ArrayList names = new ArrayList();
names.Add("Jim");
names.Add("Bob");
names.Add("Eric");
names.Add("Sam");
IEnumerable _revered = ReverserService.ToReveresed(names);
Assert.IsTrue(TestAndGetResult(_revered).Equals("Sam"));
}
[Test]
public void tester_extension_method()
{
// Extension Methods No Linq (Linq does this for you as I will show)
var enumerableOfInt = Enumerable.Range(1, 1000);
// Use Extension Method - which simply wraps older clr code
IEnumerable _revered = enumerableOfInt.ToReveresed();
Assert.IsTrue(TestAndGetResult(_revered).Equals(1000));
}
[Test]
public void tester_linq_3_dot_5_clr()
{
// Extension Methods No Linq (Linq does this for you as I will show)
IEnumerable enumerableOfInt = Enumerable.Range(1, 1000);
// Reverse is Linq (which is are extension methods off IEnumerable<T>
// Note you must case IEnumerable (non generic) using OfType or Cast
IEnumerable _revered = enumerableOfInt.Cast<int>().Reverse();
Assert.IsTrue(TestAndGetResult(_revered).Equals(1000));
}
[Test]
public void tester_final_and_recommended_colution()
{
var enumerableOfInt = Enumerable.Range(1, 1000);
enumerableOfInt.PerformOverReversed(i => Debug.WriteLine(i));
}
private static object TestAndGetResult(IEnumerable enumerableIn)
{
// IEnumerable x = ReverserService.ToReveresed(names);
Assert.IsTrue(enumerableIn != null);
IEnumerator _test = enumerableIn.GetEnumerator();
// Move to first
Assert.IsTrue(_test.MoveNext());
return _test.Current;
}
}
In C#, using Visual Studio 2005 or later, type 'forr' and hit [TAB] [TAB]. This will expand to a for
loop that goes backwards through a collection.
It's so easy to get wrong (at least for me), that I thought putting this snippet in would be a good idea.
That said, I like Array.Reverse()
/ Enumerable.Reverse()
and then iterate forwards better - they more clearly state intent.
I'd use the code in the original question, but if you really wanted to use foreach and have an integer index in C#:
foreach (int i in Enumerable.Range(0, myArray.Length).Reverse())
{
myArray[i] = 42;
}
I'm going to try answering my own question here, but I don't really like this, either:
for (int i = 0; i < myArray.Length; i++)
{
int iBackwards = myArray.Length - 1 - i; // ugh
myArray[iBackwards] = 666;
}
NOTE: This post ended up being far more detailed and therefore off topic, I apologize.
That being said my peers read it and believe it is valuable 'somewhere'. This thread is not the place. I would appreciate your feedback on where this should go (I am new to the site).
Anyway this is the C# version in .NET 3.5 which is amazing in that it works on any collection type using the defined semantics. This is a default measure (reuse!) not performance or CPU cycle minimization in most common dev scenario although that never seems to be what happens in the real world (premature optimization).
*** Extension method working over any collection type and taking an action delegate expecting a single value of the type, all executed over each item in reverse **
Requres 3.5:
public static void PerformOverReversed<T>(this IEnumerable<T> sequenceToReverse, Action<T> doForEachReversed)
{
foreach (var contextItem in sequenceToReverse.Reverse())
doForEachReversed(contextItem);
}
Older .NET versions or do you want to understand Linq internals better? Read on.. Or not..
ASSUMPTION: In the .NET type system the Array type inherits from the IEnumerable interface (not the generic IEnumerable only IEnumerable).
This is all you need to iterate from beginning to end, however you want to move in the opposite direction. As IEnumerable works on Array of type 'object' any type is valid,
CRITICAL MEASURE: We assume if you can process any sequence in reverse order that is 'better' then only being able to do it on integers.
Solution a for .NET CLR 2.0-3.0:
Description: We will accept any IEnumerable implementing instance with the mandate that each instance it contains is of the same type. So if we recieve an array the entire array contains instances of type X. If any other instances are of a type !=X an exception is thrown:
A singleton service:
public class ReverserService { private ReverserService() { }
/// <summary>
/// Most importantly uses yield command for efficiency
/// </summary>
/// <param name="enumerableInstance"></param>
/// <returns></returns>
public static IEnumerable ToReveresed(IEnumerable enumerableInstance)
{
if (enumerableInstance == null)
{
throw new ArgumentNullException("enumerableInstance");
}
// First we need to move forwarad and create a temp
// copy of a type that allows us to move backwards
// We can use ArrayList for this as the concrete
// type
IList reversedEnumerable = new ArrayList();
IEnumerator tempEnumerator = enumerableInstance.GetEnumerator();
while (tempEnumerator.MoveNext())
{
reversedEnumerable.Add(tempEnumerator.Current);
}
// Now we do the standard reverse over this using yield to return
// the result
// NOTE: This is an immutable result by design. That is
// a design goal for this simple question as well as most other set related
// requirements, which is why Linq results are immutable for example
// In fact this is foundational code to understand Linq
for (var i = reversedEnumerable.Count - 1; i >= 0; i--)
{
yield return reversedEnumerable[i];
}
}
}
public static class ExtensionMethods
{
public static IEnumerable ToReveresed(this IEnumerable enumerableInstance)
{
return ReverserService.ToReveresed(enumerableInstance);
}
}
[TestFixture] public class Testing123 {
/// <summary>
/// .NET 1.1 CLR
/// </summary>
[Test]
public void Tester_fornet_1_dot_1()
{
const int initialSize = 1000;
// Create the baseline data
int[] myArray = new int[initialSize];
for (var i = 0; i < initialSize; i++)
{
myArray[i] = i + 1;
}
IEnumerable _revered = ReverserService.ToReveresed(myArray);
Assert.IsTrue(TestAndGetResult(_revered).Equals(1000));
}
[Test]
public void tester_why_this_is_good()
{
ArrayList names = new ArrayList();
names.Add("Jim");
names.Add("Bob");
names.Add("Eric");
names.Add("Sam");
IEnumerable _revered = ReverserService.ToReveresed(names);
Assert.IsTrue(TestAndGetResult(_revered).Equals("Sam"));
}
[Test]
public void tester_extension_method()
{
// Extension Methods No Linq (Linq does this for you as I will show)
var enumerableOfInt = Enumerable.Range(1, 1000);
// Use Extension Method - which simply wraps older clr code
IEnumerable _revered = enumerableOfInt.ToReveresed();
Assert.IsTrue(TestAndGetResult(_revered).Equals(1000));
}
[Test]
public void tester_linq_3_dot_5_clr()
{
// Extension Methods No Linq (Linq does this for you as I will show)
IEnumerable enumerableOfInt = Enumerable.Range(1, 1000);
// Reverse is Linq (which is are extension methods off IEnumerable<T>
// Note you must case IEnumerable (non generic) using OfType or Cast
IEnumerable _revered = enumerableOfInt.Cast<int>().Reverse();
Assert.IsTrue(TestAndGetResult(_revered).Equals(1000));
}
[Test]
public void tester_final_and_recommended_colution()
{
var enumerableOfInt = Enumerable.Range(1, 1000);
enumerableOfInt.PerformOverReversed(i => Debug.WriteLine(i));
}
private static object TestAndGetResult(IEnumerable enumerableIn)
{
// IEnumerable x = ReverserService.ToReveresed(names);
Assert.IsTrue(enumerableIn != null);
IEnumerator _test = enumerableIn.GetEnumerator();
// Move to first
Assert.IsTrue(_test.MoveNext());
return _test.Current;
}
}
I prefer a while loop. It's more clear to me than decrementing i
in the condition of a for loop
int i = arrayLength;
while(i)
{
i--;
//do something with array[i]
}
In C I like to do this:
int i = myArray.Length;
while (i--) {
myArray[i] = 42;
}
C# example added by MusiGenesis:
{int i = myArray.Length; while (i-- > 0)
{
myArray[i] = 42;
}}
I would always prefer clear code against 'typographically pleasing' code. Thus, I would always use :
for (int i = myArray.Length - 1; i >= 0; i--)
{
// Do something ...
}
You can consider it as the standard way to loop backwards.
Just my two cents...
For C++:
As mentioned by others, when possible (i.e. when you only want each element at a time) it is strongly preferable to use iterators to both be explicit and avoid common pitfalls. Modern C++ has a more concise syntax for that with auto
:
std::vector<int> vec = {1,2,3,4};
for (auto it = vec.rbegin(); it != vec.rend(); ++it) {
std::cout<<*it<<" ";
}
prints 4 3 2 1
.
You can also modify the value during the loop:
std::vector<int> vec = {1,2,3,4};
for (auto it = vec.rbegin(); it != vec.rend(); ++it) {
*it = *it + 10;
std::cout<<*it<<" ";
}
leading to 14 13 12 11
being printed and {11, 12, 13, 14}
being in the std::vector
afterwards.
If you don't plan on modifying the value during the loop, you should make sure that you get an error when you try to do that by accident, similarly to how one might write for(const auto& element : vec)
. This is possible like this:
std::vector<int> vec = {1,2,3,4};
for (auto it = vec.crbegin(); it != vec.crend(); ++it) { // used crbegin()/crend() here...
*it = *it + 10; // ... so that this is a compile-time error
std::cout<<*it<<" ";
}
The compiler error in this case for me is:
/tmp/main.cpp:20:9: error: assignment of read-only location ‘it.std::reverse_iterator<__gnu_cxx::__normal_iterator<const int*, std::vector<int> > >::operator*()’
20 | *it = *it + 10;
| ~~~~^~~~~~~~~~
Also note that you should make sure not to use different iterator types together:
std::vector<int> vec = {1,2,3,4};
for (auto it = vec.rbegin(); it != vec.end(); ++it) { // mixed rbegin() and end()
std::cout<<*it<<" ";
}
leads to the verbose error:
/tmp/main.cpp: In function ‘int main()’:
/tmp/main.cpp:19:33: error: no match for ‘operator!=’ (operand types are ‘std::reverse_iterator<__gnu_cxx::__normal_iterator<int*, std::vector<int> > >’ and ‘std::vector<int>::iterator’ {aka ‘__gnu_cxx::__normal_iterator<int*, std::vector<int> >’})
19 | for (auto it = vec.rbegin(); it != vec.end(); ++it) {
| ~~ ^~ ~~~~~~~~~
| | |
| | std::vector<int>::iterator {aka __gnu_cxx::__normal_iterator<int*, std::vector<int> >}
| std::reverse_iterator<__gnu_cxx::__normal_iterator<int*, std::vector<int> > >
If you have C-style arrays on the stack, you can do things like this:
int vec[] = {1,2,3,4};
for (auto it = std::crbegin(vec); it != std::crend(vec); ++it) {
std::cout<<*it<<" ";
}
If you really need the index, consider the following options:
void loop_reverse(std::vector<int>& vec) {
if (vec.size() > static_cast<size_t>(std::numeric_limits<int>::max())) {
throw std::invalid_argument("Input too large");
}
const int sz = static_cast<int>(vec.size());
for(int i=sz-1; i >= 0; --i) {
// do something with i
}
}
void loop_reverse2(std::vector<int>& vec) {
for(size_t i=vec.size(); i-- > 0;) { // reverse indices from N-1 to 0
// do something with i
}
}
void loop_reverse3(std::vector<int>& vec) {
for(size_t offset=0; offset < vec.size(); ++offset) {
const size_t i = vec.size()-1-offset; // reverse indices from N-1 to 0
// do something with i
}
}
Looks good to me. If the indexer was unsigned (uint etc), you might have to take that into account. Call me lazy, but in that (unsigned) case, I might just use a counter-variable:
uint pos = arr.Length;
for(uint i = 0; i < arr.Length ; i++)
{
arr[--pos] = 42;
}
(actually, even here you'd need to be careful of cases like arr.Length = uint.MaxValue... maybe a != somewhere... of course, that is a very unlikely case!)
In C# using Linq:
foreach(var item in myArray.Reverse())
{
// do something
}
In C++ you basicially have the choice between iterating using iterators, or indices.
Depending on whether you have a plain array, or a std::vector
, you use different techniques.
C++ allows you to do this using std::reverse_iterator:
for(std::vector<T>::reverse_iterator it = v.rbegin(); it != v.rend(); ++it) {
/* std::cout << *it; ... */
}
The unsigned integral type returned by std::vector<T>::size
is not always std::size_t
. It can be greater or less. This is crucial for the loop to work.
for(std::vector<int>::size_type i = someVector.size() - 1;
i != (std::vector<int>::size_type) -1; i--) {
/* std::cout << someVector[i]; ... */
}
It works, since unsigned integral types values are defined by means of modulo their count of bits. Thus, if you are setting -N
, you end up at (2 ^ BIT_SIZE) -N
We are using std::reverse_iterator
to do the iterating.
for(std::reverse_iterator<element_type*> it(a + sizeof a / sizeof *a), itb(a);
it != itb;
++it) {
/* std::cout << *it; .... */
}
We can safely use std::size_t
here, as opposed to above, since sizeof
always returns std::size_t
by definition.
for(std::size_t i = (sizeof a / sizeof *a) - 1; i != (std::size_t) -1; i--) {
/* std::cout << a[i]; ... */
}
Actually the above way of determining the size of an array sucks. If a is actually a pointer instead of an array (which happens quite often, and beginners will confuse it), it will silently fail. A better way is to use the following, which will fail at compile time, if given a pointer:
template<typename T, std::size_t N> char (& array_size(T(&)[N]) )[N];
It works by getting the size of the passed array first, and then declaring to return a reference to an array of type char of the same size. char
is defined to have sizeof
of: 1. So the returned array will have a sizeof
of: N * 1, which is what we are looking for, with only compile time evaluation and zero runtime overhead.
Instead of doing
(sizeof a / sizeof *a)
Change your code so that it now does
(sizeof array_size(a))
// this is how I always do it
for (i = n; --i >= 0;){
...
}
The best way to do that in C++ is probably to use iterator (or better, range) adaptors, which will lazily transform the sequence as it is being traversed.
Basically,
vector<value_type> range;
foreach(value_type v, range | reversed)
cout << v;
Displays the range "range" (here, it's empty, but i'm fairly sure you can add elements yourself) in reverse order. Of course simply iterating the range is not much use, but passing that new range to algorithms and stuff is pretty cool.
This mechanism can also be used for much more powerful uses:
range | transformed(f) | filtered(p) | reversed
Will lazily compute the range "range", where function "f" is applied to all elements, elements for which "p" is not true are removed, and finally the resulting range is reversed.
Pipe syntax is the most readable IMO, given it's infix. The Boost.Range library update pending review implements this, but it's pretty simple to do it yourself also. It's even more cool with a lambda DSEL to generate the function f and the predicate p in-line.
NOTE: This post ended up being far more detailed and therefore off topic, I apologize.
That being said my peers read it and believe it is valuable 'somewhere'. This thread is not the place. I would appreciate your feedback on where this should go (I am new to the site).
Anyway this is the C# version in .NET 3.5 which is amazing in that it works on any collection type using the defined semantics. This is a default measure (reuse!) not performance or CPU cycle minimization in most common dev scenario although that never seems to be what happens in the real world (premature optimization).
*** Extension method working over any collection type and taking an action delegate expecting a single value of the type, all executed over each item in reverse **
Requres 3.5:
public static void PerformOverReversed<T>(this IEnumerable<T> sequenceToReverse, Action<T> doForEachReversed)
{
foreach (var contextItem in sequenceToReverse.Reverse())
doForEachReversed(contextItem);
}
Older .NET versions or do you want to understand Linq internals better? Read on.. Or not..
ASSUMPTION: In the .NET type system the Array type inherits from the IEnumerable interface (not the generic IEnumerable only IEnumerable).
This is all you need to iterate from beginning to end, however you want to move in the opposite direction. As IEnumerable works on Array of type 'object' any type is valid,
CRITICAL MEASURE: We assume if you can process any sequence in reverse order that is 'better' then only being able to do it on integers.
Solution a for .NET CLR 2.0-3.0:
Description: We will accept any IEnumerable implementing instance with the mandate that each instance it contains is of the same type. So if we recieve an array the entire array contains instances of type X. If any other instances are of a type !=X an exception is thrown:
A singleton service:
public class ReverserService { private ReverserService() { }
/// <summary>
/// Most importantly uses yield command for efficiency
/// </summary>
/// <param name="enumerableInstance"></param>
/// <returns></returns>
public static IEnumerable ToReveresed(IEnumerable enumerableInstance)
{
if (enumerableInstance == null)
{
throw new ArgumentNullException("enumerableInstance");
}
// First we need to move forwarad and create a temp
// copy of a type that allows us to move backwards
// We can use ArrayList for this as the concrete
// type
IList reversedEnumerable = new ArrayList();
IEnumerator tempEnumerator = enumerableInstance.GetEnumerator();
while (tempEnumerator.MoveNext())
{
reversedEnumerable.Add(tempEnumerator.Current);
}
// Now we do the standard reverse over this using yield to return
// the result
// NOTE: This is an immutable result by design. That is
// a design goal for this simple question as well as most other set related
// requirements, which is why Linq results are immutable for example
// In fact this is foundational code to understand Linq
for (var i = reversedEnumerable.Count - 1; i >= 0; i--)
{
yield return reversedEnumerable[i];
}
}
}
public static class ExtensionMethods
{
public static IEnumerable ToReveresed(this IEnumerable enumerableInstance)
{
return ReverserService.ToReveresed(enumerableInstance);
}
}
[TestFixture] public class Testing123 {
/// <summary>
/// .NET 1.1 CLR
/// </summary>
[Test]
public void Tester_fornet_1_dot_1()
{
const int initialSize = 1000;
// Create the baseline data
int[] myArray = new int[initialSize];
for (var i = 0; i < initialSize; i++)
{
myArray[i] = i + 1;
}
IEnumerable _revered = ReverserService.ToReveresed(myArray);
Assert.IsTrue(TestAndGetResult(_revered).Equals(1000));
}
[Test]
public void tester_why_this_is_good()
{
ArrayList names = new ArrayList();
names.Add("Jim");
names.Add("Bob");
names.Add("Eric");
names.Add("Sam");
IEnumerable _revered = ReverserService.ToReveresed(names);
Assert.IsTrue(TestAndGetResult(_revered).Equals("Sam"));
}
[Test]
public void tester_extension_method()
{
// Extension Methods No Linq (Linq does this for you as I will show)
var enumerableOfInt = Enumerable.Range(1, 1000);
// Use Extension Method - which simply wraps older clr code
IEnumerable _revered = enumerableOfInt.ToReveresed();
Assert.IsTrue(TestAndGetResult(_revered).Equals(1000));
}
[Test]
public void tester_linq_3_dot_5_clr()
{
// Extension Methods No Linq (Linq does this for you as I will show)
IEnumerable enumerableOfInt = Enumerable.Range(1, 1000);
// Reverse is Linq (which is are extension methods off IEnumerable<T>
// Note you must case IEnumerable (non generic) using OfType or Cast
IEnumerable _revered = enumerableOfInt.Cast<int>().Reverse();
Assert.IsTrue(TestAndGetResult(_revered).Equals(1000));
}
[Test]
public void tester_final_and_recommended_colution()
{
var enumerableOfInt = Enumerable.Range(1, 1000);
enumerableOfInt.PerformOverReversed(i => Debug.WriteLine(i));
}
private static object TestAndGetResult(IEnumerable enumerableIn)
{
// IEnumerable x = ReverserService.ToReveresed(names);
Assert.IsTrue(enumerableIn != null);
IEnumerator _test = enumerableIn.GetEnumerator();
// Move to first
Assert.IsTrue(_test.MoveNext());
return _test.Current;
}
}
In C I like to do this:
int i = myArray.Length;
while (i--) {
myArray[i] = 42;
}
C# example added by MusiGenesis:
{int i = myArray.Length; while (i-- > 0)
{
myArray[i] = 42;
}}
In C++ you basicially have the choice between iterating using iterators, or indices.
Depending on whether you have a plain array, or a std::vector
, you use different techniques.
C++ allows you to do this using std::reverse_iterator:
for(std::vector<T>::reverse_iterator it = v.rbegin(); it != v.rend(); ++it) {
/* std::cout << *it; ... */
}
The unsigned integral type returned by std::vector<T>::size
is not always std::size_t
. It can be greater or less. This is crucial for the loop to work.
for(std::vector<int>::size_type i = someVector.size() - 1;
i != (std::vector<int>::size_type) -1; i--) {
/* std::cout << someVector[i]; ... */
}
It works, since unsigned integral types values are defined by means of modulo their count of bits. Thus, if you are setting -N
, you end up at (2 ^ BIT_SIZE) -N
We are using std::reverse_iterator
to do the iterating.
for(std::reverse_iterator<element_type*> it(a + sizeof a / sizeof *a), itb(a);
it != itb;
++it) {
/* std::cout << *it; .... */
}
We can safely use std::size_t
here, as opposed to above, since sizeof
always returns std::size_t
by definition.
for(std::size_t i = (sizeof a / sizeof *a) - 1; i != (std::size_t) -1; i--) {
/* std::cout << a[i]; ... */
}
Actually the above way of determining the size of an array sucks. If a is actually a pointer instead of an array (which happens quite often, and beginners will confuse it), it will silently fail. A better way is to use the following, which will fail at compile time, if given a pointer:
template<typename T, std::size_t N> char (& array_size(T(&)[N]) )[N];
It works by getting the size of the passed array first, and then declaring to return a reference to an array of type char of the same size. char
is defined to have sizeof
of: 1. So the returned array will have a sizeof
of: N * 1, which is what we are looking for, with only compile time evaluation and zero runtime overhead.
Instead of doing
(sizeof a / sizeof *a)
Change your code so that it now does
(sizeof array_size(a))
That's definitely the best way for any array whose length is a signed integral type. For arrays whose lengths are an unsigned integral type (e.g. an std::vector
in C++), then you need to modify the end condition slightly:
for(size_t i = myArray.size() - 1; i != (size_t)-1; i--)
// blah
If you just said i >= 0
, this is always true for an unsigned integer, so the loop will be an infinite loop.
In C#, using Visual Studio 2005 or later, type 'forr' and hit [TAB] [TAB]. This will expand to a for
loop that goes backwards through a collection.
It's so easy to get wrong (at least for me), that I thought putting this snippet in would be a good idea.
That said, I like Array.Reverse()
/ Enumerable.Reverse()
and then iterate forwards better - they more clearly state intent.
In C# using Linq:
foreach(var item in myArray.Reverse())
{
// do something
}
I prefer a while loop. It's more clear to me than decrementing i
in the condition of a for loop
int i = arrayLength;
while(i)
{
i--;
//do something with array[i]
}
I'm going to try answering my own question here, but I don't really like this, either:
for (int i = 0; i < myArray.Length; i++)
{
int iBackwards = myArray.Length - 1 - i; // ugh
myArray[iBackwards] = 666;
}
// this is how I always do it
for (i = n; --i >= 0;){
...
}
The best way to do that in C++ is probably to use iterator (or better, range) adaptors, which will lazily transform the sequence as it is being traversed.
Basically,
vector<value_type> range;
foreach(value_type v, range | reversed)
cout << v;
Displays the range "range" (here, it's empty, but i'm fairly sure you can add elements yourself) in reverse order. Of course simply iterating the range is not much use, but passing that new range to algorithms and stuff is pretty cool.
This mechanism can also be used for much more powerful uses:
range | transformed(f) | filtered(p) | reversed
Will lazily compute the range "range", where function "f" is applied to all elements, elements for which "p" is not true are removed, and finally the resulting range is reversed.
Pipe syntax is the most readable IMO, given it's infix. The Boost.Range library update pending review implements this, but it's pretty simple to do it yourself also. It's even more cool with a lambda DSEL to generate the function f and the predicate p in-line.
In C++ you basicially have the choice between iterating using iterators, or indices.
Depending on whether you have a plain array, or a std::vector
, you use different techniques.
C++ allows you to do this using std::reverse_iterator:
for(std::vector<T>::reverse_iterator it = v.rbegin(); it != v.rend(); ++it) {
/* std::cout << *it; ... */
}
The unsigned integral type returned by std::vector<T>::size
is not always std::size_t
. It can be greater or less. This is crucial for the loop to work.
for(std::vector<int>::size_type i = someVector.size() - 1;
i != (std::vector<int>::size_type) -1; i--) {
/* std::cout << someVector[i]; ... */
}
It works, since unsigned integral types values are defined by means of modulo their count of bits. Thus, if you are setting -N
, you end up at (2 ^ BIT_SIZE) -N
We are using std::reverse_iterator
to do the iterating.
for(std::reverse_iterator<element_type*> it(a + sizeof a / sizeof *a), itb(a);
it != itb;
++it) {
/* std::cout << *it; .... */
}
We can safely use std::size_t
here, as opposed to above, since sizeof
always returns std::size_t
by definition.
for(std::size_t i = (sizeof a / sizeof *a) - 1; i != (std::size_t) -1; i--) {
/* std::cout << a[i]; ... */
}
Actually the above way of determining the size of an array sucks. If a is actually a pointer instead of an array (which happens quite often, and beginners will confuse it), it will silently fail. A better way is to use the following, which will fail at compile time, if given a pointer:
template<typename T, std::size_t N> char (& array_size(T(&)[N]) )[N];
It works by getting the size of the passed array first, and then declaring to return a reference to an array of type char of the same size. char
is defined to have sizeof
of: 1. So the returned array will have a sizeof
of: N * 1, which is what we are looking for, with only compile time evaluation and zero runtime overhead.
Instead of doing
(sizeof a / sizeof *a)
Change your code so that it now does
(sizeof array_size(a))
In C# using Linq:
foreach(var item in myArray.Reverse())
{
// do something
}
That's definitely the best way for any array whose length is a signed integral type. For arrays whose lengths are an unsigned integral type (e.g. an std::vector
in C++), then you need to modify the end condition slightly:
for(size_t i = myArray.size() - 1; i != (size_t)-1; i--)
// blah
If you just said i >= 0
, this is always true for an unsigned integer, so the loop will be an infinite loop.
Looks good to me. If the indexer was unsigned (uint etc), you might have to take that into account. Call me lazy, but in that (unsigned) case, I might just use a counter-variable:
uint pos = arr.Length;
for(uint i = 0; i < arr.Length ; i++)
{
arr[--pos] = 42;
}
(actually, even here you'd need to be careful of cases like arr.Length = uint.MaxValue... maybe a != somewhere... of course, that is a very unlikely case!)
In C I like to do this:
int i = myArray.Length;
while (i--) {
myArray[i] = 42;
}
C# example added by MusiGenesis:
{int i = myArray.Length; while (i-- > 0)
{
myArray[i] = 42;
}}
// this is how I always do it
for (i = n; --i >= 0;){
...
}
In C#, using Visual Studio 2005 or later, type 'forr' and hit [TAB] [TAB]. This will expand to a for
loop that goes backwards through a collection.
It's so easy to get wrong (at least for me), that I thought putting this snippet in would be a good idea.
That said, I like Array.Reverse()
/ Enumerable.Reverse()
and then iterate forwards better - they more clearly state intent.
That's definitely the best way for any array whose length is a signed integral type. For arrays whose lengths are an unsigned integral type (e.g. an std::vector
in C++), then you need to modify the end condition slightly:
for(size_t i = myArray.size() - 1; i != (size_t)-1; i--)
// blah
If you just said i >= 0
, this is always true for an unsigned integer, so the loop will be an infinite loop.
The best way to do that in C++ is probably to use iterator (or better, range) adaptors, which will lazily transform the sequence as it is being traversed.
Basically,
vector<value_type> range;
foreach(value_type v, range | reversed)
cout << v;
Displays the range "range" (here, it's empty, but i'm fairly sure you can add elements yourself) in reverse order. Of course simply iterating the range is not much use, but passing that new range to algorithms and stuff is pretty cool.
This mechanism can also be used for much more powerful uses:
range | transformed(f) | filtered(p) | reversed
Will lazily compute the range "range", where function "f" is applied to all elements, elements for which "p" is not true are removed, and finally the resulting range is reversed.
Pipe syntax is the most readable IMO, given it's infix. The Boost.Range library update pending review implements this, but it's pretty simple to do it yourself also. It's even more cool with a lambda DSEL to generate the function f and the predicate p in-line.
I'd use the code in the original question, but if you really wanted to use foreach and have an integer index in C#:
foreach (int i in Enumerable.Range(0, myArray.Length).Reverse())
{
myArray[i] = 42;
}
In C I like to do this:
int i = myArray.Length;
while (i--) {
myArray[i] = 42;
}
C# example added by MusiGenesis:
{int i = myArray.Length; while (i-- > 0)
{
myArray[i] = 42;
}}
I'd use the code in the original question, but if you really wanted to use foreach and have an integer index in C#:
foreach (int i in Enumerable.Range(0, myArray.Length).Reverse())
{
myArray[i] = 42;
}
In C# using Linq:
foreach(var item in myArray.Reverse())
{
// do something
}
Looks good to me. If the indexer was unsigned (uint etc), you might have to take that into account. Call me lazy, but in that (unsigned) case, I might just use a counter-variable:
uint pos = arr.Length;
for(uint i = 0; i < arr.Length ; i++)
{
arr[--pos] = 42;
}
(actually, even here you'd need to be careful of cases like arr.Length = uint.MaxValue... maybe a != somewhere... of course, that is a very unlikely case!)
That's definitely the best way for any array whose length is a signed integral type. For arrays whose lengths are an unsigned integral type (e.g. an std::vector
in C++), then you need to modify the end condition slightly:
for(size_t i = myArray.size() - 1; i != (size_t)-1; i--)
// blah
If you just said i >= 0
, this is always true for an unsigned integer, so the loop will be an infinite loop.
Looks good to me. If the indexer was unsigned (uint etc), you might have to take that into account. Call me lazy, but in that (unsigned) case, I might just use a counter-variable:
uint pos = arr.Length;
for(uint i = 0; i < arr.Length ; i++)
{
arr[--pos] = 42;
}
(actually, even here you'd need to be careful of cases like arr.Length = uint.MaxValue... maybe a != somewhere... of course, that is a very unlikely case!)
NOTE: This post ended up being far more detailed and therefore off topic, I apologize.
That being said my peers read it and believe it is valuable 'somewhere'. This thread is not the place. I would appreciate your feedback on where this should go (I am new to the site).
Anyway this is the C# version in .NET 3.5 which is amazing in that it works on any collection type using the defined semantics. This is a default measure (reuse!) not performance or CPU cycle minimization in most common dev scenario although that never seems to be what happens in the real world (premature optimization).
*** Extension method working over any collection type and taking an action delegate expecting a single value of the type, all executed over each item in reverse **
Requres 3.5:
public static void PerformOverReversed<T>(this IEnumerable<T> sequenceToReverse, Action<T> doForEachReversed)
{
foreach (var contextItem in sequenceToReverse.Reverse())
doForEachReversed(contextItem);
}
Older .NET versions or do you want to understand Linq internals better? Read on.. Or not..
ASSUMPTION: In the .NET type system the Array type inherits from the IEnumerable interface (not the generic IEnumerable only IEnumerable).
This is all you need to iterate from beginning to end, however you want to move in the opposite direction. As IEnumerable works on Array of type 'object' any type is valid,
CRITICAL MEASURE: We assume if you can process any sequence in reverse order that is 'better' then only being able to do it on integers.
Solution a for .NET CLR 2.0-3.0:
Description: We will accept any IEnumerable implementing instance with the mandate that each instance it contains is of the same type. So if we recieve an array the entire array contains instances of type X. If any other instances are of a type !=X an exception is thrown:
A singleton service:
public class ReverserService { private ReverserService() { }
/// <summary>
/// Most importantly uses yield command for efficiency
/// </summary>
/// <param name="enumerableInstance"></param>
/// <returns></returns>
public static IEnumerable ToReveresed(IEnumerable enumerableInstance)
{
if (enumerableInstance == null)
{
throw new ArgumentNullException("enumerableInstance");
}
// First we need to move forwarad and create a temp
// copy of a type that allows us to move backwards
// We can use ArrayList for this as the concrete
// type
IList reversedEnumerable = new ArrayList();
IEnumerator tempEnumerator = enumerableInstance.GetEnumerator();
while (tempEnumerator.MoveNext())
{
reversedEnumerable.Add(tempEnumerator.Current);
}
// Now we do the standard reverse over this using yield to return
// the result
// NOTE: This is an immutable result by design. That is
// a design goal for this simple question as well as most other set related
// requirements, which is why Linq results are immutable for example
// In fact this is foundational code to understand Linq
for (var i = reversedEnumerable.Count - 1; i >= 0; i--)
{
yield return reversedEnumerable[i];
}
}
}
public static class ExtensionMethods
{
public static IEnumerable ToReveresed(this IEnumerable enumerableInstance)
{
return ReverserService.ToReveresed(enumerableInstance);
}
}
[TestFixture] public class Testing123 {
/// <summary>
/// .NET 1.1 CLR
/// </summary>
[Test]
public void Tester_fornet_1_dot_1()
{
const int initialSize = 1000;
// Create the baseline data
int[] myArray = new int[initialSize];
for (var i = 0; i < initialSize; i++)
{
myArray[i] = i + 1;
}
IEnumerable _revered = ReverserService.ToReveresed(myArray);
Assert.IsTrue(TestAndGetResult(_revered).Equals(1000));
}
[Test]
public void tester_why_this_is_good()
{
ArrayList names = new ArrayList();
names.Add("Jim");
names.Add("Bob");
names.Add("Eric");
names.Add("Sam");
IEnumerable _revered = ReverserService.ToReveresed(names);
Assert.IsTrue(TestAndGetResult(_revered).Equals("Sam"));
}
[Test]
public void tester_extension_method()
{
// Extension Methods No Linq (Linq does this for you as I will show)
var enumerableOfInt = Enumerable.Range(1, 1000);
// Use Extension Method - which simply wraps older clr code
IEnumerable _revered = enumerableOfInt.ToReveresed();
Assert.IsTrue(TestAndGetResult(_revered).Equals(1000));
}
[Test]
public void tester_linq_3_dot_5_clr()
{
// Extension Methods No Linq (Linq does this for you as I will show)
IEnumerable enumerableOfInt = Enumerable.Range(1, 1000);
// Reverse is Linq (which is are extension methods off IEnumerable<T>
// Note you must case IEnumerable (non generic) using OfType or Cast
IEnumerable _revered = enumerableOfInt.Cast<int>().Reverse();
Assert.IsTrue(TestAndGetResult(_revered).Equals(1000));
}
[Test]
public void tester_final_and_recommended_colution()
{
var enumerableOfInt = Enumerable.Range(1, 1000);
enumerableOfInt.PerformOverReversed(i => Debug.WriteLine(i));
}
private static object TestAndGetResult(IEnumerable enumerableIn)
{
// IEnumerable x = ReverserService.ToReveresed(names);
Assert.IsTrue(enumerableIn != null);
IEnumerator _test = enumerableIn.GetEnumerator();
// Move to first
Assert.IsTrue(_test.MoveNext());
return _test.Current;
}
}
I would always prefer clear code against 'typographically pleasing' code. Thus, I would always use :
for (int i = myArray.Length - 1; i >= 0; i--)
{
// Do something ...
}
You can consider it as the standard way to loop backwards.
Just my two cents...
Source: Stackoverflow.com