complexity of set::insert

Question

I have read that insert operation in a set takes only log(n) time. How is that possible?

To insert, first we have find the location in the sorted array where the new element must sit. Using binary search it takes log(n). Then to insert in that location, all the elements succeeding it should be shifted one place to the right. It takes another n time.

My doubt is based on my understanding that set is implemented as an array and elements are stored in sorted order. Please correct me if my understanding is wrong.

You are assuming that std::set is implemented as a sorted array. Why? — Konrad Rudolph
Taken from cppreference: Sets are usually implemented as red-black trees. — chris
@KonradRudolph: Now only I got to know that sets are implemented using red-black tree. Thanks chris — bibbsey
Well, it should be known to anyone caring about data structures that sets are usually implemented using trees or hashes, not using arrays, because of performance... Heck, in Java, you actually have to decide whether you want a HashSet or a TreeSet (which is a SortedSet), and I doubt there is an ArraySet available. (Note that unmodifiable sets can efficiently be implemented as a sorted array, using binarySearch - so actually as a sorted tree stored in an array) — Has QUIT--Anony-Mousse
@Anony-Mousse: Actually, a flat set is, in many cases, more performant than a tree-based set, due to cache locality. — Benjamin Lindley

cdhowie cdhowie · Accepted Answer · 2012-10-08T06:39:09

std::set is commonly implemented as a red-black binary search tree. Insertion on this data structure has a worst-case of O(log(n)) complexity, as the tree is kept balanced.

complexity of set::insert

1 Answers