Crius
asked on
How to append to std::string in linked list fashion?
I think this is an extremely difficult question. Urgency can be measured in months.
Background:
I work in a large company that uses std::string as its string choice. The application we code is a database application, and it often does hundreds of thousands of appends to a single string for a single report (The format we output is XML). The data in a report can be anywhere from 1k, to about 1gig. My group has developed a wrapper around this template class, but when we pass a std::string to library, we can not pass our own class, so this problem needs to somehow be handled in the std::string class itself. Maybe via the allocator object.
Problem:
The problem is, these appends slow us down because of all the allocation and string copying that must be done each append. If we could somehow have std::string store all the appends in a linked-list, and then combine it once, when we need it, this would be an ideal solution. Any speed-ups that can be provided could be helpful though.
Thoughts:
We need this in the std::string itself because this is the only object we can pass to other libraries that need to read or write to the string. While we could make sure the string was concatenated before passing it outside of our code, this is very dangerous and tedious since it's easy to forget.
Allocating more space than needed would help, but wouldn't be an ideal solution since it would hamper performance. The large range in amount of data that can be returned makes it difficult to guess how much would be good since a single append is generally anywhere from 2 bytes to 400 bytes.
I wasn't able to understand how the allocator class could be overridden since we need to combine all the data when it is needed.
Background:
I work in a large company that uses std::string as its string choice. The application we code is a database application, and it often does hundreds of thousands of appends to a single string for a single report (The format we output is XML). The data in a report can be anywhere from 1k, to about 1gig. My group has developed a wrapper around this template class, but when we pass a std::string to library, we can not pass our own class, so this problem needs to somehow be handled in the std::string class itself. Maybe via the allocator object.
Problem:
The problem is, these appends slow us down because of all the allocation and string copying that must be done each append. If we could somehow have std::string store all the appends in a linked-list, and then combine it once, when we need it, this would be an ideal solution. Any speed-ups that can be provided could be helpful though.
Thoughts:
We need this in the std::string itself because this is the only object we can pass to other libraries that need to read or write to the string. While we could make sure the string was concatenated before passing it outside of our code, this is very dangerous and tedious since it's easy to forget.
Allocating more space than needed would help, but wouldn't be an ideal solution since it would hamper performance. The large range in amount of data that can be returned makes it difficult to guess how much would be good since a single append is generally anywhere from 2 bytes to 400 bytes.
I wasn't able to understand how the allocator class could be overridden since we need to combine all the data when it is needed.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
Thank you for these feedbacks. First I would like to address some of the problems encountered with some of these solutions:
Using std::string is a company-wide mandate, and can not be changed. We were using a far more efficient string class before, but we had to change our class to derive from std::string. This can not be changed. It is not up to our smallish group. In fact, this change to std::string is what is prompting this question, otherwise, there would not be any problems.
A conversion operator was considered, but most of our calls to external code pass by reference, and I couldn't figure out how to do a concatenation during a call if we pass by reference.
An example of our append code is as follows:
(where string1, string2, and string3 are std::string)
string1 += string2;
also
string1 = string2+string3;
If we can use conversion operators to guarantee we can concantenate our string when it gets passed outside our code (by pointer, by reference, and by copy) then this would be a perfect solution!!!
We *must* derive our class from std::string however, and this brought up the problem - while we are sure our functions are the only ones used in our code, we could be assured this would not be the case when we passed our string outside of our code. Doing a dir of our *.cpp files only, we have 33 megs of code. Our string class is used everywhere, so changing the way we call external functions (we are very chatty) would not be feasible. We really need an automatic way of doing it without changing the interface/calling.
A block allocator would help, but as stated in my original problem, we don't want to use much more memory than needed, and we use a ton of strings, and their sizes differ greatly. A linked list is a great way to go, and std::list is basically this. If only we could use this instead of std::string.
There are many great solutions out there, but we must use std::string. It's a flexible class it seems, although I really don't understand how it works. I am hoping there's a way to have std::string behave more like a linked list in implementation.
Using std::string is a company-wide mandate, and can not be changed. We were using a far more efficient string class before, but we had to change our class to derive from std::string. This can not be changed. It is not up to our smallish group. In fact, this change to std::string is what is prompting this question, otherwise, there would not be any problems.
A conversion operator was considered, but most of our calls to external code pass by reference, and I couldn't figure out how to do a concatenation during a call if we pass by reference.
An example of our append code is as follows:
(where string1, string2, and string3 are std::string)
string1 += string2;
also
string1 = string2+string3;
If we can use conversion operators to guarantee we can concantenate our string when it gets passed outside our code (by pointer, by reference, and by copy) then this would be a perfect solution!!!
We *must* derive our class from std::string however, and this brought up the problem - while we are sure our functions are the only ones used in our code, we could be assured this would not be the case when we passed our string outside of our code. Doing a dir of our *.cpp files only, we have 33 megs of code. Our string class is used everywhere, so changing the way we call external functions (we are very chatty) would not be feasible. We really need an automatic way of doing it without changing the interface/calling.
A block allocator would help, but as stated in my original problem, we don't want to use much more memory than needed, and we use a ton of strings, and their sizes differ greatly. A linked list is a great way to go, and std::list is basically this. If only we could use this instead of std::string.
There are many great solutions out there, but we must use std::string. It's a flexible class it seems, although I really don't understand how it works. I am hoping there's a way to have std::string behave more like a linked list in implementation.
ASKER
jkr,
If you could supply me with the conversion operators that would automatically be called when we are calling a function with the std::string as an argument, I would be very happy to award you an A.
We need to handle the following 3 possibilities:
1) Passed by value
2) Passed by reference
3) Passed by pointer
Passed by value can be done via a custom copy constructor.
How do I do the other two?
If you could supply me with the conversion operators that would automatically be called when we are calling a function with the std::string as an argument, I would be very happy to award you an A.
We need to handle the following 3 possibilities:
1) Passed by value
2) Passed by reference
3) Passed by pointer
Passed by value can be done via a custom copy constructor.
How do I do the other two?
ASKER
Oops, also for anthony_w - it looks like this is the way to go...
Since we are required to derive our class from std::string... Well, will a str::string conversion operator still work? Will it be called, or will the compiler just say, "Hey, you're already a std::string, so I won't call the conversion operator?".
Since we are required to derive our class from std::string... Well, will a str::string conversion operator still work? Will it be called, or will the compiler just say, "Hey, you're already a std::string, so I won't call the conversion operator?".
ASKER
After some tinkering and testing I was able to prove that the compiler will not call a user-defined conversion operator if the object is already what you want.
IE: Creating a class that inherits from std::string will cause any std::string conversion operators in the class to never be called.
I admit this question was far too specific with too many restrictions placed on it:
1) I have to inherit from std::string.
2) I need to pass my string class to outside functions.
3) I want it to have fast appending, like a linked-list can provide.
As such, I doubt there is a solution. I will split the points according to how much effort I felt were put in. It's unfortunate most of my questions get the answer of "It can't be done" in the end, but I admit, I would have been shocked if someone had come up with a way to do this.
IE: Creating a class that inherits from std::string will cause any std::string conversion operators in the class to never be called.
I admit this question was far too specific with too many restrictions placed on it:
1) I have to inherit from std::string.
2) I need to pass my string class to outside functions.
3) I want it to have fast appending, like a linked-list can provide.
As such, I doubt there is a solution. I will split the points according to how much effort I felt were put in. It's unfortunate most of my questions get the answer of "It can't be done" in the end, but I admit, I would have been shocked if someone had come up with a way to do this.
>>copying that must be done each append.
IMHO, you should cosider addressing this differently all together.
I recommend you try using std::list<std::string> instead.
Exactly how are you appending the data?
Do you have example code?
It might be that you just need to tweek the append code.