Inserting into a vector at the front

Question

iterator insert ( iterator position, const T& x );

Is the function declaration of the insert operator of the std::Vector class.

This function's return type is an iterator pointing to the inserted element. My question is, given this return type, what is the most efficient way (this is part of a larger program I am running where speed is of the essence, so I am looking for the most computationally efficient way) of inserting at the beginning. Is it the following?

//Code 1
vector<int> intvector;
vector<int>::iterator it;
it = myvector.begin();
for(int i = 1; i <= 100000; i++){
    it = intvector.insert(it,i);
}

Or,

//Code 2
vector<int> intvector;
for(int i = 1; i <= 100000; i++){
    intvector.insert(intvector.begin(),i);
}

Essentially, in Code 2, is the parameter,

intvector.begin() 

"Costly" to evaluate computationally as compared to using the returned iterator in Code 1 or should both be equally cheap/costly?

Ensheathe

Adding to the front of a vector means moving all the other elements back. If you want (to constantly perform) front insertion, you might really want to use list or deque. – Anamorphic

The only way to know how to speed up your program is with profiling. You should just program first then profile it and find out. Stop guessing. Do the second one, it's cleaner. (Obviously, these kind of micro-optimizations never make a difference; case in point, you should be using a container that can insert to the front faster, like deque.) – Uncork

You can also use IgushArray ( github.com/igushev/IgushArray ) which like an array has fast constant-time access operation, but insert/erase operation takes only O (N^1/2) time. Be careful, the structure is very sensitive for reserve() – Chamomile

There is a version of vector::insert that takes a range (two iterators) as argument instead of a value. Get an iterator (preferably random access, but at least forward) to generate the integers you want to add, and make a single call to insert: this way the vector will have a single reallocation+shuffling to make space for all of the new values. – Worsley

std::vector<T>::insert() can invalidate your iterator since it may cause the vector to resize. – Campground

If you need to insert a significant number at the beginning, you could reverse the vector, insert them at the back and then reverse it back. But without knowing the exact nature of your question, it is hard to say whether this would be cost efficient. – Commensal

Answer 1

The efficiency of obtaining the insertion point won't matter in the least - it will be dwarfed by the inefficiency of constantly shuffling the existing data up every time you do an insertion.

Use std::deque for this, that's what it was designed for.

Pointtopoint

Answer 2

If one of the critical needs of your program is to insert elements at the begining of a container: then you should use a std::deque and not a std::vector. std::vector is only good at inserting elements at the end.

Other containers have been introduced in C++11. I should start to find an updated graph with these new containers and insert it here.

Scot

The only case for using list is when you need the splice member. Use deque instead. – Pren

No not only. According to this diagram, when inserting in the middle should we use std::list. – Scot

@Billy -- That's not the only case for using list. You use list if you need to frequently insert or remove elements from the middle of the list, or call functions that require those operations, (like splice, or sort) – Truesdale

@PigBen: Sort is actually going to be slower on a list, because sort doesn't actually remove anything -- it only needs to compare and swap. (Okay, the swap operation can be made slightly cheaper if your objects are huge, but that's an abnormal use case) The problem with the "insert at middle" argument is that to get to the middle of the list requires linear time. If you can keep iterators around pointing where you need, by all means use list. However, I don't think I've ever seen anyone use list for that purpose; usually what is wanted is deque. – Pren

@Billy, thanx for arguing for the std::deque, it seems I should have used it most of the time instead of std::list. – Scot

Looks like the original is here...? linuxsoftware.co.nz/cppcontainers.html – Undertaker

I don't know. I have seen dozens of this schema reused in different pages. The site you are pointing to looks very thorough though. Maybe it is the real really original ;-) – Scot

@BillyONeal llvm.org/docs/ProgrammersManual.html#llvm-adt-ilist-node-h - llvm uses linked lists to store instructions inside a basic block – Wahoo

@borisov likely because basic blocks need multiple "entry" pointers rather than a flat linked list – Pren

@BillyONeal I posted this to illustrate that although you "haven't seen anyone keep pointers around" and use a list, that's a very natural use case for llvm since the LLVM IR is produced/owned by the front end, and the optimisation passes just keep pointers to instructions/basic blocks/functions/etc. and shift them around/modify them. Having a std::deque will not fit that use case. – Wahoo

@BillyONeal basic blocks themselves are stored in a std::vector and the CFG structure is implied by the terminator instructions at the end of each basic block but this is outside the scope of this question. – Wahoo

@borisov You found an example 5 years later. Color me surprised :P – Pren

@BillyONeal haha, happens :D I wanted to post this because I also thought that no one will use a list and keep pointers but apparently it exists and llvm is a big enough project to be a valid example. I'm currently writing an opt pass and I'm dealing with this on a day to day basis and it actually makes lots of sense. – Wahoo

@bonsov thanks for telling about it. I am just starting to use cland, I will need to keep that it mind. – Scot

