What is preferable to use to store a fairly large number of elements (simple types)? vector<pair<>> or unordered_map ? And is there anything more productive than vector for storing a one-dimensional list? Everywhere I see that instead of an array, when a dynamic number of elements is used, it is vector that is used.

In the case of a one-dimensional list, you need to quickly add and delete. And look for the value through the pointer to the memory cell. In the case of a two-dimensional list, you need to search for the second value by the first, add, delete.

  • one
    These containers have different properties. How did you just take them and compare them in performance? Anyway, what purpose are you pursuing? - Anton Sazonov
  • OK. Large amounts of simple data. Including pointers. No "collapse" when removing items. We need one-dimensional and two-dimensional type of lists. Quick search for an item by key in the case of two-dimensional. - user64675
  • I did not understand a bit, but how is the key search related to vector? - Anton Sazonov
  • vector <pair <Key, Value >>. I apologize if it is not clear, I am in C ++ after C #. There are dictionaries. - user64675 September
  • and what you need? fast read or quick add / delete? - Pavel Ershov

1 answer 1

If you need quick add and remove, take unordered_set : it has these operations - depreciated O (1). It is not clear, however, what you mean by "search for a value through a pointer to a memory cell."

For the second case, you need unordered_map , it has the same asymptotics.

For the case of vector<pair<Key, Value>> you have to search, add and delete O (container size). For small size values, this may be more likely due to the primitiveness of operations, but with any large size take unordered_* .

Since you mentioned in the comments that you came from C #: in C ++, unlike C #, it is a rather slow standard allocator. Therefore, the performance of containers may well be weaker than that of similar in C #.

  • I mean the ability to get a pointer to the added element, for its subsequent change and getting its value. - user64675
  • @ rinart73: Well, insert returns an iterator to the inserted item. But pay attention to the subtleties: (1) after inserting the next element, the iterator (and therefore the pointer to the element) is invalidated, it can no longer be used. (2) you cannot change an item by this iterator / pointer, since you will change the hashcode of an item. - VladD
  • But in unordered_set you need to bother with hashes. Productivity will suffer again ... And what are the options then? How to add a large number of elements, getting pointers to them, which will be valid and according to which elements can be changed? Is it possible to take not an element iterator, but a pointer to a memory cell? - user64675
  • @ rinart73: (1) faster than unordered_set , does not happen. If you need a quick delete, there is no better solution than a hash table. The performance there is O (1), which is anyway better than the O (n) of a naive container. - VladD
  • one
    @ rinart73: A reasonable compromise can be placing an element in a structure, not a pointer to it: unordered_set<struct data*> . - VladD