-3

To use vector efficiently we need to reserve the memory before setting the elements. But for map and set which are not contiguous containers how we can make them fast and efficient?

I have a vector/set/map of size 10s Millions of doubles and want to add non-repeated elements. I want to make it as fast as possible.

Roy
  • 65
  • 2
  • 15
  • 40
  • 3
    Maps and sets offer fast insertion times anyway. Vectors have to reallocate blocks of memory. – chris Jan 24 '13 at 04:10
  • There are overloads of `insert` and `erase` that take hints to avoid O(lg N), associative lookup. But without specifying what operation you want to make more efficient, this isn't a real question. – Potatoswatter Jan 24 '13 at 04:11
  • possible duplicate of (Q1) [Why is std::map implemented as red-black tree?](http://stackoverflow.com/questions/5288320/why-is-stdmap-implemented-as-red-black-tree) (Q2) [In STL maps, is it better to use map::insert than `[]`?](http://stackoverflow.com/questions/326062/in-stl-maps-is-it-better-to-use-mapinsert-than) – iammilind Jan 24 '13 at 04:14
  • 1
    @jogojapan, Well, you see, sometimes vectors get infected with O(log N) insertion complexity when they get too near a set in your code. – chris Jan 24 '13 at 04:17
  • @jogojapan: Contagious containers means that they don't store elements in continous memory space – Roy Jan 24 '13 at 04:20
  • @jogojapan, contagious containers means that you can get infected easily by them. e.g. contain hazardous material. – thang Jan 24 '13 at 04:21
  • 1
    @Hesam, The word you're looking for is *contiguous*. Contagious means easily spreadable, like a disease. – chris Jan 24 '13 at 04:22
  • 1
    One question per question, please. – Lightness Races in Orbit Jan 24 '13 at 04:59

1 Answers1

2

Q1) all STL containers are already as efficient as they can be. It's up to you the programmer to choose what data structures suits the given requirement. You need to understand the pros and cons of each data structures.

Q2) Map[key] = value calls operator[] which can also be used to access elements, not just inserting, whereas insert() function is only specific to inserting. insert() has few other overloading feature not available on operator[], check http://www.cplusplus.com/reference/map/map/insert/

gerrytan
  • 40,313
  • 9
  • 84
  • 99
  • 3
    I could argue number one. You can, if need be, produce something more tailored to your performance needs. I might be slightly misinterpreting your intention, however. – chris Jan 24 '13 at 04:18
  • 1
    remark that the operator[] adds an element if it isn't there. this is sometimes counter intuitive because when you want to read out from a key (not knowing that it isn't in the map) and end up adding it to the map. this is sometimes a hiccup for new programmers. – thang Jan 24 '13 at 04:20
  • @chris You could argue, but you'd be wrong; all of the STL containers are as efficient as they can be implemented. Sure, you could write your own container, with its own performance characteristics that may better fit your needs. But that's not what the STL containers are; they are generic containers giving a specific interface. And they are as efficient as that interface can possibly be. Just because something is more tailored to what you want doesn't mean it somehow breaks proven performance characteristics. – Alice Oct 08 '15 at 15:00
  • @Alice, I agree. For as general as they need to be, huge care was put into making them efficient. – chris Oct 08 '15 at 15:14