6 Replies - 435 Views - Last Post: 07 January 2013 - 05:42 AM Rate Topic: -----

#1 qkrtjdwls91  Icon User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • Posts: 15
  • Joined: 19-December 12

What Data Structure does a vector use?

Posted 05 January 2013 - 01:24 PM

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>
Is This A Good Question/Topic? 0
  • +

Replies To: What Data Structure does a vector use?

#2 Skydiver  Icon User is online

  • Code herder
  • member icon

Reputation: 3590
  • View blog
  • Posts: 11,168
  • Joined: 05-May 12

Re: What Data Structure does a vector use?

Posted 05 January 2013 - 06:35 PM

Did you even try cracking open the vector header file to find out yourself?
Was This Post Helpful? 0
  • +
  • -

#3 qkrtjdwls91  Icon User is offline

  • New D.I.C Head

Reputation: 2
  • View blog
  • Posts: 15
  • Joined: 19-December 12

Re: What Data Structure does a vector use?

Posted 05 January 2013 - 06:39 PM

View PostSkydiver, 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
  • +
  • -

#4 Skydiver  Icon User is online

  • Code herder
  • member icon

Reputation: 3590
  • View blog
  • Posts: 11,168
  • Joined: 05-May 12

Re: What Data Structure does a vector use?

Posted 05 January 2013 - 06:47 PM

Look at your INCLUDE environment variable. It should list which directories the VS compiler searches to find header files.
Was This Post Helpful? 0
  • +
  • -

#5 Aphex19  Icon User is offline

  • Born again Pastafarian.
  • member icon

Reputation: 615
  • View blog
  • Posts: 1,873
  • Joined: 02-August 09

Re: What Data Structure does a vector use?

Posted 05 January 2013 - 11:23 PM

View Postqkrtjdwls91, 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  Icon User is offline

  • Engineer
  • member icon

Reputation: 1076
  • View blog
  • Posts: 4,536
  • 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  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5848
  • View blog
  • Posts: 12,707
  • 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.
Was This Post Helpful? 3
  • +
  • -

Page 1 of 1