Computer Science Canada

[C++] Don't use arrays in C++!
Author:  wtd [ Sat Dec 18, 2004 3:02 pm ]
Post subject:  [C++] Don't use arrays in C++!
But... don't you tell us to use arrays?

Yes, in Turing, and other languages, where arrays are either well-implemented, or there's simply no decent alternative.

C++ has a better alternative

The vector class in the Standard Template Library provides a more flexible, powerful alternative to using arrays.

Whoa, whoa, whoa... what's the Standard Template Library?

The STL is a collection of classes and functions which revolve around the C++ concept of templates, whereby we can create types and functions which operate on many types of data, without immediately specifying those types, or writing separate classes or functions for every type.

Don't worry, GCC includes an implementation of the STL, as do most other compilers these days. Visual C++ 6.0, it should be noted, has an implementation of it, but that implementation is quite bad. If you use this compiler, you may be led to believe the STL is a bad thing, when it's really the compiler at fault.

A simple template class

Now, we could write the following trivial code:

code:
#include <string>
#include <iostream>

class int_math
{
   private:
      int original;
   public:
      int_math(int original_) : original(original_) { }
      int add(int other) const { return original + other; }
      int value() const { return original; }
};

class double_math
{
   private:
      double original;
   public:
      double_math(double original_) : original(original_) { }
      double add(double other) const { return original + other; }
      double value() const { return original; }
};

int main()
{
   int_math a(8);
   double_math b(7.0);

   std::cout << a.add(5)
             << std::endl
             << b.add(41.3)
             << std::endl;

   return 0;
}


But, we should notice that we're duplicating a lot of code and this is a bad thing in programming, when it can be avoided. Fortunately C++ gives us a way to avoid code duplication in this instance.

code:
#include <string>
#include <iostream>

template <typename _t>
class math
{
   private:
      _t original;
   public:
      math(_t original_) : original(original_) { }
      _t add(_t other) const { return original + other; }
      _t value() const { return original; }
};

int main()
{
   math<int> a(8);
   math<double> b(7.0);

   std::cout << a.add(5)
             << std::endl
             << b.add(41.3)
             << std::endl;

   return 0;
};


Back to why arrays are bad

So, why are arrays bad, you ask. Well, reason number one is that they do not keep track of their own size. We have to do it manually, and that's just asking for trouble.

Consider an example where we want to ask for series of grades and find the average of them. We might get as many as ten, but we might get less, so we have to keep track of the number input.

code:
#include <iostream>

int main()
{
   int grades[10];
   int num_grades = 0;
   char answer = 'y';

   while (answer == 'y')
   {
      std::cin >> grades[num_grades];
      num_grades++;

      do
      {
         std::cout << "Enter another? ";
         std::cin >> answer;
      } while (!(answer == 'y' || answer == 'n'));
   }

   int sum = 0;

   for (int i = 0; int i < num_grades; i++)
   {
      sum += grades[i];
   }

   std::cout << "Average grade: " 
             << (sum / num_grades)
             << std::endl;

   return 0;
}


Now, let's look at the same example, using std::vector.

code:
#include <iostream>
#include <vector>

int main()
{
   std::vector<int> grades;
   char answer = 'y';

   while (answer == 'y')
   {
      int temp_grade;
      std::cin >> temp_grade;
      grades.push_back(temp_grade);

      do
      {
         std::cout << "Enter another? ";
         std::cin >> answer;
      } while (!(answer == 'y' || answer == 'n'));
   }

   int sum = 0;

   for (std::vector<int>::iterator i(grades.begin()); i != grades.end(); i++)
   {
      sum += *i;
   }

   std::cout << "Average grade: "
             << (sum / grades.size())
             << std::endl;
   return 0;
}


The important bits are:

code:
grades.push_back(temp_grade)


And:

code:
grades.size()


The first adds a new element (in this case a grade) onto the end of the vector. The second line grabs the size of the vector. The std::vector is just a class, so getting the size of one is as simple as calling a member function. Smile

