5

I am trying to create a set of n whole numbers in c++ and I was wondering is there is a more efficient way of doing it rather than the simple for loop as shown below

 std::set<int> indices;
    for(int i = 0; i < n; ++i){
        indices.insert(i);
    }

I tried googling but couldn't find the any answers. I feel like the incremental nature of the numbers being inserted should lead to a more efficient implementation.

Morpheus
  • 3,285
  • 4
  • 27
  • 57

4 Answers4

9

If you want to be efficient you can leverage emplace_hint. If the value to emplace should be emplaced right before the hint then it will happen in constant time instead of log N.

std::set indices;
for (int i = 0; i < n; ++i)
{
    indices.emplace_hint(indices.end(), i);
}

should be O(N) instead of O(NlogN).

NathanOliver
  • 171,901
  • 28
  • 288
  • 402
3

Probably not one more efficient, no.

std::generate (or in this case, more directly, std::iota) can also do what you want, but off the top of my head I can't see a particular benefit over a simple for loop, at least in terms of performance.

Ultimately, whatever you end up doing, will need to create lots of tree nodes with these values, and at some level the computer needs to iterate to do this. You don't get any benefit from pre-allocating here because that notion is meaningless with a set (though this would be a valid suggestion for a vector).

(Edit: I can't take credit for this, but rodrigo points out that an insert hint may help. Anecdotally I heard somewhere that hints tend to be ignored nowadays but I'm not sure how true that is.)

The best way is to try not to want this. Usually if you have a collection of N consecutive integers, you can find a way to not need it, be it through some magic maths or at least through generating only what you need on demand. I suppose there is an exception to every rule though.

Lightness Races in Orbit
  • 378,754
  • 76
  • 643
  • 1,055
  • after reading your answer, I might be looking at my original problem incorrectly. I have some random ints between 0 and n (n = 7 for example) like {3,5,6}. I want the set difference {1,2..7} - {3,5,6} – Morpheus Dec 03 '18 at 15:38
  • 2
    @Morpheus That *definitely* doesn't require you to construct a set with all numbers, but now it's a bit late to change the question to that, so you should probably make a new one. – Bartek Banachewicz Dec 03 '18 at 15:38
  • 1
    @Morpheus A much more interesting problem! If the range is small, I think I'd probably do what you're doing. If it's large, there's probably a better algorithm, at least one that's more time-efficient _and_ space-efficient, but off-hand I'm not sure what would look like, at least not without spending some time thinking and measuring... which would require knowing how the result is to be used. – Lightness Races in Orbit Dec 03 '18 at 15:39
  • 1
    @Morpheus What are you going to do with the set difference? – melpomene Dec 03 '18 at 15:40
  • @melpomene That's the final answer. I am printing it. – Morpheus Dec 03 '18 at 15:41
  • 1
    @LightnessRacesinOrbit This can be done with a two-iterator for loop, one going through all numbers, and the other through the set, like so `for (int i = 0, auto it = nums.begin(); i < n; ++i) { if (it != nums.end() && *it == i) { it++; continue; } result.insert(i); }` – Bartek Banachewicz Dec 03 '18 at 15:41
  • 1
    @BartekBanachewicz I think the iterator increment needs to be conditional? – Lightness Races in Orbit Dec 03 '18 at 15:41
  • 2
    About whether the hint is ignored in modern implementation, [GCC seems to use them as expected](https://gcc.gnu.org/onlinedocs/libstdc++/manual/associative.html#containers.associative.insert_hints). – rodrigo Dec 03 '18 at 15:42
  • 1
    @LightnessRacesinOrbit Yeah, you're right, but this was mostly to illustrate the idea anyway. – Bartek Banachewicz Dec 03 '18 at 15:42
  • 1
    @rodrigo Fair enough. I wonder where I heard that – Lightness Races in Orbit Dec 03 '18 at 15:43
3

There is this overload for set::insert():

iterator insert( iterator hint, const value_type& value );

where the hint is the position where you think the value should be inserted. Since your values are sorted, you can do:

for (int i = 0; i < n; ++i){
    indices.insert(indices.end(), i);
}

And get constant amortized time, instead of logarithmic time for each insert.

From the GCC docs:

Insertions can change from logarithmic complexity to amortized constant time, if the hint is properly used. [...]

If the hint parameter [...] is equivalent to: [...]

  • end(), then the item being inserted should have a key greater than all the other keys in the container.
Community
  • 1
  • 1
rodrigo
  • 94,151
  • 12
  • 143
  • 190
1

If you're set on direct construction, and are willing to use Boost, counting_iterator is an alternative:

std::set<int> indices(boost::counting_iterator<int>(0), boost::counting_iterator<int>(n));
Bartek Banachewicz
  • 38,596
  • 7
  • 91
  • 135