0

I am confused. I don't know what containers should I use. I tell you what I need first. Basically I need a container that can stored X number of Object (and the number of objects is unknown, it could be 1 - 50k).

I read a lot, over here array vs list its says: array need to be resized if the number of objects is unknown (I am not sure how to resize an array in C++), and it also stated that if using a linked list, if you want to search certain item, it will loop through (iterate) from first to end (or vice versa) while an array can specify "array object at index".

Then I went for an other solution, map, vector, etc. Like this one: array vs vector. Some responder says never use array.

I am new to C++, I only used array, vector, list and map before. Now, for my case, what kind of container you will recommend me to use? Let me rephrase my requirements:

  • Need to be a container
  • The number of objects stored is unknown but is huge (1 - 40k maybe)
  • I need to loop through the containers to find specific object
Community
  • 1
  • 1
celta
  • 33
  • 3
  • 1
    You might want to read some books that contain chapters on data structures for why you'd choose one over another. **Edit:** Als' diagram covers the rest of my comment :) – Merlyn Morgan-Graham Aug 11 '11 at 06:20
  • When you say *loop through the container to find specific object*, what do you actually mean? Locate an element in a given position? Locate an element from which you know the value? Locate an element that meets some criteria? – David Rodríguez - dribeas Aug 11 '11 at 07:16
  • @david: When new input/string comes in, i need to check if its exists in my container, if not then i create a new one. – celta Aug 11 '11 at 07:28

5 Answers5

6

std::vector is what you need.
You have to consider 2 things when selecting a stl container.

  1. Data you want to store
  2. Operations you want to perform on the stored data

There wasa good diagram in a question here on SO, which depitcs this, I cannot find the link to it but I had it saved long time ago, here it is: STL container selection flow chart

Alok Save
  • 202,538
  • 53
  • 430
  • 533
  • 2
    Nice diagram, but it lacks a caveat: *few* objects ? --> `vector`. – Matthieu M. Aug 11 '11 at 06:25
  • +1; Only problem with this diagram is that it needs to be accompanied by a paragraph to a chapter about each of the boxes :) Great for reference, but not for learning. – Merlyn Morgan-Graham Aug 11 '11 at 06:28
  • Hey man. THis is awesome diagram (I saved the diagram as well). Thanks alot :D – celta Aug 11 '11 at 07:28
  • 2
    Actually, it's a pretty bad diagram, since it ignores one of the major issues (validity of iterators) and makes some unjustified assumptions: need to insert in the middle leads immediately to `list`, but `vector` also supports insertion in the middle, and is generally preferable to `list` even when inserting in the middle. – James Kanze Aug 11 '11 at 08:03
  • I agree with James in that a few things are missing from the diagram, as well as from the question. I find it interesting that the user has accepted this answer, after adding as a comment to the question an important bit of information: He wants to perform lookups to determine whether an element exists in the container! That means that according to the diagram it should be either a `map` or a `set` (and adding the missing bits: or an `unordered_map` or `unordered_set`). Again, beware of incomplete questions (missing important bits of information) and answers (might be missing details) – David Rodríguez - dribeas Aug 11 '11 at 10:53
1

You cannot resize an array in C++, not sure where you got that one from. The container you need is std::vector.

john
  • 85,011
  • 4
  • 57
  • 81
  • you can if you really want to, even if manually or by using `realloc`. You shouldn't though. – littleadv Aug 11 '11 at 06:13
  • I was thinking of arrays declared with `T a[n];` (for some constant n) and you cannot resize them. Dynamically allocated blocks of memory can be resized of course (that's what std::vector does) but I wouldn't call them arrays. – john Aug 11 '11 at 06:16
  • @john: From the first link in my question (another question in SO). Thats why I say, I am not sure how to do it ;p – celta Aug 11 '11 at 07:30
1

The general rule is: use std::vector until it doesn't work, then shift to something that does. There are all sorts of theoretical rules about which one is better, depending on the operations, but I've regularly found that std::vector outperforms the others, even when the most frequent operations are things where std::vector is supposedly worse. Locality seems more important than most of the theoretical considerations on a modern machine.

The one reason you might shift from std::vector is because of iterator validity. Inserting into an std::vector may invalidate iterators; inserting into a std::list never.

James Kanze
  • 150,581
  • 18
  • 184
  • 329
  • Does it take lots of time shift from vector to list (coding wise), because I am still not familiar with those 2 (but I used them once before, however, I could not remember much of them) – celta Aug 11 '11 at 08:15
  • It depends on what you're doing with them. If you do anything that uses random access, the shift to list will be difficult. Otherwise, it should be sufficient to just change the type. – James Kanze Aug 11 '11 at 10:59
0

Do you need to loop through the container, or you have a key or ID for your objects?

If you have a key or ID - you can use map to be able to quickly access the object by it, if the id is the simple index - then you can use vector.

Otherwise you can iterate through any container (they all have iterators) but list would be the best if you want to be memory efficient, and vector if you want to be performance oriented.

littleadv
  • 20,100
  • 2
  • 36
  • 50
  • 2
    "but `list` would be the best if you want to be memory efficient" --> **No**. `list` is not memory efficient, at all, because each node is allocated independently (pray your `malloc` implementation does not waste too much space on each node) and contain, at least, 2 pointers on top of your data. The *only* advantages a `list` are `splice` and its iterator invalidation rules (the latter derives from the fact it's a node based container). – Matthieu M. Aug 11 '11 at 06:22
  • @Matthieu - yes, you're right. Yet... `vector` increments allocations in multiple of previous, which means that on the 20K+1 item you may end up with 40K allocated space. What you refer to is fragmentation, which may be an issue. What I refer to is utilization which too may be an issue. And the OP is the one to decide which is more important to him. – littleadv Aug 11 '11 at 06:26
  • @littleadv - On the other hand, at 20k-1 you would then only waste one element with the vector, but have 40k pointers in the linked list. – Bo Persson Aug 11 '11 at 07:57
  • @littleadv: actually, the factor is implementation dependent. The solution is to use `std::vector::reserve`, which allows you to allocate, in advance, the space. The implementation might "bump" the requested number (gcc does not), but if you have a poor STL implementation, `std::vector` might be the last of your worries... – Matthieu M. Aug 11 '11 at 11:59
0

You can use vector. But if you need to find objects in the container, then consider using set, multiset or map.

Donotalo
  • 12,748
  • 25
  • 83
  • 121