Proper grasp of arrays in memory

[Zaprzap]

This is the first time I have felt a smidgen of fear when learning C++. I am doing an exercise in Accelerated C++ and the fear is that I'm not appropriately handling memory. I'll list my code below but I figured I would give some specific questions first:

1. Is this statement correct: In memory, elements of an array are stored "against" each other (I think more precisely, contigious space is allocated for them?) and a pointer to an array points to the first element.

2. Are there any memory-specific issues that the below code will encounter?

3. If it interests me, would tools such as Valgrind worth looking into now, or should I wait until I have a better grasp of C++?

4. My "String List" is not complete, but are there any other glaring issues I might look into?

Accelerated C++ I have enjoyed thus far, everything has presented itself with ease, with this chapter the only one that has given me any difficulty. So here is the code:

String_list.h

#ifndef GUARD_STRING_LIST_H
#define GUARD_STRING_LIST_H

// String_list.h
#include <string>

// Store a list of strings
class String_list
{
public:
    typedef std::string* iterator;
    typedef const std::string* const_iterator;

    String_list();

    size_t size() const { return list_size; }
    const_iterator begin() const { return first; }
    const_iterator end() const { return last + 1; }

    void push_back(std::string);
private:
    iterator first;
    iterator last;
    size_t list_size;
};

#endif

String_list.cpp

#include <string>
#include "String_list.h"

String_list::String_list():list_size(0) {}

void String_list::push_back(std::string s) {

    // allocate space for the updated list
    std::string* updated_list = new std::string[list_size + 1];

    // copy elements from list to updated list
    for (size_t i = 0; i != list_size; ++i)
        updated_list[i] = first[i];

    // add new string to updated list
    updated_list[list_size] = s;

    // destroy array and free memory
    if(list_size > 0)
        delete[] first;

    // update iterators
    first = updated_list;
    last = updated_list + list_size;

    ++list_size;
}

[mike_2000_17]

1) Is this statement correct: In memory, elements of an array are stored "against" each other (I think more precisely, contigious space is allocated for them?) and a pointer to an array points to the first element.

Yes. This statement is correct.

2) Are there any memory-specific issues that the below code will encounter?

No (but as you said, it's incomplete). There are a number of things that could be done better, but there is no memory-related "wrong-doing".

3) If it interests me, would tools such as Valgrind worth looking into now, or should I wait until I have a better grasp of C++?

It's never too early to try out Valgrind. If you have any doubts that some piece of code might be doing something funny memory-wise, like fiddling with pointers in some dubious way, then just run your program in valgrind (it helps if you make sure to compile with debugging symbols, which is done with the option -g for GCC / MinGW). If there is anything wrong, valgrind will most probably catch it. And after all, what's the worst that could happen? The worst that could happen is that valgrind gives you a report that you don't understand, and if so, just retry later on or come here to ask us what it means, it can only help you learn better.

4) My "String List" is not complete, but are there any other glaring issues I might look into?

Like I hinted at earlier, there are definitely some glaring issues.

First of all, you said that the class is incomplete, and by that, I understand that you have more functionality to add to it (like pop_back, ... and all the usual stuff and more). However, before you implement any of these other functions, you have to first take care of the Big Three (or Big Five, for C++11), that is, the Big Three: the destructor, the copy-constructor / copy-assignment, and the swap function; or the Big Five: the destructor, the copy-constructor, the move-constructor, the swap function and the assignment operator. I'm pretty sure that this topic is covered in your book, accelerated C++, because it's a central topic in C++, if not, read my tutorial on the Big Five that I linked to.

Second thing is that you have a redundancy in your implementation, the data member list_size is not necessary because you have the range of pointers (first,last) already. There is no reason to have this additional data member.

