New Topic/Question
Reply
What Data Structure does a vector use?
Does it use an Array that increases its size when it runs out of space?
Does it use a Linked List?
Does it use a Stack?
I am talking about the vector that you get when you do
#include <vector>
6 Replies - 224 Views - Last Post: 07 January 2013 - 05:42 AM
Rate Topic:
#1
qkrtjdwls91
- New D.I.C Head
Reputation: 2
- Posts: 15
- Joined: 19-December 12
What Data Structure does a vector use?
Posted 05 January 2013 - 01:24 PM
Is This A Good Question/Topic?
0
MultiQuoteReplies To: What Data Structure does a vector use?
#3
qkrtjdwls91
- New D.I.C Head
Reputation: 2
- Posts: 15
- Joined: 19-December 12
Re: What Data Structure does a vector use?
Posted 05 January 2013 - 06:39 PM
Skydiver, on 05 January 2013 - 06:35 PM, said:
Did you even try cracking open the vector header file to find out yourself?
U can do that? O.O where does visual studio 2010 keep its header files? in windows 7
Was This Post Helpful?
0
#5
Aphex19
- Born again Pastafarian.
-
Reputation: 604
- Posts: 1,866
- Joined: 02-August 09
Re: What Data Structure does a vector use?
Posted 05 January 2013 - 11:23 PM
qkrtjdwls91, on 06 January 2013 - 01:39 AM, said:
U can do that? O.O where does visual studio 2010 keep its header files? in windows 7
In VS you can just right click the #include <vector> line and go to "Open Document", although you should be able to find vector in "C:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\crt\src".
What concrete data structure does a vector use? This might shed some light on the subject. Basically, it's a contiguous array of elements as far as I know.
This post has been edited by Aphex19: 05 January 2013 - 11:36 PM
Was This Post Helpful?
2
#6
jjl
- Engineer
-
Reputation: 871
- Posts: 3,996
- Joined: 09-June 09
Re: What Data Structure does a vector use?
Posted 06 January 2013 - 08:56 PM
It uses a dynamically allocated array, with two unique members that describe it (size and capacity). The size refers to the number of elements occupying the vector, the other describes the physically size of the dynamic array.
Was This Post Helpful?
0
#7
baavgai
- Dreaming Coder
-
Reputation: 4892
- Posts: 11,288
- Joined: 16-October 07
Re: What Data Structure does a vector use?
Posted 07 January 2013 - 05:42 AM
Technically, it uses whatever the hell it likes. It need only support it's public methods. The implementation is irrelevant. Isn't Object Oriented Programming grand?
In practice, there's usually an array involved. This is because random access is more expensive in other structures. However, you could have an array of arrays, so reallocation isn't so expensive... It you were on an architecture that used something like static sized memory pages, you'd might take advantage of that.
Those are implementation details. The user of the class should never have to be concerned with such things.
In practice, there's usually an array involved. This is because random access is more expensive in other structures. However, you could have an array of arrays, so reallocation isn't so expensive... It you were on an architecture that used something like static sized memory pages, you'd might take advantage of that.
Those are implementation details. The user of the class should never have to be concerned with such things.
Was This Post Helpful?
3
Page 1 of 1
|
|
| 