(a natural question from a beginner's perspective, but I couldn't find one. It may be due to my lack of understanding of data structure.)
Let's assume a situation where there is no need to check if the key already exists when inserting an element into the std::map. E.g. Inserting a pair from another std::map(which doesn't have duplicate keys).
But, as far as I know, operator[], insert, and emplace lookup the key among the existing keys.
Is lookup required, because std::map is a tree-type data structure? (although it's up to the implementation).
Since the map must be sorted by key, it seems impossible not to do a lookup when inserting.
Is my understanding correct, or is there a way to add a key (and its mapped value) into std::map without checking for duplicates?
Is lookup required, because
std::mapis a tree-type data structure?
No, lookup is (practically) required because lookup is required to be faster than O(n). (It is not required that a std::map be implemented as a tree-type data structure.)
If lookup was allowed to be O(n), then it would not matter where a new element goes; a search could simply look at everything. Conversely, looking at everything takes O(n) time. In order to beat this time complexity, a search must be able to eliminate some entries from consideration without looking at them.
When adding an element to a std::map, the new element must not be placed where the lookup will eliminate it without looking at it. That is, it must be placed so that looking it up will find it. How long does it take to find a place for the new element? Well, if it took less time than finding the element later, replace your "find" algorithm with whatever you use to find a place for the new element. If it takes more time, replace whatever you use to find a place for the new element with your "find" algorithm. The end result is that whatever you use to find a place for the new element is equivalent, in terms of algorithmic complexity, to finding the element later.
So an insertion requires a process that is as complex as lookup. For practical considerations, we might as well say insertion does a lookup. (I'll add the caveat that the lookup could be done in advance of the insertion – with other work done in between – as long as the insertion has the result of the lookup and as long as the "other work" does not invalidate the lookup. The standard containers do not expose such an interface, though.)
Note that the above applies to all standard sorted containers, not just std::map. I would in particular call out std::multimap, where the existence of a duplicate key does not prevent an insertion. (To me, the question reads as if the thought was that the point of performing the lookup was to prevent duplicates.) Even when duplicate keys are allowed, insertion requires a lookup (or equivalent) whenever lookup is required to be faster than O(n).