Since std::vector is a class...

Of course, now that we've said that std::vector is just a class, this means we could implement a lot of features by simply subclassing std::vector.

code:
#include <iostream>
#include <vector>

class grades_collection : public std::vector<int>
{
   public:
      int sum()
      {
                 int sum = 0;

         for (iterator i(begin()); i != end(); i++)
         {
                sum += *i;
             }

             return sum;
      }

      int average()
      {
                 return sum() / size();
          }
};

int main()
{
   grades_collection grades;
   char answer = 'y';

   while (answer == 'y')
   {
      int temp_grade;
      std::cin >> temp_grade;
      grades.push_back(temp_grade);

      do
      {
         std::cout << "Enter another? ";
         std::cin >> answer;
      } while (!(answer == 'y' || answer == 'n'));
   }

   std::cout << "Average grade: "
             << grades.average()
             << std::endl;
   return 0;
}


Make it even simpler

We could simplify this even further by declaring a friend function which gets input and puts it into the vector.

code:
#include <iostream>
#include <vector>

class grades_collection : public std::vector<int>
{
   public:
      int sum()
      {
                 int sum = 0;

         for (iterator i(begin()); i != end(); i++)
         {
                sum += *i;
             }

             return sum;
      }

      int average()
      {
                 return sum() / size();
          }

          friend std::istream& operator>>(std::istream& in, grades_collection& g);
};

std::istream& operator>>(std::istream& in, grades_collection& g)
{
   int temp_grade;
   in >> temp_grade;
   g.push_back(temp_grade);
   return in;
}

int main()
{
   grades_collection grades;
   char answer = 'y';

   while (answer == 'y')
   {
      std::cin >> grades;

      do
      {
         std::cout << "Enter another? ";
         std::cin >> answer;
      } while (!(answer == 'y' || answer == 'n'));
   }

   std::cout << "Average grade: "
             << grades.average()
             << std::endl;
   return 0;
}


In Summary

There's more to come, but for now, we've seen that vectors offer a distinct advantage by knowing their own size.

We've also seen that their object-oriented nature makes it trivial to extend them, and this ability can make dealing with them much simpler.
Author:  md [ Sun Dec 19, 2004 2:42 pm ]
Post subject: 
Hmm, I've never used vectors, but I can see how they might be more useful than arrays. The only problem might be when you need to say quickly insert lots of data into the array. As I don't know how the vector class works I can't be sure, but it looks like it might need to allocate more memory when you add something, which is quite slow.

Is this actually the case, or are vectors on par speed wise with arrays?
Author:  wtd [ Sun Dec 19, 2004 9:13 pm ]
Post subject: 
Vectors do automatically resize if you add more items than they can currently hold. Depending on the implementation of the STL that you're using, this can be pretty darn efficient.

One hint, though is that the std::vector constructor takes a number of items to hold.

code:
std::vector<int> grades(10);


Will create a vector called grades which can hold 10 integers. It can be resized later, of course, like any other vector, but if you don't exceed that number, it won't resize.
Author:  md [ Sun Dec 19, 2004 9:56 pm ]
Post subject: 
Cool! And how do the iterators compare speed-wise? Obviously they arn't as fast as i++, but are they close?
Author:  wtd [ Sun Dec 19, 2004 10:05 pm ]
Post subject: 
Cornflake wrote:
Cool! And how do the iterators compare speed-wise? Obviously they arn't as fast as i++, but are they close?


They're pretty much as fast. For anything but the absolute most critical system, where you're counting memory usage in bytes, you won't notice a difference.

Additionally, iterators are really cool.

How would you copy one array into another?

code:
int main()
{
   int foo[10], bar[10];

   for (int i = 0; i < 10; i++)
   {
      bar[i] = foo[i];
   }

   return 0;
}


Well, that's tedious.

How would you copy one vector into another?

code:
#include <vector>
#include <algorithm>

