an efficient c++ string

What about std::deque ?

Quote:

Original post by fabien007 It should also be fast when accessing at any position, inserting at the beginning (which would be rare) and inserting at the end (most of the case).

With these requirements, you might be best off using a std::vector< char > or simply std::string.

Quote:

I guess it would be made of linked blocks. A plus would be its ability to (also) return iovecs (to avoid useless copies).

std::vector<...> stores data contiguously, and has a size() member. std::string's data() member returns a pointer to the string data, and also has a size() member.

Linked data structures are generally not good for fast random access, and if most of your insertions occur at the end, std::vector< char > or std::string should be more than efficient, although I have no idea what your exact needs are.

Quote:

Original post by fabien007 It should also be fast when accessing at any position, inserting at the beginning (which would be rare) and inserting at the end (most of the case).

If only need to insert at the beginning and the end then it's not too hard to write a 'bidirectional' deque container.
It should be fairly easy to write considering that you only need to handle characters, i.e. no tricky placement news and exception safety.

Quote:

Original post by stylin Quote: Original post by fabien007 It should also be fast when accessing at any position, inserting at the beginning (which would be rare) and inserting at the end (most of the case). With these requirements, you might be best off using a std::vector< char > or simply std::string.

The OP wanted a reallocation free version.

Does the code need to be portable to machines without virtual memory?
One option might be to simply reserve a large contiguous portion of the address space and commit pages as needed. A better solution would be to allocate everything in native pages and reallocate by shuffling them around with the MMU.

You *cannot* avoid reallocation and also have contiguous storage - the initial block simply can't be guaranteed to fall in a region of memory where the space after it will necessarily be available later; otherwise you have effectively already reserved that space. But I don't see why you would need to avoid reallocation in a context where plain allocation (and insertion into a linked list of blocks) is OK.

It sounds though like contiguous storage may not be required for you. If std::string really doesn't do it for you, look for a rope implementation. AFAIK ropes normally are implemented with "linked blocks" of some sort.

And what is an "iovec"?

Quote:

Original post by Zahlman You *cannot* avoid reallocation and also have contiguous storage - the initial block simply can't be guaranteed to fall in a region of memory where the space after it will necessarily be available later; otherwise you have effectively already reserved that space. But I don't see why you would need to avoid reallocation in a context where plain allocation (and insertion into a linked list of blocks) is OK.

Of course you can, if you've got virtual memory. It's just one of many seemingly impossible MMU tricks (copy-on-write, memory mapped files, circular buffers, etc..).

Quote:

Original post by Zahlman It sounds though like contiguous storage may not be required for you. If std::string really doesn't do it for you, look for a rope implementation. AFAIK ropes normally are implemented with "linked blocks" of some sort.

I've only read about SGI's rope implementation, and never used it myself. It did appear to have an awful lot of overhead however, so if performance is critical there may be faster (portable) solutions available. Such as a custom bidirectional deque.

Quote:

Original post by Zahlman You *cannot* avoid reallocation and also have contiguous storage

I would like a contiguous storage only when required. Internally linked list or any kind of stucture glueing together contiguous parts of memory would be used, and a toString or c_str method would be called to copy the scattered parts into one final contiguous storage.
This temporary method would be used until applications would access the different part of memory via iovecs (thus without any copy).

Quote:

Original post by Zahlman And what is an "iovec"?

An iovec is a simple low level structure, basically:

typedef struct _iovec {
unsigned long iov_len;
char* iov_base;
} iovec;

Then it can be implemented in arrays, linked lists or whatever you like. It can be seen as the representation of a single contiguous memory zone.

Quote:

Original post by doynax Of course you can, if you've got virtual memory. It's just one of many seemingly impossible MMU tricks (copy-on-write, memory mapped files, circular buffers, etc..).

Do you know any good tutorial to learn those "MMU tricks"?