Do people write vectors in C

Are Python list arrays vectors under the hood?

Assuming this isn't bait, you should know that C and C++ are different languages with different use cases. Although C++ is (basically) a superset of C with classes, stl, etc. it is not normally written the same way as C. (Note: many universities teach C++ as "C with classes", which is fine I guess but doesn't really teach the power of the newer C++11 ,14, or 17 constructs, which are used in industry code. Not always used, but they are used more often than not in my experience.)

To help this make sense, think about making a char[100]. In both C and C++, you are allocating 100 bytes on the stack of data you can do whatever you want with. You can clearly see how this is a powerful ability, and the use is clear. It may help to explain that an array is just a contiguous block of data with n elements, where it is sizeof(type)*n bytes long (excluding padding). You could explicitly write binary to a char array and then typecast it as a double, you'll get a double.

A C++ vector on the other hand, is a data structure that needs far more data when you create one typed char with 100 members. There is overhead in creating the vector, storing it, and resizing it. It is far easier (and often times more reliable), but you've added quite a bit of code, and that adds time and memory.

On modern computers the time/memory isn't really a huge deal, but it should be fairly clear now why C programmers don't just build vectors when they want to store data. An array and a vector are used for different things, and even though there is overlap in their uses that doesn't mean one will always be preferred over the other.

Good question, I really have no idea it's so complex. It doesn't remind me of a linked list and you can access items directly. Unless it iterates sequentially.
github.com/python/cpython/blob/master/Objects/listobject.c

python lists are linked lists and the arrays from numpy are dynamic arrays aka vectors.

source: pure guess

So is there any evident case of vectors being used in C for their search time and rescalability, or is it just generally avoided?
I do not think they're lists, click link on

No... Python lists are O(1) random access.

Proof?

Same way it is written in C++.

He's just going to Google it the same way you could have dummy

just look up what a vector is
then write it
they're one of the easiest data structures

How much spoon-feeding do you need? If you're this retarded you should change fields

Maybe I just wanted to see user provide an example out of curiosity, and proof that he knew what he was talking about. Why the hostility?
Idk about that, C doesn't have methods.

Meant to reply to

It's in the source code boi, someone just posted it.

realloc

lol that was me, didn't realize they provide d big O in the comments.

Sure it does

vector * v = vector_new();

vector_push_back(v, 5);

printf("length: %d\n", vector_size(v));
int x = vector_get(v, 0); // x = 5

vector_delete(v);

>on the heap

THAT DOESN'T COUNT

Attached: 318271da980706f7a18a811c3456a77d.png (633x758, 29K)

static methods are still methods
use meme function pointers if you want polymorphism

No, mainly because since C++ is (almost) a superset of C, if you want vectors you just write C++. I went a little overboard explaining it looking at that block of text lol.

Vectors are used for a couple reasons: resizeability, reliability, and flexibility/ease of use. The question is do we need that when we are writing pure C as opposed to C++? We don't. C is used in production for things like hypervisors, operating systems, embedded systems (among others). All of these systems memory and time are serious concerns. Say you are writing an emulator where the host machine's cpu runs at 4x the clock rate of the guest machine's, this means you have 4 clock cycles to emulate the guest machine's instruction to make it seem like the emulated guest machine is running at normal speed. Thats not a lot, and the code you are writing better be fast, you might even just want to write some assembly for that. You better fucking believe a vector resize operation takes a few more than four clock cycles. Don't even get me started on how absolutely fucking fast operating system code needs to be relative to user level code.

When writing these low-level applications speed, memory and robustness are the most important parts of the software. C++ is used in user level code because it has these constructs that make it easier for programmers to get the software in production, but also add slowdown and memory usage that the end user doesn't care too much about.

Also it should be noted that C++ is still faster than a lot of stuff since its compiled, don't be fooled into thinking that its slow. Its just not fast enough when you use stl for low level stuff (in most cases).

vector v;
vector_new(&v)

vector_push_back(&v, 5);

printf("length: %d\n", vector_size(&v));
int x = vector_get(&v, 0);

vector_delete(&v);

A C++ vector is just a size-constrained array under the hood that is intelligently realloc'd (or whatever bastardization is the c++ equivalent) as needed.

In C, you'd use a third party library or implement it yourself.

meant for

Its an very OP vector template that accepts literally any type

and yes every python noobs wield this power right out of the box

Are you retarded? Just about every operating systems and concurrent programming course in the US is taught in C.

Just because ITT Bombay doesn't teach using C doesn't mean actual universities don't.

What kind of shitty uni doesn't teach C?

Reminder:

Linked lists are terrible for caching

:-)

> Old Dominion
> ranked #231-300 on USNews
Maybe that's why nobody at your school knew C.

Attached: 729.gif (340x340, 137K)

don't modern processors all have markov cache predictors?

Attached: 1495398141882.png (1000x1100, 121K)

They are extensible arrays iirc.

> he doesn't use unrolled linked lists

checking in

>op
>allocates 8 bytes per element
It fosters ignorance and waste of resources. Use docs.python.org/3/library/array.html instead.
It was funny seeing the "sum the primes under 2 million" threads on Jow Forums, where Pythonistas were using lists for a bool array in their sieve. It takes ~7.45GiB of RAM just to hold a bool array of 1 billion elements using lists, compared to 0.93GiB for a char array.

> he doesn't know about unrolled linked lists
S I G H

I mean that sounds like something I just wouldn't want to use python for anyway

>he doesnt utilize every single bit

Not applicable to Python.
But you can optimize any language, and understanding of algorithms like prime sieves is language independent. The point is, a bool array doesn't need 8 bytes allocated per element, and one should know that. Languages like Python abstract too much, and give a poor understanding to beginners.

>what is heap

What C++ offers over C in this area is restricting access patterns (no private in C), ease of writing containers (template metaprogramming) and member function call syntax.
It doesn't make any more datastructures possible.

That said datastructure use tends to be more restrained in C. Usually because the areas where you use C you value predictability. I can't explain it quickly but if you use advanced datastructures you often give up the allocation to the library.
Of course there's ways around this...

Rate my bitsieve
$ time python3 -c 'import primes; print(sum(primes.bitsieve(2*10**6)))'
142913828922

real 0m0.712s
user 0m0.711s
sys 0m0.000s

Attached: Screenshot_2018-05-16_19-34-11.png (588x351, 57K)

at my uni the first year is almost entirely Scheme.

good now rewrite it in C

MIT? We do a little scheme at Rutgers, I think. I'm taking a principles of programming languages course next semester and I think they use scheme for the functional programming part.

>he thinks I know C

Attached: 1508965388120.png (466x492, 152K)

>So is there any evident case of vectors being used in C for their search time and rescalability, or is it just generally avoided?
If you're using C over something else, such as C++, then you're usually doing so for performance. Vectors are nice for the programmer because you can use it for a lot of things. But if you're writing C you'd probably rather customize your search for the specific task and memory structure.
If you wanted rescalability, you'd use realloc (and/or maybe VLAs). It takes a bit more time, but once you use the task to define bounds it's easy for realloc to provide the same rescalability functionality as vectors with much better performance.

It also has the advantage that it automatically deletes its heap contents when it goes out of scope and that the underlying array can be passed to C functions. C++ vectors are just comfy.

Verctor[Number of vector][U][V][W]

?

>he cant write a basic C program

You can do something like this pastebin.com/txQbd6i7

size_t *test = load_xarray(0, sizeof *test);
assert(xarray_size(test) == 0);
for (size_t i = 0; i < N/2; ++i) {
test = xarray_expand(test);
test[i] = i;
}
assert(xarray_size(test) == N/2);
for (size_t i = 0; i < N/2; ++i) assert(test[i] == i);
test = xarray_resize(test, N);
memset(test + N/2, 0, sizeof (size_t [N/2]));
assert(xarray_size(test) == N);
for (size_t i = 0; i < N/2; ++i) assert(test[i] == i);
for (size_t i = N/2; i < N; ++i) assert(!test[i]);
free_xarray(test);

This board is for Americans, friend.

No, they are arrays that double in size as space needs grow, more or less. I believe there are alternate implementations that use linked lists but CPython uses arrays.

>vector
>it's actually an array

Attached: 1499113774343.jpg (405x583, 25K)

????????

C++ first semester in my uni, and I'm in a third-world shithole.

>A C++ vector on the other hand, is a data structure that needs far more data when you create one typed char with 100 members. There is overhead in creating the vector, storing it, and resizing it. It is far easier (and often times more reliable), but you've added quite a bit of code, and that adds time and memory.
What the fuck are you on about. Most of the "code" involved in a std::vector implementation is template metaprogramming so it works with any possible type. The actual generated instructions are far less, and post-constexpr can even be zero-overhead in size & time. A vector shouldn't be any bigger or slower than doing the same thing in C. A C++ vector is not the equivalent of a C/C++ array aka int[], that would be a std::array.

its fine I have 32 gb

>can only sieve up to 32 billion

>write a vector implementation in C
>benchmark it
>same exact performance as C++ vectors in all cases but one
>it's much faster than C++ for growing small arrays when a realloc succeeds
>find out C++ "can't" use realloc or any equivalent because of new/delete shenanigans

Which third world country? SudAfrikant checking in and can confirm we did C++ in first semester EE

Portugal. ECE, C taught in the first year.

You can use vectors in C.
I have written a simple macro that allows you to create vectors of a generic type.
It has simple functions like reserving memory in advance pushing back and inserting elements.
it works kinda like this
MAKE_VECTOR(double) //you can use any type
vector_double v;
vector_double_construct(&v);
vector_double_push_back(&v, 13);
int index = 1;
printf("%lf", vector_double_get(&v, index));
vector_double_free(&v);

Using a macro is better than passing around void pointers because it allows for better optimisation.

which explains the post

you can do it many ways

How fast is that compared to std::vector?

for instance, you might implement a linked list...that is basically how c++ implements vectors

same goes for stack, queue, and other stl structures. you have to determine the primary data type. c++ allows for templates, enabling generic programming

I haven't benchmarked it but it does what you would do by hand in C. The macroed function returning an element from the vector is as simple as
static inline type vector_##type##_get(const vector_##type *vec, size_t index){\ return vec->data[index];\ }
pushing back reallocates twice the memory it is already allocated each time the reserved memory is reached. I have heard std::vector does the same.
It also has a version of push back that does not check if the pushed element is exceeding the reserved memory so you can reserve memory in advance and push elements back as fast as possible.

static inline void vector_##type##_fpush_back(vector_##type *vec, type elem){\ vec->data[vec->size++] = elem;\ }

static inline void vector_##type##_push_back(vector_##type *vec, type elem){\ if (vec->size >= vec->capacity){\ vec->data = realloc(vec->data, sizeof(type)*vec->capacity*2);\ vec->capacity *= 2;\ }\ vec->data[vec->size] = elem;\ vec->size ++;\ }\

As you can see the code is really simple and it does not check for errors in allocation. It just assumes that everything just goes right. It's just a simple experiment i wrote and it's obviously not meant for any serious usage so comparing it to std:: vector does not seem fair.

sorry I fucked up my formatting

>C is rarely taught these days
Funny, because I just got done with a networking class that uses C for the assignments.

Macro abuse.

>What C++ offers over C in this area is restricting access patterns (no private in C),
You can use an opaque handle but that's usually suboptimal in efficiency.

static inline
Enjoy your bloated executables.

Actually I recently completed my generic vector implementation in plain C
It's basically a heap allocated array of void pointers
I have created some function to move variables in and out of the heap and destroy them as needed so I can easily store in the vector objects of any type or even complex data structures
During initialization I specify the base size.
Once the array fill it automatically allocates more memory with realloc()
Once I delete enough element I can call a trim() function to deallocate unneeded memory
It works very good, it's fast, there are no leaks and it offers nice and fast random access
It's an opaque pointer too, I made so I can't look inside it and just my custom accessor functions to manipulate it (for exaple, sort(), filter(), reverse(), set(), get(), binsearch(), etc)

In other words C can do everything and it's great

>It's basically a heap allocated array of void pointers
Sounds inefficient as fuck

The functions are rarely longer than a few lines and most of them translate to a very few CPU instructions. There is no need to call a function when all the function does is return a value from memory. It would be inlined by the compiler anyways.

I know for a fact that my school uses C for Comp Org 2 and Operating Systems, not to mention the fact that we're a C++ school in the first place.

It isn't though
In some basic, not very thorough, tests I did, it's very fast
Rarely you want to use a structure to store a simple data type like an int and I like the flexibility void pointers provide
By passing function pointers to custom destructors, comparators, etc I can easily store complex data types (or even structures containing functions) inside it and repurpose it for any use and the memory management is easy (I just pass a custom destructor once and it handles everything and there are no leaks)
I just need to include a single file and no recompilations are needed, I prefer it than mucking with the preprocessor and abusing it

github.com/nothings/stb/blob/master/stretchy_buffer.h

My favourite implementation of vector-like behaviour in C for when I just want something done quick and easy.

This seems useful.
I really should take a more thorough look at the stb libraries.

>fuck, memory leak

this

You're correct when the data structure is a vector but for anything more complicated static inline is gonna bite you in the ass. There's a reason the semantics of inline are different in C++.

>t. Rajeesh

Which uni?

His point, that std::vector and standard c array have a different purpose is still valid. high performance computing often relies on a certain data format, e.g. for sparse matrices. You won't do that with a vector. You need to exactly know what's going on and therefore you use a c array

>You need to know exactly how shit your code is because you're a retard who thinks abstraction is bad

That's literally you.

At my suny school C is the first language you learn, then c++, then java, and if you're EE/CE you'll be doing lots of assembly and embedded c

But it's harder to do sparse matrices in C than in C++. You're not going to be using raw arrays, std::vector, or std::array as the primary storage of a (general) sparse array anyways, because all three are contiguous containers.