Jump to content
  • Advertisement
Sign in to follow this  
Will-O

C++ container choice

This topic is 3750 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

I have two object types (classes) with containers as a part of their member data in my current project. At the moment I'm only using the std::vector but I was wondering whether this was the best option. The first case is a 2D grid. At the moment this has a vector of vertices and a vector of links. I need to be able to look up a vertex in the grid so that the vertex can be moved. Also I need to look up links to alter some of their properties too. Once the containers of vertices and links have been populated they never need to be altered themselves (just the objects within the containers). The properties of the objects within these containers need to be recalled often in a random order. I would use an array but it's not possible unless the objects within the array are known at compile time. I also have a collection of algorithms for finding the index to the vertex/link I'm looking for. The grid object holds a lot of data so the most minimal of containers would be useful. The second is a string of positions (x,y). Again they will not need to be altered once loaded in. This time the information held in objects of this container will always be called in order, though sometimes forwards and sometimes backwards and sometimes skipping a few objects in the list. Also the objects within the container are never altered. Occasionally it is also necessary to delete all the objects within both containers, ideally without destroying the top object. Pseudo Code...
class Grid
{
  vector<Point> _verts;
  vector<Connector> _links;
  int _rows, _cols;

  Grid(int rows, int cols); // make grid

  Point GetVert(const int vNum); // access a vertex
  Connector GetLink(const int lNum); // access a link

  ~Grid();
}
class LongLine
{
  vector <Point> _records;
  int _currentRecord;
  
  LongLine(); // Calls ReadFromFile()

  void ReadFromFile(); // populates _records form a file
  cosnt int ThisPoint(); //Returns index of current point being accessed
  void GetNext();       // Goes to next in sequence
  void GetPrevious();   // Goes to previous point in sequence
  void GoFwd(const int num); // Go forward num places in sequence
  void GoBack(const int num); // Go back num places in sequence
  const Point GetPos(const int num) const; // returns the Point with index num

  ~LongLine();
}
[Edited by - Will-O on June 18, 2008 8:46:44 AM]

Share this post


