Optimizing sorting container of objects with heap-allocated buffers - how to avoid hard-copying buffers?

Question

I was making sure I knew how to do the op= and copy constructor correctly in order to sort() properly, so I wrote up a test case. After getting it to work, I realized that the op= was hard-copying all the data_.

I figure if I wanted to sort a container with this structure (its elements have heap allocated char buffer arrays), it'd be faster to just swap the pointers around. Is there a way to do that? Would I have to write my own sort/swap function?

#include    <deque>
//#include  <string>
//#include  <utility>
//#include  <cstdlib>
#include    <cstring>
#include    <iostream>
#include    <fstream>
#include    <algorithm> // I use sort(), so why does this still compile when commented out?

#include    <boost/filesystem.hpp>
#include    <boost/foreach.hpp>

using namespace std;

namespace fs = boost::filesystem;

class Page
{
    public:
        // constructor
        Page(const char* path, const char* data, int size) :
            path_(fs::path(path)),
            size_(size),
            rawdata_(new char[size])
        {
//          cout    << "Creating Page..." << endl;
            strncpy(rawdata_, data, size);
//          cout    << "done creating Page..." << endl;
        }
        // copy constructor
        Page(const Page& other) :
            path_(fs::path(other.path())),
            size_(other.size()),
            rawdata_(new char[other.size()])
        {
//          cout    << "Copying Page..." << endl;
            strncpy(data_, other.data(), size_);
//          cout    << "done copying Page..." << endl;
        }
        // destructor
        ~Page() { delete[] data_; }
        // accessors
        const fs::path& path() const { return path_; }
        const char* data() const { return rawdata_; }
        int size() const { return size_; }
        // operators
        Page& operator = (const Page& other) {
            if (this == &other)
                return *this;
            char* newImage = new char[other.size()];
            strncpy(newImage, other.data(), other.size());
            delete[] data_;
            rawdata_ = newImage;
            path_ = fs::path(other.path());
            size_ = other.size();
            return *this;
        }
        bool operator < (const Page& other) const { return path_ < other.path();    }
    private:
        fs::path path_;
        int size_;
        char* rawdata_;
};

class Book
{
    public:
        Book(const char* path) :
            path_(fs::path(path))
        {
            cout    << "Creating Book..." << endl;
            cout    << "pushing back #1" << endl;
            // below, the RawData will be coming from methods like
            // fstream.read(char* buffer, int filesize); or
            // unzReadCurrentFile(unzFile zipFile, char* buffer, int size);
            pages_.push_back(Page("image1.jpg", "firstImageRawData", 17));
            cout    << "pushing back #3" << endl;
            pages_.push_back(Page("image3.jpg", "thirdImageRawData", 17));
            cout    << "pushing back #2" << endl;
            pages_.push_back(Page("image2.jpg", "secondImageRawData", 18));

            cout    << "testing operator <" << endl;
            cout    << pages_[0].path().string() << (pages_[0] < pages_[1]? " < " : " > ") << pages_[1].path().string() << endl;
            cout    << pages_[1].path().string() << (pages_[1] < pages_[2]? " < " : " > ") << pages_[2].path().string() << endl;
            cout    << pages_[0].path().string() << (pages_[0] < pages_[2]? " < " : " > ") << pages_[2].path().string() << endl;

            cout    << "sorting" << endl;
            BOOST_FOREACH (Page p, pages_)
                cout    << p.path().string() << endl;
            sort(pages_.begin(), pages_.end());
            cout << "done sorting\n";
            BOOST_FOREACH (Page p, pages_)
                cout    << p.path().string() << endl;

            cout    << "checking datas" << endl;
            BOOST_FOREACH (Page p, pages_) {
                char data[p.size() + 1];
                strncpy((char*)&data, p.data(), p.size());
                data[p.size()] = '\0';
                cout    << p.path().string() << " " << data << endl;
            }
            cout    << "done Creating Book" << endl;
        }

        const Page& getFirstPage() { return pages_[0]; }
    private:
        deque<Page> pages_;
        fs::path path_;
};

int main() {
    Book* book = new Book("/some/path/");
    // below is an example of where the rawdata is used
    // by a method that has a char* parameter
    ofstream outFile("outimage.jpg");
    outFile.write(book->getFirstPage().data(), book->getFirstPage().size());
}

Answer 1

I wouldn't use raw char * in this scenario as it's going to be an unnecessary headache. Use std::string instead, which will remove the need for the copy constructor, assignment operator and destructor as the compiler-generated ones will be sufficient.

If you then find that copying the data is still a major bottleneck, you could use a boost::shared_ptr to hold the string if you can live with the additional level of indirection in normal use. That way, the string will not be copied if the containing object is copied and you still get the safety of RAII.

Answer 2

If using manual char* manipulation isn't part of your criteria for the exercise, you could use std::string and let it handle all the allocation issues for you. The std::swap function used by std::sort is even specialized to call std::string::swap for you, which means that it automatically only swaps the pointers to your string data rather than deep-copying.

If you want to use char* for exercise purposes, probably the easiest way to create a free-standing swap function that takes two Page references and just swaps the internal data pointers around. I believe that as long as sort can see a better match than the standard template, it will call your function instead getting the increased performance.

Finally, to answer your question about the header : Compilers are free to implement headers as actual files that include other headers (even ones that might not normally be expected). Almost certainly your iostream header is including algorithm directly or indirectly. On another compiler your code might fail to compile.