Thread: vector::insert is so slow

  1. #1
    Registered User
    Join Date
    Dec 2007
    Posts
    911

    vector::insert is so slow

    I opened up a large file of 700MB and read it in a vector<char> and then I want to insert in front of the file its size.
    I turns out to be not only very slow but also max out the CPU.
    Is it normal or am I doing something wrong?
    It works well on smaller files though.

    Code:
        char szDigits[32] = "700111222";
        vector<char> v(filesize+260, '0'); // contains file 
    
        for(int i = 0; i< 9; i++)  // it gets very slow here
        {
            v.insert(v.begin()+i, szDigits[i]);
            cout << "i: " << i << endl;
        }
    Last edited by Ducky; 06-15-2013 at 08:02 AM.
    Windows 10 with Visual Studio 14.0.

  2. #2
    Registered User antred's Avatar
    Join Date
    Apr 2012
    Location
    Germany
    Posts
    257
    vector::iinsert is only fast if you add new elements at the back of the vector. If you insert anywhere else, all the elements lying past the insert position need to be shifted up one position first, so of course that doesn't exactly speed things up.


    P.S. If you really must insert at the front, I'd recommend using a double-ended queue instead (std::deque).

  3. #3
    Registered User
    Join Date
    May 2010
    Posts
    4,465
    What is "slow"?

    What type of variable is filesize and what exactly is it's value?

    What is the actual size of your vector?

    Jim

  4. #4
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,793
    Quote Originally Posted by Ducky View Post
    I opened up a large file of 700MB and read it in a vector<char> and then I want to insert in front of the file its size.
    Reserve enough bytes in teh beginning of the vector to write size later. start reading file from the preset offset in the vector. Then just overwrite the reserved bytes with actual size.
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    David J. Wheeler

  5. #5
    Registered User
    Join Date
    Dec 2007
    Posts
    911
    @antred Can I dereference a deque<char> as a vector<char> &v.at(0) or I have to switch back and forth between them?

    @vart I'm using ReadFile() to read it to the vector and ReadFile() can only read to the beginning of the file.
    It also crashes if I only reserve the size and not initialize it.
    But I will try it like ReadFile(&v.at(offset)).

    @jimblumberg No problem with the size as its less than 2GB and it works with smaller files.
    Last edited by Ducky; 06-15-2013 at 08:52 AM.
    Windows 10 with Visual Studio 14.0.

  6. #6
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,793
    Quote Originally Posted by Ducky View Post
    I'm using ReadFile() to read it to the vector and ReadFile() can only read to the beginning of the file.
    I do not see how it is relevant here. And I'm sure ReadFile is able to read at any offset in the file... You just do not need this feature.

    Quote Originally Posted by Ducky View Post
    It also crashes if I only reserve the size and not initialize it.
    So you doing it in the wrong way. Show us the code.

    What I mean - you create a vector of say 15 bytes

    read starting from the offset 5 10 bytes from file
    and after you finish reading - write the number of bytes read into the first 5 bytes of the vector.
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    David J. Wheeler

  7. #7
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    I'm using ReadFile() to read it to the vector and ReadFile() can only read to the beginning of the file.
    O_o

    The `ReadFile' API, like almost every file API in existence, reads from the current "read offset".

    As with other API, you use a function, namely `SetFilePointer' if I recall, to set the "read offset" manually.

    Reserve enough bytes in teh beginning of the vector to write size later.
    That is fine, but you could query the size of a real file in advance.

    Soma

  8. #8
    Registered User
    Join Date
    Dec 2007
    Posts
    911

    It's working

    Thanks, I worked it out with resize().
    - so I push back the header info in an empty vector
    - I resize it to the right size
    - then I read the file content just after the header info

    It's very fast now. Do you think I still need reserve()?
    It seem to work without it.

    Code:
    int main()
    {
        char * Buf2 =  "C:\\a.txt";
        char Buf3[260];
        HANDLE hFile=CreateFile(Buf2,
                                GENERIC_READ,
                                FILE_SHARE_WRITE,
                                NULL,
                                OPEN_ALWAYS,0,NULL);
    
        cout << "File created... " << endl;
    
        LARGE_INTEGER lpFileSize;
        if(!GetFileSizeEx(hFile,&lpFileSize))
        {
            return 1;
        }
    
        long long iFileSize=lpFileSize.QuadPart, r;
    
        int iWholeSize = 1 + strlen(Buf2) + 1 + iFileSize;
        int iDigits = GetNumberOfDigits(iWholeSize);
        iWholeSize += iDigits;
        char szDigits[32];
        itoa (iWholeSize, szDigits,10);
        sprintf(Buf3, "%s*%s*", szDigits, Buf2);
    
        vector<char> v;
        /// ////////////////////////////
        /// Insert header
        for(int i = 0; i< strlen(Buf3); i++)
        {
            v.push_back(Buf3[i]);
        }
        v.resize(iFileSize+260);
        /// ////////////////////////////
        /// Read file
        DWORD dwRead = 0;
        if(!ReadFile(hFile, &v.at(strlen(Buf3)),
                     iFileSize,
                     &dwRead, NULL))
    Last edited by Ducky; 06-15-2013 at 09:40 AM.
    Windows 10 with Visual Studio 14.0.

  9. #9
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    You don't need reserve if you are using resize, but let me ask you a couple of things:
    - Why are you using Win32 API instead of iostreams?
    - Why are you using char arrays and char pointers instead of std::string?
    - Why are you using sprintf instead of stringstreams?
    - Why are you manually calculating offsets? Why aren't you using a struct to store all the information you need? I see a lot of magic numbers everywhere too.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  10. #10
    Registered User
    Join Date
    Dec 2007
    Posts
    911
    1. There is no error checking possible with iostream.
    2. Very good question. I've still got it stuck in my mind that Win32 functions won't take anything but pointers. But now I that I know that they can take a vector<char> I will change them all. Thanks for the reminder.
    3. Ditto
    4. A struct. Yes that would make it much cleaner but it needed only to calculate once so there isn't much calculation involved.

    Thanks for the help!
    Cheers.
    Windows 10 with Visual Studio 14.0.

  11. #11
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,793
    Quote Originally Posted by Ducky View Post
    1. There is no error checking possible with iostream.
    Why not?
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    David J. Wheeler

  12. #12
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    There is no error checking possible with iostream.
    O_o

    As referenced in the other thread, your ignorance is still your problem.

    I do not care if you wish to use "WinAPI", but you shouldn't blame tools for your lack of knowledge in knowing how to use tools.

    Soma

    tellg() returning -1

  13. #13
    Registered User
    Join Date
    Dec 2007
    Posts
    911
    There are no return values with error codes like with Win32 functions.

    fstream:pen return value: none
    fstream:pen - C++ Reference
    Windows 10 with Visual Studio 14.0.

  14. #14
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    5,108
    There are no return values with error codes like with Win32 functions.
    O_o

    Okay.

    So, you'd rather make foolish guesses rather than actually learn to use an API by reading documentation.

    [Edit]
    If you still don't understand, read the documentation for the other methods.
    [/Edit]

    Noted.

    Soma

  15. #15
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Quote Originally Posted by Ducky View Post
    There are no return values with error codes like with Win32 functions.

    fstream::open return value: none
    fstream::open - C++ Reference
    There is a specific part on the site you linked to that describes what happens when there's an error. I suggest you take a closer look.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 2
    Last Post: 04-27-2011, 05:31 AM
  2. Insert new element into a vector
    By appointment in forum C++ Programming
    Replies: 7
    Last Post: 08-16-2009, 01:54 AM
  3. vector<...>::iterators and insert - I'm stumped.
    By Dino in forum C++ Programming
    Replies: 6
    Last Post: 12-25-2007, 06:11 AM
  4. vector insert functions
    By kes103 in forum C++ Programming
    Replies: 4
    Last Post: 03-24-2003, 03:12 PM
  5. Replies: 1
    Last Post: 09-17-2001, 05:46 AM