my list implementation is very slow

[salem c]

> If it returns NULL, then data = NULL not old memory
No.
This is how you use realloc properly.

void *temp = realloc( data, sizeof(T) * capacity * 2 );
if ( temp ) {
  data = temp;
  capacity *= 2;
} else {
  // data and the old value of capacity are still valid.
  // If this were an editor, you could panic dump all the user's hard work
  // to a file, rather than lose the whole lot.
}

> so is there any way to do this with new and delete
Yes, you new[] a whole new block of memory, do a proper copy/assignment loop (no hooky memcpy), then delete[] the old pointer.

[fewdiefie]

@dutch what is the realloc alternative in C++

[TheToaster]

There is no new/delete alternative of realloc in C++ unfortunately.

[dutch]

Toaster wrote:

Well I wasn't saying that realloc being faster is a lie,

Now you are the one who is lying.
I just explained to you why realloc would be faster in a braindead test.
The C++ needs to COPY THE PREVIOUS DATA.
The C version doesn't necessarily need to.
That would almost certainly make the C version twice as fast.

[fewdiefie]

ok thank you all

[dutch]

fewdiefie wrote:

what is the realloc alternative in C++

Something like:

auto newdata = new T[new_capacity];
std::copy(newdata, newdata + old_capacity, data);
delete[] data;
data = newdata;

[fewdiefie]

@dutch Thank you, I will use that instead of realloc I guess

@Ganado
awkward method but here is how I tested the speed of my push_back

int testVector()
{
    int start, end;
    
    Vector<int> V;
    start = clock();
    for (int i = 0; i < 100; i++)
        V.push_back(i);
    end = clock();
    
    return end - start;
}

int testvector()
{
    int start, end;
    
    vector<int> v;
    start = clock();
    for (int i = 0; i < 100; i++)
        v.push_back(i);
    end = clock();
    
    return end - start;
}

int main()
{
    int avg;
    
    avg = 0;
    for (int i = 0; i < 1000; i++)
        avg += testVector();
    cout << avg / 1000.0f << endl;
    
    avg = 0;
    for (int i = 0; i < 1000; i++)
        avg += testvector();
    cout << avg / 1000.0f << endl;
}

[Ganado]

Isn't the the same thing you posted?
Edit: Oh, you had deleted your other post. Yes, that is the test I used.

[fewdiefie]

https://ibb.co/Y7KcPDY

[TheToaster]

dutch wrote:

Now you are the one who is lying. I just explained to you why realloc would be faster in a braindead test.

Exactly. Which is why I said I'm NOT saying that, if you read my comment:

Well I wasn't saying that realloc being faster is a lie,

Not sure where this is falling apart for you, dutch. Ganado said the same thing:

Ganado wrote:

Also, I would actually want to see your benchmarking before believing anything like that.

[fewdiefie]

@TheToaster why don't you just copy my class and do the benchmark yourself instead of being a bitch to everyone.

[jonnin]

on most systems realloc is just hiding the same ideas though it is probably *very* efficiently implemented in asm level code. I don't know of any OS / system where you can truly realloc at the assembler level, so realloc is very likely doing a delete and copy. It *may* be able to see if the back end of itself is free to use and growing into unused memory, not sure if it bothers to check that or not. You can test it... see what assembler realloc generates then see what you get with a delete/copy/c++ version and compare them.

an alternative answer is to get more memory than you need if you can afford to do that, rather than copy-grow into it later. systems have 32+ Gb now. If you need 10MB and grab 100 MB, no one will notice, as long as you do this in moderation only where it matters, down in the performance critical areas of your code. The same ideas do not work when dealing with smaller devices or graphics cards or other limited memory resources, of course. This is really just a flavor of the time space tradeoff, sacking space to save time...

[mbozzi]

Well I wasn't saying that realloc being faster is a lie, I was saying his claim that his Vector class works 2 times faster than std::vector

Well it might be, but that's possibly because it's somewhat broken & the benchmark is minuscule. Plus, the growth factor is 2, which requires substantially fewer allocations in a small vector.

Asymptotically, the growth factor should approach φ from the left. This is why Microsoft's standard library uses a growth factor of 1.5 (IIRC). A growth-factor of 2 represents a theoretical worst-case.

What's not clear to me is how readily modern system allocators can take advantage of the storage reuse potential when the growth factor is around 1.5.

[TheToaster]

@TheToaster why don't you just copy my class and do the benchmark yourself instead of being a bitch to everyone.

@fewdiefie