Third, I noticed that you are using an inclusive-inclusive range of iterators internally, that is, your last iterator actually points to the last element, instead of the usual one-past-last element. I understand that you might not yet be fully acustomed to the "C++ way of life" in terms of ranges of iterators, but trust me, this inclusive-exclusive pair of iterators is really the best way to do things, especially in C++ since everything else works this way. Once, I wrote a substantial amount of code that broke that convention by doing as you do (having the last of the range pointing to the last element) and it caused me a lot of grief and I eventually had to retract it and painstakingly convert it all to the conventional inclusive-exclusive convention, and it was definitely worth the effort. Also, you will eventually understand the value of following conventions as you gain experience, it makes code easier to write and easier to read.

A small thing, the size_t type is in the std:: namespace, like everything else is, you should refer to it as std::size_t. It's just that because size_t is inherited for the C heritage of C++, where namespaces don't exist, that most compilers allow size_t without the std:: qualification.

As of C++11 (2011 standard of C++), the assignment of the strings to the new array should be done (more efficiently) with a move-assignment, as so:

for (size_t i = 0; i != list_size; ++i)
    updated_list[i] = std::move(first[i]);

The idea of move-assignment (and move-construction, together, "move-semantics") is that some types, like std::string, are very cheap to move while being expensive to copy, where a move simply means that the internals (data members) are simply ripped out of the source object (which is to be discarded anyways) and handed over to the destination object, as opposed to a copy, which requires a complete duplication of the contents of the source object. But that's beyond what is covered by your book (obviously, it's too old to cover C++11 things), and it's more something to be aware of right now so you can revisit it later on.

And finally, it is generally recommended in C++ to use STL algorithms whenever you can, because that will reduce the number of potential errors you make when writing simple things like for-loops. For example, you can do your copy operation like this:

// Copy elements from first to last into updated_list
std::copy(first, last+1, updated_list);

Note how this would have been nicer if last was located one element after the last one, because that's what std::copy expects (like all other STL algorithms).

Btw, in C++11, you could do a move of the entire range too:

// Copy elements from first to last into updated_list
std::move(first, last+1, updated_list);

Bonus comment: You can dramatically improve the performance of your string list by using a geometric expansion strategy (which is what standard containers like std::vector do).

[Maritimo]

1) Is this statement correct: In memory, elements of an array are stored "against" each other (I think more precisely, contigious space is allocated for them?) and a pointer to an array points to the first element.

Yes it is correct.

[Maritimo]

2) Are there any memory-specific issues that the below code will encounter?

Yes, your first call to push_back will fail, for example, because iterator first do not point to any memory. To solve this, you must create the constructors and destructor.

4) My "String List" is not complete, but are there any other glaring issues I might look into?

Yes. You must create basically seven member functions to your String_list that are fundamental and you didn't:

1. Ordinary constructors
2. Default constructor
3. Copy constructor
4. Move constructor
5. Copy assigmment
6. Move assigmment
7. Destructor

In all of your classes you always must take care of all of this seven member functions. You have several alternatives to do this, you can code all of them, leave some of them to be created by default or specify that they must not be created with = delete in c++11.

You must define a group of "invariants" like: 1) iterator first point to an array of strings pointers, 2) iterator last point to the last plus one string pointer and 3) list_size indicates the number of elements. You must initialize your String_list class forcing this invariants with all of your contructors and keep this invariants with all of your member functions. Finally you must liberate all your resources with your destructor. Your String_list is not doing nothing of these!!

[Zaprzap]

I am now under the impression that this exercise came too early, because I have only learned about about "Default Constructors" and "Constructors with Arguments" with no further detail. The book appears to begin with copy constructors and others on the next chapter. I got exactly what I asked for though, thank you both!

Yes, your first call to push_back will fail, for example, because iterator first do not point to any memory. To solve this, you must create the constructors and destructor.

Actually, the first push_back call does not fail. On the first call, new space is allocated in memory for updated_list (1 space in memory). The loop in the push_back does not pass its first condition, so is skipped. The string is then added to updated_list. The first is then assigned to point at this place in memory.

Perhaps the exercise was not specific enough. Maybe it expected me to use a basic array in the class, such as list[100], as brief example in this chapter had used such a list. Whatever the case, I'm looking forward to learning more soon that I can use constructors properly.