@BillyONeal a list will be much slower on most sort algorithms since it doesn't give you random access. However it's tailor made for merge sort - only sequential access required, and instead of moving an object as you merge it into the new sequence, you simply relink it. – Pointtopoint

@Mark: Yeah, I guess it depends on how expensive elements are to swap in your data set. For ints, list probably loses. – Pren

Answer 3

An old thread, but it showed up at a coworker's desk as the first search result for a Google query.

There is one alternative to using a deque that is worth considering:

std::vector<T> foo;
for (int i = 0; i < 100000; ++i)
  foo.push_back(T());
std::reverse( foo.begin(), foo.end() );

You still use a vector which is significantly more engineered than deque for performance. Also, swaps (which is what reverse uses) are quite efficient. On the other hand, the complexity, while still linear, is increased by 50%.

As always, measure before you decide what to do.

Aigrette

people say about deque but question was about vector. This reply, IMHO, fit the best – Medorra

Answer 4

Most likely deque is the appropriate solution as suggested by others. But just for completeness, suppose that you need to do this front-insertion just once, that elsewhere in the program you don't need to do other operations on the front, and that otherwise vector provides the interface you need. If all of those are true, you could add the items with the very efficient push_back and then reverse the vector to get everything in order. That would have linear complexity rather than polynomial as it would when inserting at the front.

Discrepant

+1 for a solution to the question. Maybe later on in the code it's important to have a vector. Furthermore, it might be worse to use reserve to already reserve memory and save overhead from continously re-reserving. – Rota

Answer 5

If you're looking for a computationally efficient way of inserting at the front, then you probably want to use a deque instead of a vector.

Heti

Thanks. I will look into deque. I am hoping like the vector class, the deque class also allows for accessing its elements via object[index]. In my application insertion is one part of the problem...Accessing elements is another. – Ensheathe

@Tryer, yes deque supports quick access via [] notation. Not quite as fast as vector, but adequate for most purposes. – Pointtopoint

Answer 6

When you use a vector, you usually know the actual number of elements it is going to have. In this case, reserving the needed number of elements (100000 in the case you show) and filling them by using the [] operator is the fastest way. If you really need an efficient insert at the front, you can use deque or list, depending on your algorithms.

You may also consider inverting the logic of your algorithm and inserting at the end, that is usually faster for vectors.

Asafetida

Operator[] is no faster than any of the iterator related methods, or really any other method of filling a container (i.e. std::generate_n). Reserving won't really solve what's going on here. Yes, you save the allocations a bit, but you've still got order n-squared overall operation. – Pren

@Bill: Yes, the operator is not faster than the iterators or the generate functions. I just was pointing out that reserving the required space at the beginning (in the case he or she knows how much is it) and then accessing it via the operator also saves time and usually makes algorithms more clear. But again, depends on the algorithms. – Asafetida

Answer 7

I think you should change the type of your container if you really want to insert data at the beginning. It's the reason why vector does not have push_front() member function.

Steward

Answer 8

Intuitively, I agree with @Happy Green Kid Naps and ran a small test showing that for small sizes (1 << 10 elements of a primitive data type) it doesn't matter. For larger container sizes (1 << 20), however, std::deque seems to be of higher performance than reversing an std::vector. So, benchmark before you decide. Another factor might be the element type of the container.

• Test 1: push_front (a) 1<<10 or (b) 1<<20 uint64_t into std::deque
• Test 2: push_back (a) 1<<10 or (b) 1<<20 uint64_t into std::vector followed by std::reverse

Results:

• Test 1 - deque (a) 19 µs
• Test 2 - vector (a) 19 µs
• Test 1 - deque (b) 6339 µs
• Test 2 - vector (b) 10588 µs

Lal

Answer 9

This may draw the ire of some because it does not directly answer the question, but it may help to keep in mind that retrieving the items from a std::vector in reverse order is both easy and fast.

Rippy

This would be more useful as a comment under the original post – Elliottellipse

Answer 10

You can support-

1. Insertion at front.
2. Insertion at the end.
3. Changing value at any position (won't present in deque)
4. Accessing value at any index (won't present in deque)

All above operations in O(1) time complexity

Note: You just need to know the upper bound on max_size it can go in left and right.

class Vector{
public:
    int front,end;
    int arr[100100];   // you should set this in according to 2*max_size
    Vector(int initialize){
        arr[100100/2] = initialize; // initializing value 
        front = end = 100100/2;     
        front--;end++;
    }
    void push_back(int val){
        arr[end] = val;
        end++;
    }
    void push_front(int val){
        if(front<0){return;} // you should set initial size accordingly
        arr[front] = val;
        front--;
    }
    int value(int idx){
        return arr[front+idx];
    }
    // similarity create function to change on any index
};

int main(){
    Vector v(2);
    for(int i=1;i<100;i++){
        // O(1)
        v.push_front(i);
    }

    for(int i=0;i<20;i++){
        // to access the value in O(1)
        cout<<v.value(i)<<" ";
    }
    return;
}

Mowery