How to "delete" a part of an array and keep the rest without running through it?

Question

I am trying to implement an algorithm in C++.

In the pseudocode, there is this: w ←w[0..e], where w is an array of characters and e is an integer. Basically I want to keep a part of the array and discard the rest.

Just to make the program working, I have used a for loop, where I scan through the original array up to e and I copy the values in a new array.

char newArray[sizeIAlreadyKnow];
    for (int i=0;i<e;i++) 
        newArray[i] = w[i];

I know this is not efficient; is there a way to avoid iterating through the original array? Also I am not very familiar with vectors. Do they have a functionality for this?

Thank you in advance

Answer 1

You can use std::string::resize. The basic idea is to use std::string instead of raw arrays of char. Correspondingly, things also become much easier and safer by using std::vector<T> instead of raw arrays of T.

Answer 2

You're right, you should really use vectors !

A lot of documentation is available here, there are also a lot of good tutorials on c++ and std containers (ask google for some of those)

Conserning your question, what vectors can do is (create a copy)

std::vector<char> myArray;
// fill your array, do watherver work you want with it
std::vector<char> newArray(&myArray[start], &myArray[end]);

or in you case (resize)

std::vector<char> myArray;
// fill your array, do watherver work you want with it
myArray.resize(e);

Each and every one of the methods on vector listed in here come with exemple. Reading those might help you a lot with the implementation of your algorithm.

If you ever need, more can be done (like sorting) using the algorithm section on vector (or any other std container)

Answer 3

What you're asking is not possible with C++ builtin arrays or std::vector out of the box.

In the D programming language, it's is possible. If you scroll down to the section labelled Introducing Slices in the link below, you'll find an explanation about how it's possible. In short, it can't be done without garbage collection. You can't free an array in C++ by calling delete on a pointer to the middle of it. So if you tried to slice the middle out of an array, then ditched the old pointer, you would have no way to free the memory, and your program would leak.

http://dlang.org/d-array-article.html

Now, while it's not possible using a language construct, it is possible in a number of other ways.

Of course, there is the obvious, as stated by Amxx: You can simply copy the segment of the array you want into a new array or vector. However, if you're concerned about performance, this is not the best way.The vector constructor Amxx is using will still loop over all the elements and copy them, even though you can't see it.

For a more efficient solution, there are C++ iterators. If you have a function that you want to work on a subset of an array, you can make your function accept iterators instead of an array or a vector.

For example:

int sumElements(vector<int>::iterator first, vector<int>::iterator last)
{
    int sum = 0;

    for( ; first != last; ++first)
        sum += *first;

    return sum;
}

vector<int> numbers;

for(int i = 0; i < 100; ++i)
    numbers.push_back(i);

int sum = sumElements(numbers.begin() + 10, numbers.begin() + 20);

There are also things like a string_view:
http://en.cppreference.com/w/cpp/experimental/basic_string_view

string_view is a non-owning reference to a slice of a string, but instead of having to deal with a pair of iterators, you can just treat it like the object that it is a slice of. Internally, it just stores pointers to the original string. The caveat though, is that since string_view is a non-owning reference, the original string's lifetime must outlast that of any string_view pointing at it.

The same thing could also be done with a vector, but there is nothing in the standard library for this yet(even string_view is still experimental).

I suppose you could do something like this:

template<class T>
class vector_view
{
    vector<T>::iterator first;
    vector<T>::iterator last;
public:
    vector_view(vector<T>::iterator first, vector<T>::iterator last)
        : first(first), last(last) { }

    const T& operator[](size_t i) const {
        assert(first + i < last);
        return *(first + i)
    }

    size_t size() const {
        return last - first;
    }
};

vector<int> numbers;
// ... init numbers with 100 numbers

vector_view<int> vv(numbers.begin() + 5, numbers.begin() + 32);

int number = vv[10];

I would probably just stick to vectors and iterators to keep things simple, but there you have it.

edit: similar ideas to the one above are discussed in this proposal for C++ ranges:
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n4128.html