int main()
{
   std::vector<int> foo(10), bar(10);

   std::copy(foo.begin(), foo.end(), bar.begin());

   return 0;
}


Of course...

The copy function in the STL algorithm header is quite useful, because it can work on arrays too.

code:
#include <algorithm>

int main()
{
   int foo[10], bar[10];

   std::copy(foo, foo + 10, bar);

   return 0;
}
Author:  Martin [ Sat Apr 16, 2005 12:32 pm ]
Post subject: 
++i is faster than i++
Author:  rizzix [ Sat Apr 16, 2005 1:13 pm ]
Post subject: 
NO it isin't.. ++i increments the value and returns the incremnted value..

while i++ retuns the current value then increments it
Author:  wtd [ Sat Apr 16, 2005 1:48 pm ]
Post subject: 
If you don't care about the return value, though, the prefix form is generally a bit faster. Both forms of the decrement operator offer the same performance.
Author:  rizzix [ Sat Apr 16, 2005 1:54 pm ]
Post subject: 
yes but in a for loop using ++i skips the initial value... or maybe not.
Author:  wtd [ Sat Apr 16, 2005 1:57 pm ]
Post subject: 
code:
for (int i = 0; i < n; ++i) { ... }


Is identical in behavior to:

code:
for (int i = 0; i < n; i++) { ... }
Author:  rizzix [ Sat Apr 16, 2005 2:08 pm ]
Post subject: 
so i guess there's no optimisation there. Razz
Author:  wtd [ Sat Apr 16, 2005 2:45 pm ]
Post subject: 
Wrong, but thank you for playing our game.

Just because they behave the same way as far as we're concerned in this case doesn't mean they do the same thing at the machine level. Even though we don't use it, "i++" still makes a copy and returns it.
Author:  rizzix [ Sat Apr 16, 2005 3:18 pm ]
Post subject: 
huh? y does it have to be that way?

what the compiler could do is return the current value and then increment the value in register. no need to return copys..

thats how Java handles it anyways.. i assumed it would be the same. my mistake.Embarassed although I think this is compiler dependent unless i'm mistaken again and the C++ languages it self enforces a copy returned... (which is just plain stupid imo)
Author:  Justin_ [ Wed Aug 16, 2006 3:35 pm ]
Post subject: 
What is the best way to get the integer value that represents the end of the vector?

I'm trying to do this:

c++:

vectorID[vectorID.end()].I_NEED_AN_INT();


What I have now is an iteration through the vector while keeping a count on it, then when it reaches end I'll have the integer representation of the end of the vector.
Author:  wtd [ Wed Aug 16, 2006 5:41 pm ]
Post subject: 
You wish to retrieve the last element of a vector (that happens in this case to store ints)?
Author:  Justin_ [ Wed Aug 16, 2006 6:10 pm ]
Post subject: 
Actually the label was just to emphasize that I need an int instead of an iterator in the [] operator. My actual program implements a vector of objects. Currently I am accessing individual elements in the array by counting the iteratations and supplying the intended integer value.

I hope there is a very efficient way to do it cause so far vectors have just made things more complicated and I haven't seen an advantage to them (cause i kinda like arrays).
Author:  jernst [ Mon Apr 21, 2008 9:58 am ]
Post subject:  Re: [C++] Don't use arrays in C++!
nice tutorial Smile making use of it right now for some work Very Happy
Author:  avok23 [ Mon May 05, 2008 6:03 pm ]
Post subject:  RE:[C++] Don\'t use arrays in C++!
Vectors are performance hogs. i'll rather advise u use lists or make your custom data struct. and this topics should be name "An alternate to arrays/struct/etc.."

case there is nothing wrong with this data types. arrays grant u high performan and if u ever work on a small system u have no choice yuo MUST use them. you can not go about enforcing your coding style like its some gospel you can only enlighten people to its ups and downs. please people keep an open mind and if in doubt use all available alternates.

