• Advertisement
Sign in to follow this  

So, std::vector is...??

This topic is 2769 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

What is this, exactly? How is it coded internally (seeing as how Microsoft likes to wrap everything into a DLL or LIB...)? How is it used? Why is it needed? Why is it called a vector? I'm assuming that it does not have coordinates somewhere in the class? **Insert any other questions I'm forgetting to ask...**

I started programming 25 years ago when I was 8 years old. I first heard about this thing a month or two ago. It seems to have taken the programming world by storm, so I'd like to know as many details as possible.

Share this post


Link to post
Share on other sites
Advertisement
Quote:
What is this, exactly?
A vector is a dynamically sized array that grows with the number of elements you insert into it, and is built to behave as close to a raw array as possible.

Quote:
How is it coded internally?
Templates. Because the STL containers are coded as templates, they themselves cannot be ported to a lib or dll. However, specific instantiations of these containers, such as ostream<char, type_traits<char>> for cout, clog, and cerr have been moved to the Visual Studio's C-runtime library.

Quote:
How is it used?
C++ Reference on vector for samples and usage.

Quote:
Why is it needed?
It is needed because programmers find themselves needing an array whose size is unknown or whose size is not known at compile time.

Share this post


Link to post
Share on other sites
std::vector is not made by microsoft. It is part of the standard of C++ I believe found in the Standard Template Library and you are most likely to find it in the includes of your compiler. The vector is a sizable container. It is similar in works to a dynamic array class that provides an interface to add, subtract, and change it's objects.

Normally, if you declared a dynamic array with a pointer and allocated it's memory, in order to change it's size, you would have to delete the current array and allocate more or less memory for it. The vector does that for you.

Share this post


Link to post
Share on other sites
Quote:
Original post by boogyman19946
std::vector is not made by microsoft.