Lol, you come onto this website asking why your shitty trivial linked list isn't as fast as a highly tested and benchmarked data structure in the standard library. Next you tell me that your version is twice as fast than the standard library version because you put it in a loop a thousand times with ints (try it with anything with a custom constructor/destructor or any non-POD). When someone asks you for a benchmark, you lash out in anger, yelling out expletives

The reason why your current linked list implementation will never be as efficient as a standard library container for anything other than popping a couple ints into it for your Computer Science 101 assignment is simple. One only has to examine the difference between the two:
https://gcc.gnu.org/onlinedocs/gcc-4.6.2/libstdc++/api/a00588.html

[fewdiefie]

I only asked why my LinkedList is slower because I didn't know how std::vector was implemented but after I did a small research on that, I now know the difference, I did try my vector class with complex objects too and I get the same results, 2x faster, and when using it to hold my game entities, it gives me a small increase in performance, just because your name is TheToaster does not mean that you can act like a bitch dude, now sit the fuck down before I toast your ass. I bet that you never wrote a line of code, stupid rookie. my computer science is far better than yours, one could tell from your posts and comments that you suck dick for living.

[TheToaster]

First of all, why did you edit your comment nearly ten times within an hour to add more insults to it? I saw your first comment, but I didn't have time to respond to it, so I'm doing it now.

I only asked why my LinkedList is slower because I didn't know how std::vector was implemented but after I did a small research on that, I now know the difference,

A linked list runs linear time O(n) searching, but O(1) insertions/deletions once the position has been found. A std::vector has amortized O(1) searching/insertions at the end of it, and linear time elsewhere. This is basic data structures.

The reason your vector will not work properly for non POD types is because it is implemented using C style functions, which know nothing about constructors and destructors. You claim that your "computer science is far better than [mine]", yet you start huffing and puffing in anger like a 12 year old girl when someone gives you advice.

Here is a case that doesn't work with your vector:

#include <iostream>
using namespace std;
template <class T>
class Vector
{
public:
    Vector() :data{ nullptr }, size{ 0 }, capacity{ 0 } {}
    ~Vector() { delete[] data; }
    
    void push_back(const T& t)
    {
        if (!data)
        {
            capacity = 1;
            data = static_cast<T*>(malloc(sizeof(T)));
        }
        else if (size == capacity)
        {
            capacity *= 2;
            data = (T*)realloc(data, sizeof(T) * capacity);
        }
        
        data[size] = t;
        size++;
    }
    
    T &operator[](int index) { return data[index]; }

private:
    T *data;
    int size;
    int capacity;
};


struct nonPOD
{
    nonPOD(const char* t) : e{t} {std::cout << "CTOR\n";}
    auto& operator=(const nonPOD&){std::cout << "COPY-CTOR

\n"; return *this;}
     ~nonPOD() {std::cout << "DTOR\n";}
    const char* e;
};

int main()
{

    Vector<nonPOD> V;
    for(int i = 0; i < 10; i++) 
    {
        V.push_back(nonPOD("Hello")); //Run time ERROR
    }

    return 0;
}

The results are similar when you add inheritance and virtual methods are added to the mix. If you tried the code with an std::string you get a segmentation fault.

You cannot ask for advice on how to "optimize" your code and then act like a self-righteous, ignorant twat everywhere you go. We are only trying to help. Still not exactly sure what in my comment made you so furious with anger.

[fewdiefie]

if you replace delete with free inside of my class DTOR, it would work just fine without no errors, try it yourself, anyway, I do know that my class is not compatible with c++ objects and I never claimed that it would be, and that's why I replaced it with std::allocator for memory allocation and deallocation to fix that and now it works just fine, btw I am not mad I just enjoy insulting cheap whores, bitch you never learn the lesson, watch your god damn mouth, oh almost forget, I hope you get corona and die like a fucking dog. no offense though. are you gonna report this too.

[TheToaster]

No it doesn't. Outside of the for loop, the destructors for the objects inside of Vector never get called. If it were correct, you would see it call the destructor multiple times in a row at the end when V goes out of scope. It doesn't.

There's a reason we don't use these functions in C++. While you could make it "work", that really doesn't mean anything.

You are getting quite worked up, I suggest you take a moment to take a few deep breaths.

[fewdiefie]

as I said before I just enjoy insulting cheap whores, You are the one getting worked up, you are literally refreshing the page every second and hoping that I'm not here but guess what, I'm always here bitch.

[TheToaster]

...Congratulations?