Python list and c/c++ arrays

Question

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?

i mean just the standart list in python like so a = ['spam', 'eggs', 100, 1234]. I don't have a clue what's a STL array<> is. — izi, Jan 16 '13 at 10:12
... C/C++ doesn't have a "standard list", and it certainly doesn't have Python's. — Ignacio Vazquez-Abrams, Jan 16 '13 at 10:12
I just need to know how to do what I asked) can you help with that? — izi, Jan 16 '13 at 10:14
The problem is, the answer really depends on whether you mean C or C++- C/C++ isn't a language. C provides bare-bones arrays which are not classes and provide no user-friendly member functions such as `pop()`. C++ provides a few array-like classes that do provide many useful methods. — juanchopanza, Jan 16 '13 at 10:24
A potentially useful link [here](http://stackoverflow.com/questions/914233/what-is-the-underlying-data-structure-for-python-lists). — juanchopanza, Jan 16 '13 at 10:34

score 5 · Answer 1 · answered Jan 16 '13 at 10:06

5

I guess you're looking for std::vector (or other containers in the standard library).

answered Jan 16 '13 at 10:06

Angew is no longer proud of SO

167,307
17
350
455

but how I implement such a method without the standart library? is there a way to do this in C? – izi Jan 16 '13 at 10:09
@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. – Angew is no longer proud of SO Jan 16 '13 at 10:14
@Angew: std::deque would be the closest approximation – Abhijit Jan 16 '13 at 10:25
@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 Jan 16 '13 at 10:43
@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. – James Kanze Jan 16 '13 at 10:49
@Abhijit after some reading, I have concluded that the closest C++ equivalent is `std::vector`. Python `list` seems to be implemented as an array, and has no `push_front` equivalents. – juanchopanza Jan 16 '13 at 12:58
@juanchopanza: I agree, I probably was thinking more beyond the simplistic approach. – Abhijit Jan 17 '13 at 16:08

score 1 · Answer 2 · answered Jan 16 '13 at 10:16

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;
}

score 0 · Answer 3 · answered Jan 16 '13 at 10:13

0

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

answered Jan 16 '13 at 10:13

Abhijit

62,056
18
131
204

Or `std::array` or `std::deque`. – juanchopanza Jan 16 '13 at 10:22
@juanchopanza: I believe the closest stl data-structure to Python List would be std::deque – Abhijit Jan 16 '13 at 10:25
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 Jan 16 '13 at 10:29
[This post](http://stackoverflow.com/questions/914233/what-is-the-underlying-data-structure-for-python-lists) seems to suggest that the underlying structure is an array. – juanchopanza Jan 16 '13 at 10:35

score 0 · Answer 4 · answered Jan 16 '13 at 10:16

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.

No, I want to use standart library. But I'm very intrested in the algorithm that I can implement. — izi, Jan 16 '13 at 10:41

Python list and c/c++ arrays

4 Answers4