0

Here I have a pointer to the first element and int to hold the number of elements. How do I add in malloc and calloc for memory allocation? 

struct vector_new           
  {
  char *start;
  int count;
  }
  • 8
    How is std::vector inefficient? Look at the std::vector code it will show you the answer – mmmmmm Jun 06 '11 at 21:28
  • 1
    If you have frequent insertions/deletions with in the `vector`, then `std::list` would help. – Mahesh Jun 06 '11 at 21:30
  • 2
    You will **not** succeed in being more efficient than `std::vector`. Partly because `std::vector` has **no** overhead compared to raw pointers. In the best case, you will be *as good*. It’s technically impossible to be better. – Konrad Rudolph Jun 06 '11 at 21:30
  • What do you mean, "How do I add in malloc"? Write a function that does what you want to do. This is C, so it won't be a method of the struct, but so what? – jwodder Jun 06 '11 at 21:30
  • malloc and calloc? I thought it was new and delete only for C++. – duffymo Jun 06 '11 at 21:31
  • 2
    As a general rule, the odds that you can out-perform the standard library are pretty low, since a lot of work has gone in to making it fast. – Nemo Jun 06 '11 at 21:31
  • 3
    @duffymo (and others): The question title and tags indicate that the asker's using C, not C++. – jwodder Jun 06 '11 at 21:32
  • 1
    honestly: if you ask such questions, chances are slim you will succeed... – Mario The Spoon Jun 06 '11 at 21:32
  • Unless you're talking millions of values, C, C++, Python, bash, Excel, ... are all equally efficient :) – pmg Jun 06 '11 at 21:33
  • 4
    C does provide one advantage: if you use `realloc` to expand your allocation, it's *possible* you'll avoid a copy that would be necessary with `new` and `delete`. As such, although the complexity won't be better, from a practical viewpoint you *could* still get a noticeable improvement. – Jerry Coffin Jun 06 '11 at 21:40
  • For one thing, you should use `size_t`, not `int`, for the member count! – R.. GitHub STOP HELPING ICE Jun 06 '11 at 23:32
  • @Jerry but you cannot use `realloc` with non-PODs (in C++), and you can instead use a custom allocator that handles chunks itself, instead of relying on the underlying heap management of the OS. So there are two arguments against yours: first, that `realloc` isn’t applicable here, and secondly, that it doesn’t matter because we can still replicate its behaviour. – Konrad Rudolph Jun 07 '11 at 08:32

3 Answers3

5
vector = malloc(sizeof(struct vector_new))
vector->start = malloc(size);
vector->count = size;

I'm not sure exactly what you are asking for.

BTW, std::vector has a "used" size and a "allocated" size, a semantic which you do not reproduce here.

I also agree that you are unlikely to write this faster than std::vector. There may be reasons to use C instead of C++, but that isn't one of them.

Seth Robertson
  • 30,608
  • 7
  • 64
  • 57
3

You are looking for a "dynamic array" implementation.

You keep track of both how many objects are currently in the array and how much space is allocated for it. When you need more space you call realloc and ask for current_size * factor where factor is greater than one. Typical values for factor are between 1.4 and 2.

It can be shown that the amortized cost of appending n items to the array is O(n).

Note that this is not efficient if you want to insert stuff into the middle. That's a different critter.

dmckee --- ex-moderator kitten
  • 98,632
  • 24
  • 142
  • 234
0

I'm not sure I understand your question, but is this what you are looking for:

vector_new vec;
vec.count = 10;
vec.start = malloc(vec.count);
Martin Kristiansen
  • 9,875
  • 10
  • 51
  • 83
  • 4
    In C, casting the return value of `malloc` is redundant at best and may hide an error the compiler would have caught without the cast. Don't cast. – pmg Jun 06 '11 at 21:36