If I have a datastructure which is the fastest way I could insert values into it in a specified range?

For example if I had a method:

myDatastructure var=new myDataStructure();

it would mean that I get a most optimised way of getting a datastructure holding values from 2 to 1000 in each of index sequentially.

  • This is too vague for me. And are you sure you want to write C++? Because your code is closer to C# or Java than to C++.
    – sbi
    Nov 10, 2011 at 12:12
  • 1
    See the following SO question: stackoverflow.com/questions/322715/… I think you will find it quite clear that insertion to a data structure is cheapest in a linked list implementation. When inserting a new element, the only operation that needs to happen is remapping the affected nodes.
    – maple_shaft
    Nov 10, 2011 at 12:14
  • it doesn't matter. :) i just quoted it as an eg. It could be anything- may be a vector or array. But I need it to be done the quickest way possible.
    – user841923
    Nov 10, 2011 at 12:16
  • @user841923 In Java a Vector is threadsafe, so you shouldn't use it if you are not concerned about concurrency. Furthermore, an array or array backed list of any kind is horribly expensive when it comes to insertion and removal.
    – maple_shaft
    Nov 10, 2011 at 12:31
  • 1
    The huge memory allocation overheads of a linked list is very unnecessary. Moreover, since the OP wishes to insert contiguous values, there's no reason at all not to use an array.
    – DeadMG
    Nov 10, 2011 at 13:08

2 Answers 2


If you have a C++11 STL, you could use the std::iota() function to insert sequentially increasing values into any container that supports iterators. As for choosing a type of container, C arrays or std:arrays should be the fastest as they require no additional memory allocations while inserting elements.


The fastest way to do this is to not do it. Here's an outline of a class that looks like a read-only array of consecutive integers.

class range {
  int low, high;
  typedef int iterator;
  range(int low, int high) { this.low = low; this.high = high; }
  iterator begin() { return low; }
  iterator end() { return high + 1; }
  int operator[](int index) { return low + index; }
range r(1, 1000);
for (r::iterator i = r.begin(); i != r.end(); ++i) { ... }

If you need a writable collection, then the answer depends on how you want to modify it after creation.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.