and ++i is faster than i++.
Author:  md [ Mon May 05, 2008 8:50 pm ]
Post subject:  Re: RE:[C++] Don\'t use arrays in C++!
avok23 @ 2008-05-05, 6:03 pm wrote:
Vectors are performance hogs. i'll rather advise u use lists or make your custom data struct. and this topics should be name "An alternate to arrays/struct/etc.."

case there is nothing wrong with this data types. arrays grant u high performan and if u ever work on a small system u have no choice yuo MUST use them. you can not go about enforcing your coding style like its some gospel you can only enlighten people to its ups and downs. please people keep an open mind and if in doubt use all available alternates.

and ++i is faster than i++.


Methinks your information is wrong... since vectors and lists are both collections are are based on the same code structures... both are equally fast (or slow as the case may be). Vectors could theoretically be made even faster then lists because they are less generic. Yes you could write your own class and data structures - and you may be able to tailor it to your specific needs slightly better then the STL, but you the STL is still pretty damned fast.

Also, any compiler worth it's salt will generate the same code for ++i and i++ if they are on their own. Heck, even if they don't it works out to basically the same assembly anyways. Perhaps one instruction more.
Author:  StealthArcher [ Mon May 05, 2008 9:33 pm ]
Post subject:  Re: [C++] Don't use arrays in C++!
Seeing his post I decided to run some benchmarks:

On the GCC Compiler:
On Codeblocks (for timing):
Using a for loop, with one instruction, number output, tested to 2000000:
t++ took an average of 103 seconds to complete.
++t took an average of 109.

Confused Either I'm doing something wrong, or your info is indeed incorrect.
Author:  md [ Tue May 06, 2008 10:49 am ]
Post subject:  Re: [C++] Don't use arrays in C++!
First; Test Code:
c++:

#include <iostream>
#include <ctime>

const unsigned long TIMES = 100;
const unsigned long LOOPS = 2000000000;

int main( int argc, char** argv)
{

        clock_t start, end, dif;
        double total, avg;
        unsigned long i = 0, j = 0;
       
        std::cout << "++i, test, 1 to " << LOOPS << "; " << TIMES << " times (++j)" << std::endl;
        avg = 0;
        total = 0;
        while( j < TIMES )
        {
                start = clock();
                while( i < LOOPS )
                        ++i;
                end = clock();
                ++j;
               
                dif = end - start;
                total += dif;
        }
        std::cout << "Time: " << total << " Avg: " << (total / TIMES) << std::endl;
        std::cout << "i = " << i << " j = " << j << std::endl;

        i = 0; j = 0;
        std::cout << "i++, test, 1 to " << LOOPS << "; " << TIMES << " times (j++)" << std::endl;
        avg = 0;
        total = 0;
        while( j < TIMES )
        {
                start = clock();
                while( i < LOOPS )
                        i++;
                end = clock();
                j++;
               
                dif = end - start;
                total += dif;
        }
        std::cout << "Time: " << total << " Avg: " << (total / TIMES) << std::endl;
        std::cout << "i = " << i << " j = " << j << std::endl;
}


Compiling and running:
code:
[john@arkady Projects]$ g++ test.cpp
[john@arkady Projects]$ ./a.out
++i, test, 1 to 2000000000; 100 times (++j)
Time: 9.74e+06 Avg: 97400
i = 2000000000 j = 100
i++, test, 1 to 2000000000; 100 times (j++)
Time: 9.49e+06 Avg: 94900
i = 2000000000 j = 100
[john@arkady Projects]$



Now, with optimization:
code:
[john@arkady Projects]$ g++ -O3 test.cpp
[john@arkady Projects]$ ./a.out
++i, test, 1 to 2000000000; 100 times (++j)
Time: 0 Avg: 0
i = 2000000000 j = 100
i++, test, 1 to 2000000000; 100 times (j++)
Time: 0 Avg: 0
i = 2000000000 j = 100
[john@arkady Projects]$ g++ -O2 test.cpp
[john@arkady Projects]$ ./a.out
++i, test, 1 to 2000000000; 100 times (++j)
Time: 0 Avg: 0
i = 2000000000 j = 100
i++, test, 1 to 2000000000; 100 times (j++)
Time: 0 Avg: 0
i = 2000000000 j = 100
[john@arkady Projects]$