Yes, I know. My point was that Microsoft hides the code to any and all internal C/C++ ANSI and other standards in DLLs and LIBs. This means I would need to understand x86 assembly (which I don't) to see how these are implemented internally. Compilers used to provide the code along with the libraries.


Quote:
Original post by boogyman19946The vector is a sizable container. It is similar in works to a dynamic array class that provides an interface to add, subtract, and change it's objects.

Normally, if you declared a dynamic array with a pointer and allocated it's memory, in order to change it's size, you would have to delete the current array and allocate more or less memory for it. The vector does that for you.


So it can replace linked lists?

Share this post


Link to post
Share on other sites
The main difference between a linked list and a vector is that a linked list supports insertion of objects at unusual indexing. A vector still must enter it's objects at either the front or the end of it's indexing. If you do not need to have objects in a certain order, vector is the way to go, if you do, linked list is asking for use.

Share this post


Link to post
Share on other sites
Quote:
Original post by maspeir
So it can replace linked lists?


It could. It depends on what you're looking for. Can you be limited to sequential access, and are you looking for fast insertion and deletions? If you are, then go with std::list. Do you need random accessing of elements? If you are, then go with std::vector. Do you need quick look up of an arbitrary element? If so, then go with std::set or std::map.

Share this post


Link to post
Share on other sites
Quote:
Original post by maspeir
Quote:
Original post by boogyman19946
std::vector is not made by microsoft.


Yes, I know. My point was that Microsoft hides the code to any and all internal C/C++ ANSI and other standards in DLLs and LIBs. This means I would need to understand x86 assembly (which I don't) to see how these are implemented internally. Compilers used to provide the code along with the libraries.


Being a templated type, they physically can't hide this code from you, it's all inside the vector header file.
I also seem to have all of the source code to the standard libs with the full version of Visual Studio. The express editions definately hide it from you though when they can.

Share this post


Link to post
Share on other sites
Quote:
Original post by maspeir
What is this, exactly?

It's a dynamic array.

Quote:
How is it coded internally (seeing as how Microsoft likes to wrap everything into a DLL or LIB...)?

It has a pointer to the data, a number of elements that the block of data can hold and a number of elements actually being used.

Quote:
How is it used? Why is it needed?

It's a container that has very fast access to an element by index, you can quickly add or remove elements at the end. It basically behaves like an array, but you can change its size dynamically. I find myself using it all the time.

Quote:
Why is it called a vector? I'm assuming that it does not have coordinates somewhere in the class?

vector is just a bad name. They called it that because (3,1,5) is a 3D vector, so they call an arbitrary finite sequence a vector. For it these sequences to be vectors (by the mathematical definition) you should be able to add them, subtract them and scale them.

Quote:
I started programming 25 years ago when I was 8 years old.

Me too (give or take one year).

Quote:
I first heard about this thing a month or two ago. It seems to have taken the programming world by storm, so I'd like to know as many details as possible.

Have you heard of abstract data types? vector has been around for a long time. And you probably have implemented something similar at one point or another.

If you still don't see the point, I'll try to come up with a couple of examples where you may want to use one.

Share this post


Link to post
Share on other sites
Quote:
Yes, I know. My point was that Microsoft hides the code to any and all internal C/C++ ANSI and other standards in DLLs and LIBs. This means I would need to understand x86 assembly (which I don't) to see how these are implemented internally. Compilers used to provide the code along with the libraries.
vector is a class template, so the code should be available. (In VC++, you can just right-click on #include <vector> and open the file.)

However, you may not get that much out of looking at the source code, as SC++L containers and algorithms code is often pretty difficult to read. (This is partially due to the general conventions that tend to be used, but also specifically due to the liberal use of leading underscores to avoid symbol conflicts.)
Quote:
So it can replace linked lists?
As noted previously, the SC++L includes a variety of container types (vector, deque, list, map, set, etc.), so there are plenty of container types to choose from. (In other words, vector doesn't really replace linked lists; if it were to be said to replace anything, it would be 'raw' dynamically allocated arrays.)

Share this post


Link to post
Share on other sites
Quote:
Original post by maspeir

Yes, I know. My point was that Microsoft hides the code to any and all internal C/C++ ANSI and other standards in DLLs and LIBs. This means I would need to understand x86 assembly (which I don't) to see how these are implemented internally. Compilers used to provide the code along with the libraries.

STL is completely templated, which means every compiler delivers full source code - it's all headers. Including Microsoft's.

Quote:
So it can replace linked lists?


No, it's a different kind of container, sort of the opposite of linked list, what is expensive in linked list is cheap with vector and vice versa.

Share this post


Link to post
Share on other sites
Thanks for the info, everyone! Go easy on me! I am a self-taught C programmer (hobbyist, not professional) that has stayed away from C++ like it was a plague. These are rather new concepts for me.

I like the fact that the hard work of memory management seems to be done for me AND standardized!

Share this post


Link to post
Share on other sites
C++ is just an extension to C so there really is no reason not to use it really :D You pick what you like to use and leave the rest to C. I've seen a post once where Linus Torvalds was bashing C++ in favor of C. >.> ahh here is the link:

Linus vs. C++

I thought it was just amusing to read :D

Share this post


Link to post
Share on other sites
Quote:
Original post by boogyman19946
C++ is just an extension to C so there really is no reason not to use it really :D You pick what you like to use and leave the rest to C. I've seen a post once where Linus Torvalds was bashing C++ in favor of C. >.> ahh here is the link:

Linus vs. C++

I thought it was just amusing to read :D


While I agree with him for the most part, his post seemed rather shallow and not backed up by much. It would have been nice to see some references backing up his assertions.

I'm learning C++ mostly due to peer pressure. It is hard to ask a question around here without getting slapped in the face with C++. I still don't like it (read: HATE it!), but it is the direction the world is moving, so...

Share this post


Link to post
Share on other sites
Quote:
Original post by maspeir
Quote:
Original post by boogyman19946
C++ is just an extension to C so there really is no reason not to use it really :D You pick what you like to use and leave the rest to C. I've seen a post once where Linus Torvalds was bashing C++ in favor of C. >.> ahh here is the link:

Linus vs. C++

I thought it was just amusing to read :D


While I agree with him for the most part, his post seemed rather shallow and not backed up by much. It would have been nice to see some references backing up his assertions.

I'm learning C++ mostly due to peer pressure. It is hard to ask a question around here without getting slapped in the face with C++. I still don't like it (read: HATE it!), but it is the direction the world is moving, so...


haha, Here is the reference ^.^ :

Stroustrup claims C++ is a joke

heh, I have never had a greater laugh in my life XD The man is a genius.

Share this post


Link to post
Share on other sites
Whenever you see somebody write a response with that level of vitriol, you know that their words are based more in emotion than reason. There's a certain small kernel of truth to what he's saying, but I think the only thing you need to read from that rant is this:
Quote:
C++ leads to really really bad design choices.

No, C++ doesn't lead to bad design choices--your inability to use it well does. The design is governed by the programmer, not the language. Unfortunately, there's a huge number of programmers out there who don't know how to use it well because, frankly, C++ is harder to use well (or rather, easier to use poorly) than C.

C'est la vie.

To the OP: I recommend really diving into the theory behind templates and generic (meta)programming in C++ before ever using anything that requires you to type '<>'. Like Linus is ranting about, it can be very easy to misuse, and many compilers will allow you to do things that you shouldn't be able to do, so it's very very useful to have a good theoretical and functional understanding about what's going on behind the scenes before you even touch it.

Share this post


Link to post
Share on other sites
Quote:
Original post by Antheus
Quote:
So it can replace linked lists?


No, it's a different kind of container, sort of the opposite of linked list, what is expensive in linked list is cheap with vector and vice versa.


std::list replaces linked lists, std::vector is a dynamic array: guarantee that elements appear contiguously in memory.

std::vector is the functional equivalent of a C array that gets realloc'd whenever it's full. The default growth policy of std::vector is that whenever it's realloc'd it consumes double the memory (i think that's right...). So if it's 4 elements long and you push_back a 5th element it will realloc to have a new max capacity of 8 elements.

There are many caveats with vector so it's good to really know how it operates, which you can generally learn just by googling "stl vector". For instance, removing the last element is constant time, but removing a middle element requires basically a memcpy of all subsequent elements one slot up. So if ordering is not important std::swap the current element with the last and do a pop_back(). If ordering is important and you're frequently removing interstitial elements, std::vector is obviously not the correct data structure, std::list is likely more appropriate.

The STL provides implementations of a WHOLE LOT of algorithms: queue, map, stack, vector, list to name a few. It is obviously important that you really know your data structure performance characteristics before choosing one.

-me

Share this post


Link to post
Share on other sites
Quote:
Original post by alvaro
vector is just a bad name. They called it that because (3,1,5) is a 3D vector, so they call an arbitrary finite sequence a vector. For it these sequences to be vectors (by the mathematical definition) you should be able to add them, subtract them and scale them.
Vector is a perfectly good name. It's related to vector processing and other computer science-y things, and has nothing to do with 3D vectors... well, I guess they're like 3rd cousins or something.

EDIT: Oh, I see what you mean. Nevermind.

Share this post


Link to post
Share on other sites
Quote:
Original post by Palidine
std::vector is the functional equivalent of a C array that gets realloc'd whenever it's full. The default growth policy of std::vector is that whenever it's realloc'd it consumes double the memory (i think that's right...).

Exact growth characteristics are unspecified so long as push_back() is amortized constant. I've seen implementations with growth ratios anywhere from 1.5 to 3.

Share this post


Link to post
Share on other sites
Quote:
Original post by Daaark
Quote:
Original post by boogyman19946

haha, Here is the reference ^.^ :

Stroustrup claims C++ is a joke

heh, I have never had a greater laugh in my life XD The man is a genius.
Is that real? Seems made up. But hilarious anyways.


http://www2.research.att.com/~bs/bs_faq.html#IEEE

Share this post


Link to post
Share on other sites
Quote:
Original post by Daaark
Quote:
Original post by boogyman19946

haha, Here is the reference ^.^ :

Stroustrup claims C++ is a joke

heh, I have never had a greater laugh in my life XD The man is a genius.
Is that real? Seems made up. But hilarious anyways.


It's a very funny fake.

Share this post


Link to post
Share on other sites
Hehe, I wasn't sure if it was really a fake, but I doubt someone would spend that much time to create a new language just as a joke. Even more ridiculous, write a book that's thicker than bible about it.

Share this post


Link to post
Share on other sites
Quote:
Original post by Antheus
Quote:
Original post by maspeir

Yes, I know. My point was that Microsoft hides the code to any and all internal C/C++ ANSI and other standards in DLLs and LIBs. This means I would need to understand x86 assembly (which I don't) to see how these are implemented internally. Compilers used to provide the code along with the libraries.

STL is completely templated, which means every compiler delivers full source code - it's all headers. Including Microsoft's.
There is much more to the code than just the templated bits. Microsoft ships the entirety of the code with Visual Studio, which means you can debug into both the C and C++ runtimes.

Share this post


Link to post
Share on other sites
Quote:
Original post by boogyman19946
Hehe, I wasn't sure if it was really a fake, but I doubt someone would spend that much time to create a new language just as a joke. Even more ridiculous, write a book that's thicker than bible about it.
It was obviously a joke, but it could have been a real interview where Bjarne was just having some fun. Stranger things have happened.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement