CODEWITHSUNDEEP
c++
Dmitriy Korolevich
Dmitriy Korolevich

Reputation: 31

C++ std::set index of insert

I've faced a following issue:

Suppose I've got a std::set named Numbers, containing n values. I want to insert (n+1)th value (equal to x), which I in advance know not to be in the set yet. What I need is some way to check, in which position will it be inserted, or, equivalently, how many of elements less than x are already contained in Numbers.

I definitely know some ways of doing it at O(n), but what I need is O(log(n)). Theoretically it might be possible as std::set is usually implemented as Binary Search Tree (presumably O(log(n)) is possible only if it stores information about sizes of each subtree in each vertex). The question is whether it's technically possible, and if it is, how to do it.

Upvotes: 3

Views: 1888

Answers (5)

Yigal Eilam
Yigal Eilam

Reputation: 77

Instead of:

std::set<MyT> mySet;

use:

std::set<std::pair<MyT,int>> mySet;

Then, for example: 

//inserting a std::vector<MyT> myVec:
for (int i=0; i<myVec.size(); i++)
      mySet.insert( std::pair<MyT,int>(myVec[i], i) );

The sorted result:

for (auto it=mySet.begin(); it!=mySet.end(); ++it)
  cout << it->first << " index=" << it->second << "\n";

Upvotes: 0

baderman
baderman

Reputation: 126

Maybe you should use set::lower_bound(), which time, according to this (http://lafstern.org/matt/col1.pdf) document, should be proportional to log N

Upvotes: 0

Andriy Tylychko
Andriy Tylychko

Reputation: 16276

You can find "position" where this new element would be inserted in O(lon(n)) using set::lower_bound, but it's just an iterator. std::set::iterator is bidirectional, not random access, so you cannot count how many elements are smaller than that new one in O(lon(n))

Upvotes: 0

Mark Ransom
Mark Ransom

Reputation: 308452

All of the set functions are going to work with iterators; the iterator of a set is bidirectional, not random-access, so determining the position will be an O(n) operation.

You don't need to know the position to insert a new element in the set, and insertions are O(log n).

Upvotes: 1

Michael Krelin - hacker
Michael Krelin - hacker

Reputation: 143249

There's no "position" in set, there's iterator and set gives you no promises regarding implementation. You can, probably use lower/upper_bound and count elements, but I don't think it's going to take internals into account.

Upvotes: 1

Related Questions