Clearly the compiler can optimize away such a trivial example - and that at least on this computer and with this particular build/version of g++ i++ is faster (trivially so... since iirc CLOCKS_PER_SEC is 1000).

Oh, and g++ version:
code:
[john@arkady Projects]$ g++ -v
Using built-in specs.
Target: i686-pc-linux-gnu
Configured with: ../configure --prefix=/usr --enable-shared --enable-languages=c,c++,fortran,objc,obj-c++,treelang --enable-threads=posix --mandir=/usr/share/man --enable-__cxa_atexit --disable-multilib --libdir=/usr/lib --libexecdir=/usr/lib --enable-clocale=gnu --disable-libstdcxx-pch --with-tune=generic
Thread model: posix
gcc version 4.3.0 (GCC)
Author:  btiffin [ Tue May 06, 2008 12:40 pm ]
Post subject:  Re: [C++] Don't use arrays in C++!
Re; ++ and which is faster;

Don't forget. gcc has the ever so teachable -S option. Try it with both post and pre increment. You'll see exactly what the compiler and optimizer are up to at the assembler level. diff -y on the .s files to get a quick grok of deltas. Not many when it comes to integral data types. Smile The issue really comes to rise when objects are involved and with operator++ overloading.

And for some technical details check out http://en.allexperts.com/q/C-1040/Increment-operators.htm

Cheers
Author:  Analysis Mode [ Tue Feb 24, 2009 11:22 pm ]
Post subject:  Re: [C++] Don't use arrays in C++!
if you have two arrays a1 and a2 and you want to copy from a1 into a2:

memcpy(a2,a1,sizeof a1);

you can do this with other data strucutres likes a deque to vector, etc.

and vectors are slower than arrays (i.e. adjacency lists compared to adjacency matrices).
Author:  DemonWasp [ Wed Feb 25, 2009 1:27 am ]
Post subject:  RE:[C++] Don\'t use arrays in C++!
You can't really compare a Vector with an array. One does a whole lot more than another with regards to bounds-checking (among other things) than the other does. You have to compare the utility of the faster result versus the utility of faster / easier / cheaper maintenance and modification, which is a lot harder than invoking your executable with time in front. In most areas, it should be obvious which one you want.

Pre-increment and post-increment can be compiled out when you have an integer incrementing, but C++ allows you to overload operators, and as I recall, iterators overload ++. However, the way that the function works for myIterator++ involves at least one, possibly dozens, of object-creations and copies, which is a lot slower than ++myIterator, which does nothing of the sort (and unfortunately, the compiler can't really do a whole lot about this).

Mixing C and C++ works out well for performance, but is awful for cross-platform compatability and maintenance. Unless you KNOW you need the performance, use one or the other but not both. Remember: premature optimisation is the root of much (if perhaps not all) evil.
Author:  Briggs [ Wed Feb 25, 2009 6:05 pm ]
Post subject:  RE:[C++] Don\'t use arrays in C++!
If you want to use pointers, though, then arrays are the way to go. I'll just put that bit in.
Author:  btiffin [ Wed Feb 25, 2009 9:32 pm ]
Post subject:  Re: [C++] Don't use arrays in C++!
Just old guy rambling, having encountered a meme
Quote:
"We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil." - Donald Knuth

Followed closely by
Quote:
"Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it." -Brian Kernighan

and then one of mine
Quote:
"Those that can, do. Those that can't teach, write documentation."

Cheers
Author:  Dark [ Thu Feb 26, 2009 9:35 pm ]
Post subject:  RE:[C++] Don\'t use arrays in C++!
hmm I'll try this, ty

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy