I've known of and have been using the std::vector class for about a dozen weeks now, primarily while making my graphics application, and I'm starting to wonder how I ever programmed without it!

For starters, making the file handler for my graphics program has been absolute Hell... specifically because of all the nuances in what the thing should do when you click on certain things, or type in certain file names, or switch your desired file format, etc. etc. But the process of actually creating the list of files from the current working directory was extremely simple, thanks to _stricmp() for sorting and the findfirst() and findnext() functions to get the filenames, but most importantly, the std::vector object that holds the list of filenames and file attributes without having to do messy memory allocation or whatnot.

I've also got std::vector objects holding the brush history, undo history, and bitmap pages.

I've been slowly losing my desire to work with static arrays, which, 12 weeks ago, I was convinced would never happen. As a result, I've been going through the docs for my game engine and the first game I'm going to make with it and altering many of their static-allocated features to be dynamic. (Some of the static-ness is still there, but only where it makes sense to have small, predefined limits.)

The new and delete commands make perfect sense to me now as well, and I haven't touched malloc() or calloc() since PixelShips Retro, though it took over half an hour for me to fix a bug in my graphics program that involved nothing more than changing "BITMAP *bitmap" in a function definition to a "BITMAP *&bitmap"...

...so I guess stupid mistakes are still going to happen...

Anyways, I'm fully confident in using dynamic arrays and std::vector objects now, and it's hard to imagine that I used to program without them not long ago...

--- Kris Asick (Gemini)
--- http://www.pixelships.com

Amen brother.

Don't stop at std::vector. Take a look at STL. STL offers a number of simple algorithms. std::copy, transform, find_max, etc. all make life much simpler.

And then when you're really serious take a look at boost. Boost is doing such a good job that most of the C++0x library changes (ie: the next c++ standard) is coming from the boost libraries. In fact, its the same way that the STL (including std::vector) managed to work its way into C++ everywhere.

You bring back memories of when I first discovered the vector. 90% of all the programming I uses that in one way or another.

std::map is also quite handy in certain cases.

I think I use std::list the most.

Oh, and don't forget std::string. It isn't the best, by far, but with a handy to_string template function life is a breeze.

template<typename T>
std::string to_string(const T &value)
{
  std::ostringstream ret;
  ret << value;
  return ret.str();
}

std::vector is pretty much the only container I ever use. I remember using std::map for a couple of times to store some settings but that's it. It is not that I don't need know else, it's just that all my programs work perfectly fine with vectors

Of cource there are a lot more of those interesting headers. Algorithm and numeric come to my mind first. I suggest to at least read the TOC of SGI STL documentation to get some idea what functionality does STL have.

I very often use STD vector, though occasionally use an array for some things that are small, delicate, and have a defined max size.

Bookmark this link.

Simple example:

// Before
for(vector<string>::iterator itr = strings.begin(); itr != strings.end(); ++itr)
  itr->foobar();

// After
for_each(strings.begin(), strings.end(), mem_fun_ref(&string::foobar));

well billy bob, seeing as how you use boost and you gave a stringstream example you should probably like this:

void log_errno(int yoko)
{
    log_message("Error " + boost::lexical_cast<std::string>(yoko) + ": " + strerror(yoko));
}

If you read the hpp file, you'll notice it uses a stringstream (sstream or the boost implementation based on #defines).

Also, the idea of using for_each and transform has got me thinking about functional programming. That's where i discovered boost lambda (which will be in C++0x).

for_each(a.begin(), a.end(), 
         if_(_1 % 2 == 0)[ cout << _1 ])

Being C++ it isn't half as elegant as python list comprehensions but its pretty good for a start.

Niiice. I don't actually use boost, just the BOOST_FOREACH header. But that's a neat trick anyway.

The path of illumination has opened before you. At the end of the corridor lies a door which says "LISP", which, when you reach it, you can claim reaching the ultimate state of enlightenment as a programmer.

// After after
BOOST_FOREACH(string item, strings)
     item.foobar();

Now make your code go over some arbitrary memory, or how about even a subset of the strings list...

Right. And thats why I use the STL. Boost is mostly crap anyway. This sort of method: boost::lexical_cast should not be using stringstream anyway, thats tons of unnecessary overhead. There are more efficient ways to do that.

Boost is generally lame anyway. Its key "popular" features are just thin wrappers around C++ features.

And come on, macros? I thought we were done with those.

for_each(a.begin(), a.end(), 
         if_(_1 % 2 == 0)[ cout << _1 ])

template<int power, typename Parm>
bool powerOf(Parm p) { return p % power == 0; }

^^ put that in a header somewhere, very reusable.
Now to do ugly lambada crap in a clean way:

copy_if(a.begin(), a.end(), ostream_iterator<int>(cout), PowerOf<2>);

woa i have so much to learn. Is this used in the work place? example a database programing position.

Most of whats is being shown here are just neat tricks that help you stand out from being a good programmer to being a better programmer.

Now regarding the work place it really depends. For a database programming job, chances are you wont need to know anything here. Very rarely is database code done in C++, and if it is, it's going to be abstracted away some how.

.Net, Java etc are languages that you'll find most database jobs use and they wont need any of these clever hacks. Mostly because stuff like this is built into the language, or added in someway.(For each loops are the best example).

Now if you're developing a C++ program in your job, then it could be. However you want to avoid being too fancy with this kind of stuff since it might work nice, but some other people might not understand the code etc. But in the end its not necessary and clean and easy to understand and efficient is more important then using neat tricks to simplify things. In fact depending on the requirements of the project, you might not even be able to do some stuff you would like.

Now if your asking if you need to the STL to code C++ apps, and you better be familiar with STL and not just learning it for the first time when you walk in.

I just said this today, only it was "PHP" instead of "std::vector".

You really want to use different STL containers for different purposes. Look into deque, set, map and list as well, not only vector, and get familiar with them, so you can pick the right thing for the task at hand.

Agreed. The way its implemented is ugly. Lambda functions are really nice though. Your solution is nice but the problem is that you still have to declare something outside the function.

The thing that really irks me about c++ is that you cannot define a function inside of a function. SO you have to make a private member somewhere...

A lot of what i do is program math for applied problems like dt-mri imaging. C++ is sort of the general purpose does all language for me but i'd still love to see more features of a functional language. There are many things that functional languages simply cannot do easily or cleanly enough.

Yeah, but at least its reusable.

if(powerOf<5>(25))
  cout << "25 is a power of 5!\n";

OMG, I had the exact same thing just a week ago.
And again today, while diving into the PHP image functions. Woooo-hoo! It's almost like a full allegro built into the language! Well, the graphics part at least...

Yeah. I'd love something like this:

vector<string> mystrlst;

foreach(mystrlst, lambda(string& s) { cout << s; } );

Generally, lambda functions could be soooo useful; for example, to pass as a callback...
Or php-like:

vector<string> mystrlst;

foreach(mystrlst as s) {
  cout << s;
}

Tobais, that already exists:

vector<string> mystrlist;
std::copy(mystrlist.begin(), mystrlist.end(), ostream_iterator<string>(cout, "item seperator"));

The cout is just an example; my point is that where the cout statement sits, there could be arbitrary code; anything you like.
Something like the lambda thing is possible already, with the minor drawback that you cannot define the function on-the-fly, it must be a function or member function somewhere.
And templates make up for a lot, often allowing for more elegant solutions.

But I do sometimes miss a more convenient iterating mechanism in C++.

WOW, this article got me looking into vectors, I had heard about them before but never understood how to use them, now I'm in the same boat as you and don't know how I got by without them!

I WUB WOOOOUU!!
sorry, read vgcats on vgcats.com to understand.

I remember learning about vectors in my beginning c++ programming class. Long time ago,but they are awsome. Been developing in PHP for five years and I must admit, that was awsome too. I love them both. :-D

Oh my God. I think I'd prefer to write it out as a for loop. You know, so that my eyes don't bleed :-).

Yes but its fukcing blazing fast. That statement will be faster then writing out the for loop yourself!

For the kind of efficiency, thats the cleanest code I've ever seen.

C++ was meant to be fast and elegant, not noobish. Don't mistake the two.

Err... prove it.

Oh, and lets not forget the opposite operation:

vector<string> tokens;
copy(istream_iterator<string>(cin), istream_iterator<string>(), back_inserter(tokens));

A compiler can unroll the loop, as well as a plethora of other tricks.

Really? The compiler has no prior knowledge of the number of elements in mystrlist, so it can't unroll it fully. It can partially unroll it (i.e., execute it in blocks of 8 iterations or whatever using the Duff's device for example), but that can be just as easily done to any for loop.

I'm not saying it won't be faster - maybe it will be. But it's still butt ugly, and I'm not convinced it actually does provide a benefit. Anyway, the point is moot in that case, because the majority of the time will be spent on output to cout.

One sample output wit g++ -O2:Total time to copy 10000000 ints from one vector to other 100 times:
std::copy: 2620000
regular loop: 2870000
</code>Without optimizations:

Total time to copy 10000000 ints from one vector to other 100 times:
std::copy:    2830000
regular loop: 30390000

Satisfied?

Using cout would have been pointless as its overhead would have been way too high for measuring the actual looping process

[edit]
With vectors that fit into cache:
No optimizations:

Total time to copy 100000 ints from one vector to other 10000 times:
std::copy:    320000
regular loop: 29170000

-O2

Total time to copy 100000 ints from one vector to other 10000 times:
std::copy:    350000
regular loop: 490000

Use iterators

cgames@ryan ~ $ g++ test.cpp -O3 -funroll-loops
cgames@ryan ~ $ ./a.out 
Total time to copy 100000 ints from one vector to other 10000 times:
std::copy:     690000
regular loop:  970000
iterator loop: 900000

Okay, so it's faster, and by a fair margin, but why?

[edit]
While loop is faster

Here is the loop I had in mind:

for(int i=0;i<LOOPS;i++)
  for(it1 = intvec1.begin(), it2 = intvec3.begin(); it1 != intvec1.end(); it1++, it2++)
    (*it2) = (*it1);

With regular loop changed to that, and -O2:

Negligible 1.5% difference.

Anyway, I was just playing - if there is a good way to use <algorithm> by all means, you should use it.

But it's not all that important if the loop version will be more readable. This is not so in the case of std::copy, which is very straight-forward. But in the case of algorithms that require you to define a function (which will often be used only this once), it's not worth the hassle. Not unless we get lambda functions in C++.

Here's a silly.

$ g++ test.cpp -O3 -funroll-loops && power ./a.out 
Total time to copy 10000 ints from one list to other 100000 times:
std::copy:     7220000
iterator loop: 6930000

<hypothesis>It seems copy is doing a memcpy internally, overridden for vectors. When it can't do so and must use a generic copy function, the overhead of the method pointers causes it to be slower.</hypothesis>

Put all together and ran on my Core2 at 32bit:

#g++ std_copy.cpp -O3 -funroll-loops && ./a.out

Total time to copy 100000 ints from one vector to other 10000 times:
std::copy:     390000
regular loop:  550000
iterator loop: 580000
Jakub's loop:  560000

I ran it several times and there weren't much changes.

Different CPU's might give different results.

You have a fast machine, HoHo What clock/cache?

I'm running a Core Duo at 3.0 GHz with I think 4 MB cache between the cores.

Core2Duo e4300@2.93GHz at the moment. That means 2M L2 shared between two cores and ~62% OC. Could go higher when I could somehow give it more than default voltage
Your last code with -O3 -funroll-loops gave me this:

Total time to copy 10000 ints from one list to other 100000 times:
std::copy:     1480000
iterator loop: 1520000

When I changed list to vector then iterator loop actually got faster than std::copy

Total time to copy 10000 ints from one vector to other 100000 times:
std::copy:     480000
iterator loop: 430000

Well, all I can say is when in doubt, benchmark
Also please note the speed difference between lists and vectors.

Yeah lists are bloated and are almost completely useless because of it. They're more useful for academic purposes then anything else.

Hm, lists have faster insertions that vectors. You can remove elements in constant time. If you sort a list of MyClass (using list::sort), it could seriously outperform std::sort on vector, because it doesn't need to copy actual data, just rearrange the pointers.
However, iterating through a list is slower, because vector uses a random_iterator.

Each STL container has its strenghts and weaknesses. Sometimes it might even be more efficient to use one type for one task, and then copy the data to a different container to do something else with the data.

For example, std::set is blazing fast to get you unique, sorted data. If you needed a lot of random access on the data later, you might copy it to a vector before continuing. (Benchmark, of course.)

***

By the way, they say that the container's "native" methods could be faster than the equivalent std::algorithm (optimized for this particular container). Anybody care to benchmark operator = ?

If the vector doesn't need to be sorted you can add and remove stuff from there in constant time too.

That depends on how you use it. If you have enormous list then iterating it over and over again will probably take more time than with vectors (need benchmarks!). If you don't keep pointers in the container and the elements are big then lists may win.

I agree. Though if you can alter your design just a little you may find that vectors perform better than lists for most things. Also in some cases deque may be a bit better than vector.

Last time I used lists was about three years ago in uni when we were asked to write a list class

That's a big "if". And a vector may get copied using push_back(). And if you wanted to keep the container sorted, a multiset would probably be fastest.

List can win clearly, if the copy constructor is expensive. For example when sorting std::strings.

Yes, a vector is a most general use container, because very often random access is what you need (replacement to single array). However, it is impossible to design a container that works remarkably well for all purposes, because you need a different structure for each purpose. Knowing the tools is good, also STL is designed in a way, that it is relatively easy to switch the container you are using and to move data to a different container.

I can also see how implementing your own list deters you from using std::list

Not if it is a compliant STL implementation and you have already reserved enough slots for your data set (two conditions which are easily satisfied).

Of course, vectors can easily win if you don't sort the actual array contents (you generate an sorted index->actual index mapping that happens to return items in sorted order). Completely avoids copy constructor overhead. Granted, this is not what is done in any STL container as far as I know, but it is possible to sort a vector-like container with zero data copies of the actual container data this way... (it would be interesting though to have an STL wrapper object that does just this for all random access data types; call it something like sorted_wrapper.)

For copy-expensive objects, you can sort a vector of pointers to the object. Although it is still questionable if it is worth the effort if list can do this without any extra work.
(I created an expensive class consisting of two ints and a string containing "Hello world", and overloaded comparison to sort it based on one of the randomly initialized ints. Then I sorted a vector of these objects, a vector of pointers and a list (identical data to the first vector). The results: sorting pointers ~3 x faster than first vector, sorting list ~5-6 x faster than a regular vector.)

Your idea is interesting, but wouldn't it produce massive overhead - no less than a list? Also, after sorting, wouldn't you still need to do the copying in one go (adds at least O(N) and seems tricky to do in-place)?

Anyway, I'm not saying list is better than vector per se (or the other way round). But a simple contiguous block of memory just doesn't suit well for all kinds of manipulations. Nor does any other data structure. So you have to make choices.

Finally, here's a link to compare the effectiveness of some operations with different containers. (Keeping in mind that O(N) can mean very different things with different containers.)

The rest of the site is interesting reading too!

...and after all, keep in mind that STL containers are designed to use the same interface wherever possible, so if all is well, changing the container type for a given application later on shouldn't be too much of a problem. Just profile them against each other and see what's faster.