What is the best way to insert range of values into a datastructure

Question

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();
var.insert(2,1000);

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.

• sbi: 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++.
• maple_shaft: 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.
• user841923: 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.
• maple_shaft: @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.
• DeadMG: 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.

Answer 1

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.

Answer 2

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 {
private:
 int low, high;
public:
 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.