C++Talk.NET C++ language newsgroups   Archives   FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in to check your private messages   Log in  string, list<char> and deque<char>          C++Talk.NET Forum Index -> C++ Language (Moderated) View previous topic :: View next topic   Author Message Radu Grigore Guest Posted: Wed Apr 21, 2004 7:37 pm    Post subject: string, list<char> and deque<char> Are there situations when container<char> is preferable to string? Some ideas: Does container<char> work better when the size is large (e.g. 100000KB)? Is list<char> preferable when there are lots of replace operations? etc. thanks, radu [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top llewelly Guest Posted: Thu Apr 22, 2004 3:09 pm    Post subject: Re: string, list<char> and deque<char> [email]radugrigore (AT) ieee (DOT) org[/email] (Radu Grigore) writes: Quote: Are there situations when container<char> is preferable to string? [snip] Yes. Here are some rules of thumb: (a) If you find yourself using operator[], you should perfer vector<char> to string. (b) If you find yourself adding and removing individual characters, you should prefer vector<char> to string, unless the strings are quite large, in which case you should consider other containers. (c) If you find yourself using iterators, you should prefer vector<char> to string. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Michiel Salters Guest Posted: Fri Apr 23, 2004 12:09 am    Post subject: Re: string, list<char> and deque<char> [email]radugrigore (AT) ieee (DOT) org[/email] (Radu Grigore) wrote in message news:<5c77fd19.0404210501.57262e78 (AT) posting (DOT) google.com>... Quote: Are there situations when container<char> is preferable to string? Some ideas: Does container<char> work better when the size is large (e.g. 100000KB)? Is list<char> preferable when there are lots of replace operations? etc. std::vector<char> can be used to create a contiguous char[] buffer; std::strng::c_str() only has a const char* c_str(). That means any C function taking (char* buf, size_t* bufsize_in_out) is best called using &vec[0]. std::deque<char> can be useful when TCP is used to send messages, as IP framentation may not coincide with message boundaries. This is solved by a FIFO container, and deque is efficient in this regard. Regards, Michiel Salters [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Ivan Vecerina Guest Posted: Fri Apr 23, 2004 12:13 am    Post subject: Re: string, list<char> and deque<char> "Radu Grigore" <radugrigore (AT) ieee (DOT) org> wrote Quote: Are there situations when container<char> is preferable to string? Probably. For example, if you want to have a modifyable contiguous buffer, vector<char> is a portable alternative to string. ( string storage is not guaranteed to be contiguous, only the result of c_str() or data() is, and these are non-modifyable buffers). Quote: Some ideas: Does container<char> work better when the size is large (e.g. 100000KB)? Is list<char> preferable when there are lots of replace operations? list<char> would introduce a lot of storage overhead. deque<char> could be a choice if modifications occur mainly at the end (or beginning) of the buffer (e.g. when appending lots of data to a buffer). None of these is optimal for insertions/edits within the string. The SGI STL provides a container specifically targeted at handling 'edit buffers': it is called a "rope", and manages changes by referring to sub-ranges of the original data. See: http://www.sgi.com/tech/stl/Rope.html Regards, Ivan -- http://ivan.vecerina.com/contact/?subject=NG_POST <- e-mail contact form [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Yakov Lerner Guest Posted: Fri Apr 23, 2004 12:36 am    Post subject: Re: string, list<char> and deque<char> [email]radugrigore (AT) ieee (DOT) org[/email] (Radu Grigore) wrote: Quote: Are there situations when container<char> is preferable to string? Some ideas: Does container<char> work better when the size is large (e.g. 100000KB)? Is list<char> preferable when there are lots of replace operations? etc. Stlport and STL from SGI has something called "rope". The interface is similar to that of string, but performance and internal representation is completely different. SGI doc says: Note that the C++ standard does not specify the complexity of basic_string operations. In this implementation, basic_string has performance characteristics very similar to those of vector: access to a single character is O(1), while copy and concatenation are O(N). By contrast, rope has very different performance characteristics: most rope operations have logarithmic complexity. Ropes work faster than strings when the size is large and the contents changes often, but slower in other conditions. Read more at: http://www.sgi.com/tech/stl/ropeimpl.html http://www.sgi.com/tech/stl/Rope.html Yakov Lerner [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top kanze@gabi-soft.fr Guest Posted: Fri Apr 23, 2004 10:38 am    Post subject: Re: string, list<char> and deque<char> [email]radugrigore (AT) ieee (DOT) org[/email] (Radu Grigore) wrote in message news:<5c77fd19.0404210501.57262e78 (AT) posting (DOT) google.com>... Quote: Are there situations when container<char> is preferable to string? I'd phrase it differently: are there any specific cases where std::string is preferable to some container<char>? std::string is (or tries to be) a general purpose beast -- it does everything in a more or less acceptable manner, but isn't best at anything. So if you are only doing one particular thing, and need to do it well, std::string is probably NOT the correct choice. Quote: Some ideas: Does container<char> work better when the size is large (e.g. 100000KB)? std::vector<char> and std::deque<char> have guaranteed performance when growing them, std::string doesn't. std::vector<char> also guarantees contiguity of the underlying memory -- nothing else does. Quote: Is list<char> preferable when there are lots of replace operations? etc. Well, I can't think of a case off hand where I would use std::list<char>. But I probably use std::vector<char> as much as I do std::string. -- James Kanze GABI Software mailto:kanze (AT) gabi-soft (DOT) fr Conseils en informatique orientée objet/ http://www.gabi-soft.fr Beratung in objektorientierter Datenverarbeitung 9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34 [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Peter van Merkerk Guest Posted: Fri Apr 23, 2004 11:13 am    Post subject: Re: string, list<char> and deque<char> "llewelly" <llewelly.at (AT) xmission (DOT) dot.com> wrote Quote: radugrigore (AT) ieee (DOT) org (Radu Grigore) writes: Are there situations when container<char> is preferable to string? [snip] Yes. Here are some rules of thumb: (a) If you find yourself using operator[], you should perfer vector<char> to string. (b) If you find yourself adding and removing individual characters, you should prefer vector<char> to string, unless the strings are quite large, in which case you should consider other containers. (c) If you find yourself using iterators, you should prefer vector<char> to string. Forgive me my ignorance, but could you provide me with the rationale behind these rules of the thumb? Are those rules related to a particular standard library implementation? Is the goal to improve performance, to lower memory usage or is the interface of those other containers more suitable for the task? -- Peter van Merkerk peter.van.merkerk(at)dse.nl [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Ben Hutchings Guest Posted: Fri Apr 23, 2004 5:08 pm    Post subject: Re: string, list<char> and deque<char> Radu Grigore wrote: Quote: Are there situations when container<char> is preferable to string? Some ideas: Does container<char> work better when the size is large (e.g. 100000KB)? If you are appending to it repeatedly to build a large string, vector<char> may well be preferable because it grows in exponential rather than constant increments. There is no such guarantee for string; in some implementations it may grow by linear increments, which would result in quadratic time complexity. Quote: Is list<char> preferable when there are lots of replace operations? Perhaps, but list<char> is likely to use at least 12 bytes per char stored! The rope (= heavyweight string) class template from STL [1] may be more appropriate in this situation. [1] http://www.sgi.com/tech/stl/Rope.html Quote: etc. vector<char> is suitable as a writable buffer for C functions whereas string isn't. [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Radu Grigore Guest Posted: Fri Apr 23, 2004 11:15 pm    Post subject: Re: string, list<char> and deque<char> [email]jilerner (AT) yahoo (DOT) com[/email] (Yakov Lerner) wrote in message news:<4357fc34.0404220325.19ed9da3 (AT) posting (DOT) google.com>... Quote: Are there situations when container<char> is preferable to string? Stlport and STL from SGI has something called "rope". [...] Thanks to all for the useful information provided. The question was triggered by the design of a small code generation tool. It reads a data file and then it "preprocess" some templates. Two frequent operations to be done are: (1) replace a macro with some info from the data file (2) replicate parts and recursively preprocess them The first one resembles a "define", while the second resembles a "foreach". In both cases the data is taken from the data file (e.g. the lists iterated by "foreach" are in the data-file).. The performance is not an issue but rather design clarity and portability. (Therefore I do not intend to use SGI's rope.) Nevertheless, if it can be improved by using an appropriate container then I'll do it. It works like this: 1. read the data (whole file) 2. read the template (whole file) 3. for each macro 4. preprocess template (might recursively call preprocessing for other macros) More specifically, step 4 works by calling a function: T ApplyMacro(const T& input, const T& macro, Processor* proc); The function identifies each occurrence of macro in input and its corresponding parameters and replaces it with the result obtained by evaluating proc. The Processor is an abstract command. A concrete processor might in turn call ApplyMacro. The problem is to choose T. For now it is a string. Now I'll try to summarize your replies: (1) If you want contiguous memory then use vector<char>. You may want this for calling C functions that modify the string received as a char*. (Or, I may add, if you know this will be good for caching.) (2) If appending information or removing extremities are frequent operations then consider using a deque<char>. An example is when you must wait for multiple pieces of information that come from a network and concatenate them. (3) A list<char> works faster for insertions/removals in the interior but introduces space overhead. (My guess is that it is at least 5 times larger than other alternatives: sizeof(char) + 2 * sizeof(char*)). (4) Working with individual characters indicates that alternatives to string should be considered. Do you use []? Do you use iterators? do you remove/insert individual characters? (I think this can safely be generalized to: whenever you work with "slices" of the string). (5) In SGI's STLport there is a "better string" called a "rope". It behaves asymptotically faster. Quote: From your replies I have the impression that string should be preferred only for the "trivial" uses. Ah,... I almost forgot: I think I'll use a deque<char> for T. regards, radu [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Francis Glassborow Guest Posted: Sat Apr 24, 2004 12:02 am    Post subject: Re: string, list<char> and deque<char> In message <d6652001.0404220501.74827005 (AT) posting (DOT) google.com>, [email]kanze (AT) gabi-soft (DOT) fr[/email] writes Quote: radugrigore (AT) ieee (DOT) org (Radu Grigore) wrote in message news:<5c77fd19.0404210501.57262e78 (AT) posting (DOT) google.com>... Are there situations when container<char> is preferable to string? I'd phrase it differently: are there any specific cases where std::string is preferable to some container<char>? std::string is (or tries to be) a general purpose beast -- it does everything in a more or less acceptable manner, but isn't best at anything. So if you are only doing one particular thing, and need to do it well, std::string is probably NOT the correct choice. My general rule of thumb is if the object is conceptually a string I use std::string but if all I want is an array of char I use vector<char>. -- Francis Glassborow ACCU Author of 'You Can Do It!' see http://www.spellen.org/youcandoit For project ideas and contributions: http://www.spellen.org/youcandoit/projects [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Roger Orr Guest Posted: Sat Apr 24, 2004 8:40 pm    Post subject: Re: string, list<char> and deque<char> "llewelly" <llewelly.at (AT) xmission (DOT) dot.com> wrote Quote: radugrigore (AT) ieee (DOT) org (Radu Grigore) writes: Are there situations when container<char> is preferable to string? [snip] Yes. Here are some rules of thumb: (b) If you find yourself adding and removing individual characters, you should prefer vector<char> to string, unless the strings are quite large, in which case you should consider other containers. Obviously if you are adding and removing from _both_ ends deque may be best. Also there might be other, non-standard containers for particular implementations of the STL, for example www.stlport.org offers rope (a 'heavy' string) which may offer benefits particularly for large strings. HTH Roger. -- MVP in C++ at www.brainbench.com [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Radu Grigore Guest Posted: Sun Apr 25, 2004 2:01 am    Post subject: Re: string, list<char> and deque<char> Quote: (3) A list<char> works faster for insertions/removals in the interior but introduces space overhead. (My guess is that it is at least 5 times larger than other alternatives: sizeof(char) + 2 * sizeof(char*)). A correction. On most machines (sizeof(char) + 2 * sizeof(char*)) / sizeof(char) = 9. I don't remember why I said 5. regards, radu [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top kanze@gabi-soft.fr Guest Posted: Mon Apr 26, 2004 2:24 pm    Post subject: Re: string, list<char> and deque<char> llewelly <llewelly.at (AT) xmission (DOT) dot.com> wrote Quote: radugrigore (AT) ieee (DOT) org (Radu Grigore) writes: Are there situations when container<char> is preferable to string? [snip] Yes. Here are some rules of thumb: (a) If you find yourself using operator[], you should perfer vector<char> to string. (b) If you find yourself adding and removing individual characters, you should prefer vector<char> to string, unless the strings are quite large, in which case you should consider other containers. (c) If you find yourself using iterators, you should prefer vector<char> to string. So what's left:-)? I generally use std::string as the default text string. Anything that might be critical to the application, of course, gets wrapped, so that I can easily change the actual implementation later. But that is true for anything -- I would wrap an std::vector too, if it were critical to the application. -- James Kanze GABI Software mailto:kanze (AT) gabi-soft (DOT) fr Conseils en informatique orientée objet/ http://www.gabi-soft.fr Beratung in objektorientierter Datenverarbeitung 9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34 [ See http://www.gotw.ca/resources/clcm.htm for info about ] [ comp.lang.c++.moderated. First time posters: Do this! ] Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         C++Talk.NET Forum Index -> C++ Language (Moderated) All times are GMT Page 1 of 1   Jump to: Select a forum C/C++----------------C LanguageC Language (Moderated)C++ Language (Moderated)C++ language (comp.lang.c++)C++ language, library and standards Non-English C/C++ Newsgroups----------------C++ (German)C++ (French)  You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum Powered by phpBB © 2001, 2006 phpBB Group SEO toolkit © 2004-2006 webmedic.