Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question
    
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 '11 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 '11 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 '11 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 '11 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 '11 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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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