For e.g. if we have an array in python arr = [1,3,4]. We can delete element in the array by just using arr.remove(element) ot arr.pop() and list will mutate and it's length will change and that element won't be there. Is there a way to do this is C ot C++?. If yes the how to do that?
4 Answers
I guess you're looking for std::vector (or other containers in the standard library).
answered Jan 16, 2013 at 10:06
Angew is no longer proud of SO
172k18 gold badges377 silver badges478 bronze badges
7 Comments
izi
but how I implement such a method without the standart library? is there a way to do this in C?
Angew is no longer proud of SO
@IgorZimenko You asked "C or C++" (and tagged just
C++), so I answered for C++. In C, you'll have to implement this yourself. If you want to do that, just try it and if you hit concrete problems, ask new question(s) here on SO (tagged C). If you don't know where to start, reading a book on data structures might be in order.
Abhijit
@Angew: std::deque would be the closest approximation
James Kanze
@IgorZimenko How to implement without the standard library? You pretty much have to reimplement most of what
std::vector does. (It's not really as difficult as it sounds, if you ignore the allocator business.)James Kanze
@Abhijit I don't see where
std::deque would be any more appropriate than std::vector. Python lists provide both random access ([]) and removal/insertion at arbitrary places. Not to mention things like l[3::3] = 3 * [ 0 ], to set every third element to 0. |
Arrays in C are just pointers and they don't contains an information about their length. So, C-programmer should keep not only a pointer but it's length too. Here's a snippet to erase a particular value from "C-array"
/// \return a new length
int removeFromArray( int * array, int arrayLength, int elementToRemove ) {
int i;
for ( i = 0; i < arrayLength; i++ ) {
if ( array[ i ] == elementToRemove ) {
memmove( & array[ i ], & array[ i + 1 ], arrayLength - i - 1 );
return arrayLength - 1;
}
}
return arrayLength;
}
Comments
In C++ either you can use std::list or std::vector based on your mileage
If you need to implement in C, you need to write your double-link list implementation or if you wan't to emulate std::vector, you can do so by using memcpy and array indexing
4 Comments
juanchopanza
Or
std::array or std::deque.Abhijit
@juanchopanza: I believe the closest stl data-structure to Python List would be std::deque
juanchopanza
I am not completely sure, I haven't used python for a while. But there is a
collections.deque data structure, which makes me wonder...juanchopanza
This post seems to suggest that the underlying structure is an array.
As I understand, you don't want or able to use standard library (BTW, why?).
You can look into the code of the vector template in one of STL implementations and see, how it's implemented.
The basic algorithm is simple. If you're deleting something from the middle of the array, you must shrink it after. If you're inserting into the middle - you must expand it before. Sometimes it involves memory reallocation and moving you array, by memcpy for example.
Or you can implement double-linked list as mentioned. But it won't behave like array.
1 Comment
izi
No, I want to use standart library. But I'm very intrested in the algorithm that I can implement.
[]array, or a STLarray<>?