Link to post
Share on other sites
Advertisement
A vector should be fine for what you're doing. Vector is best when you aren't changing things a lot. If you need to do a lot of adding and deleting (It sounds like you don't) a std::list might be better but I imagine you won't even notice a difference, If you have used a vector before then I would stick with it.

Also, the [] operator is nice too because you can access the vector like an array

Quote:

I would use an array but it's not possible unless the objects within the array are known at compile time.


Not sure what you mean by this. What ever you use you will have to fill it with objects at initialization time anyways.

[Edited by - firstelder_d on June 18, 2008 9:06:54 AM]

Share this post


Link to post
Share on other sites
std::vector is perfectly fine in most cases and from your description it looks like std::vector will also do just fine in your case.

If the order of the elements in your vector is not important you could possibly arrange them in a way that makes searching more optimal (sorted vector and then doing a binary search if possible)

You should have a look at the different algorithm complexities for the various STL containers to find the best container in other cases. A vector for instance is bad if you often have to delete or insert elements somewhere in the middle. You can work around this with a vector by swapping the element that should be deleted with the last one and then deleting the last one, but that is not always applicable when the order of the elements matters.
When you only have do add/delete elements at the back vector is fine, if you also have to add/delete at the front a dequeue is better suited. In other cases a std::list might be better suited but that depends on how ofter elements are changed and how often the list is traversed since list traversal is a lot slower than vector traversal.

The best thing to do is to understand how the various containers are implement to understand what operations are efficient and what operations are more costly.

Share this post


Link to post
Share on other sites
Quote:
Original post by firstelder_d
Also, the [] operator is nice too because you can access the vector like an array

Quote:

I would use an array but it's not possible unless the objects within the array are known at compile time.


Not sure what you mean by this. What ever you use you will have to fill it with objects at initialization time anyways.


Yes like the whole [] thing. Makes life quite easy and obvious - it's clear what's being done when, for example, I write _verts[(cols * j) + i] - where i is col number, j row number and cols total columns.

As to the bit about knowing about arrays at compile time - when the program starts the number of cols and rows are not known. An array would have to be made large and only partly in use, unless I've made a hash of initialising them! Either way the std containers and vectors especially are quite easy to populate and index to elements.

Share this post


Link to post
Share on other sites
Quote:
Original post by Trenki
You should have a look at the different algorithm complexities for the various STL containers to find the best container in other cases.
...
The best thing to do is to understand how the various containers are implement to understand what operations are efficient and what operations are more costly.


That was the subtext of my question. I'm not totally sure about which containers are best suited to what operation.

From what's been said it seems that vectors are fine in this case because it's actually a fairly static structure. I was more concerned about my continual need to look things up within the Grid object and hop around in the other one.

** I completely forgot to mention **
The vertex objects and link objects each point to the ones attached to each other, if that makes sense. e.g. the vertex 1 row up and 1 row in points to the link below, to the left, to the right and above.
Does this make a difference to the type of container used?

Share this post


Link to post
Share on other sites
Quote:
Original post by Will-O
** I completely forgot to mention **
The vertex objects and link objects each point to the ones attached to each other, if that makes sense. e.g. the vertex 1 row up and 1 row in points to the link below, to the left, to the right and above.
Does this make a difference to the type of container used?


No, but it significantly changes the abstract model in use. If it's a 2D grid, why use a 1D structure? If it's a grid in the usual sense, why do you move vertices? It's not entirely clear what you're doing.

If it's just a normal grid, you don't need to store these references between points at all. If you have this grid structure, you can easily find one point from another one without using any explicit references - just add 1 to the index to move right, subtract 1 to move left, add the row width to go down a row, subtract the row width to go up a row.

Given that you know the grid's width and height at the point of creation, I would have just used a 2D array and not bothered with any more complex structure. That's without knowing anything about your use case however.

Share this post


Link to post
Share on other sites
The links have properties which I need to alter/extract etc, which is why I've got them there. I did start with just the points but found that I needed the link info too.

class Point : public Vector4d // it's a position
{
Link *_Left, *_Right, *_Up, *_Down;
// assign pointers to neighbouring links
// this = v; force z = 0 & w = 1;
Point(Link *L, Link *R, Link *U, Link *D, Vector4d v)

};


class Connector : public Vector4d // holds directional info of link
{
Point *_start, *_end;
double _strength;

Connector(Point *p0, Point *p1, double strength); // assign pointers to verts
// at each end of this link

Vector4d S_times_D(); // retrieve multiple of
// strength & Direction
}


Edge vertices would not have all pointers assigned to links (NULL instead) so they would not be able to move 90deg to the edge (=>>corner ones not at all).

The 2D - 1D question is why I asked about the suitability of <vector> (as well as the container type vs container complexity). This is a 2D structure and I did try to create it with 2D arrays but on compiling there were problems because the size of the grid was not known at the point of compilation. Vectors are more flexible and robust than arrays but they are also 1D.

I'm using vectors and it seems to be the consensus that they're right for the job and experience shows vectors easier to work with than normal arrays so I'll stick with them.

Share this post


Link to post
Share on other sites
Quote:
Original post by Will-OThe 2D - 1D question is why I asked about the suitability of <vector> (as well as the container type vs container complexity). This is a 2D structure and I did try to create it with 2D arrays but on compiling there were problems because the size of the grid was not known at the point of compilation. Vectors are more flexible and robust than arrays but they are also 1D.


Vectors can be 2D as well, just like arrays:


vector< vector<type>> my2dVector;


And you address them just like arrays: m2dVector[j]

Share this post


Link to post
Share on other sites
Also, do you have any pointers *into* a vector? Pretty sure that addresses inside vectors aren't fixed. If the vector ever resizes they may change, which is guaranteed to happen when you are first filling it up.

Not sure if you do not, just making sure. =)

Share this post


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

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!