C语言 前置到字符串
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2328182/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Prepending to a string
提问by Ryan
What is the most efficient way to prepend to a C string, using as little memory as possible?
使用尽可能少的内存添加到 C 字符串的最有效方法是什么？
I am trying to reconstruct the path to a file in a large directory tree.
我正在尝试重建大型目录树中文件的路径。
Here's an idea of what I was doing before:
这是我之前在做什么的想法：
char temp[LENGTH], file[LENGTH];
file = some_file_name;
while (some_condition) {
parent_dir = some_calculation_that_yields_name_of_parent_dir;
sprintf(temp, "%s/%s", parent_dir, file);
strcpy(file, temp);
}
This seems a bit clunky though.
不过，这似乎有点笨拙。
Any help would be appreciated. Thanks!
任何帮助，将不胜感激。谢谢！
采纳答案by Eli Bendersky
Copying can hardly be avoided if you want it in the same memory chunk. If the allocated chunk is large enough you coulduse memmoveto shift the original string by the length of what you want to prepend and then copy that one into the beginning, but I doubt this is less "clunky". It would however save you extra memory (again, granted that the original chunk has enough free space for them both).
如果您希望它在同一个内存块中，则几乎无法避免复制。如果分配的块足够大，您可以使用memmove您想要添加的长度来移动原始字符串，然后将该字符串复制到开头，但我怀疑这不那么“笨拙”。然而，它会为您节省额外的内存（同样，假设原始块有足够的可用空间供它们使用）。
Something like this:
像这样的东西：
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
void prepend(char* s, const char* t);
/* Prepends t into s. Assumes s has enough space allocated
** for the combined string.
*/
void prepend(char* s, const char* t)
{
size_t len = strlen(t);
memmove(s + len, s, strlen(s) + 1);
memcpy(s, t, len);
}
int main()
{
char* s = malloc(100);
strcpy(s, "file");
prepend(s, "dir/");
printf("%s\n", s);
return 0;
}
回答by Zan Lynx
If you don't need the string to be stored in order, but only appearto be in order, then use a thing called a "rope." (It's made of lots of "string", see.)
如果您不需要按顺序存储字符串，而只需要按顺序存储，则使用称为“绳索”的东西。（它由许多“字符串”组成，请参阅。）
I believe it's basically a vector (in C terms, an array) of struct { char *begin; char *end };
我相信它基本上是一个向量（用 C 术语来说，一个数组） struct { char *begin; char *end };
In C++ it implements all the std::string functions. In C you'd need to write (or get a library of) replacement functions for all the strxxx() functions.
在 C++ 中，它实现了所有 std::string 函数。在 C 中，您需要为所有 strxxx() 函数编写（或获取）替换函数。
What the "rope" would do to prepend a string to another string is simply insert a new begin,end pair pointing at the new piece of string. It might also have to copy the new piece of string, if it's a temporary pointer. Or it can just take ownership of the string if it's an allocated string.
“绳子”将一个字符串添加到另一个字符串之前所做的只是插入一个新的开始，结束对，指向新的字符串。如果它是一个临时指针，它可能还必须复制新的字符串。或者，如果它是一个分配的字符串，它就可以拥有该字符串的所有权。
A rope is very good for large strings. But anything under about 8 KB is faster to handle with memmove and memcpy.
绳子非常适合大弦。但是使用 memmove 和 memcpy 处理大约 8 KB 以下的任何内容都更快。
回答by Jay
sprintf() is generally not 'fast'. Since you know it's pre-pending memmove() twice would probably be preferable for speed.
sprintf() 通常不是“快”。因为你知道它预先挂起 memmove() 两次可能会更好地提高速度。
If you're allocating the strings with malloc() originally you might consider using realloc() to resize the character arrays so they can contain the new string.
如果您最初使用 malloc() 分配字符串，您可能会考虑使用 realloc() 调整字符数组的大小，以便它们可以包含新字符串。
char* p = malloc( size_of_first_string );
...
p = realloc( p, size_of_first_string + size_of_prepended_string + 1 );
memmove( p + size_of_prepended_string, p, size_of_first_string );
memmove( p, prepended_string, size_of_prepended_string );
回答by Joel
You can climb to the top of the directory tree keeping the names as you go along, then paste the names together all at once. At least then you aren't doing unnecessary copies by pushing onto the front.
您可以爬到目录树的顶部，同时保留名称，然后一次性将名称粘贴在一起。至少那样你不会通过推到前面来做不必要的副本。
int i = 0;
int j;
char temp*[MAX_DIR_DEPTH], file[LENGTH];
while (some_condition) {
temp[i++] = some_calculation_that_yields_name_of_parent_dir;
}
char *pCurrent = file;
for( j = i-1; j > 0; j-- )
{
strcpy(pCurrent, temp[j]);
pCurrent += strlen(temp[j]);
*pCurrent++ = '\';
}
strcpy(pCurrent, filename);
*pCurrent = 0;
回答by Thomas Matthews
Perhaps I'm confused, but I believe that a prepend is the same as appending with the strings swapped. So instead of prepending"Hello" to "World", the string "World" can be appendedto "Hello":
也许我很困惑，但我相信前置与交换字符串后附加相同。因此，而不是前面加上“你好”到“世界”，字符串“世界”可以追加为“Hello”：
const char world[] = "World";
const char hello[] = "Hello";
// Prepend hello to world:
const unsigned int RESULT_SIZE = sizeof(world) + sizeof(hello) + 2 * sizeof('[] [] [] [] [] [f] [o] [o] [.] [t] [x] [t] [[] [] [] [a] [/] [f] [o] [o] [.] [t] [x] [t] [char temp[LENGTH], file[LENGTH];
int lastEmpty = put_at_end(some_file_name, file);
// lastEmpty points to right most empty slot
while (some_condition) {
parent_dir = some_calculation_that_yields_name_of_parent_dir;
int len = strlen(parent_dir);
char *tmp = parent_dir + len -1;
while (lastEmpty > 0) {
file[lastEmpty] = *tmp;
lastEmpty --;
tmp--;
}
}
]
^
|
lastEmpty
]
^
|
lastEmpty
');
char * result = malloc(RESULT_SIZE);
if (result)
{
strcpy(result, hello);
strcat(result, world);
puts("Result of prepending hello to world: ");
puts(result);
puts("\n");
}
Also, the main waste of execution time is finding the end of a string. If the strings were stored with the length, the end could be calculated faster.
此外，执行时间的主要浪费是查找字符串的结尾。如果字符串与长度一起存储，则可以更快地计算结尾。
回答by Thomas Matthews
You could maintain the string starting from the end. Since you seem to know the maxSize already...
您可以从末尾开始维护字符串。由于您似乎已经知道 maxSize ......
So basically if file initially was (foo.txt)
所以基本上如果文件最初是 (foo.txt)
void GetFilename(char *pFile)
{
strcpy(pFile, "someFile");
}
void GetParentDir(char *pDir)
{
strcpy(pDir, "/parentdir");
}
int _tmain(int argc, _TCHAR* argv[])
{
char path[1024];
GetParentDir(path);
int dirSize = strlen(path);
path[dirSize] = '/';
GetFilename(path + dirSize + 1);
printf(path);
return 0;
}
Now if you add a parent dir a/ it will look like
现在，如果您添加父目录 a/ 它看起来像
#define BUFSIZE 256
#define LEFTBUF 20
struct mstring
{
char * string;
unsigned s;
unsigned e;
}
void checkbuf(struct mstring *value, int newstringlen, char leftorright)
{
//have fun here
}
char * concat (struct mstring * value, char * str)
{
checkbuf(value, strlen(value,str), 'r');
int i=0;
while (str[i])
value->string[value->e++]=str[i++];
}
char * set(struct mstring * value, char * str)
{
value->e=LEFTBUF;
value->s=LEFTBUF;
concat( value,str);
}
char * prepend (struct mstring * value, char * str)
{
checkbuf(value, strlen(value,str), 'l');
int i=strlen(value,str)-1;
while (i>=0)
value->string[--value->s]=str[i--];
}
int main()
{
struct mstring * mystring= (struct mstring *) malloc(sizeof(struct mstring) );
mystring->string=(char*)malloc(sizeof(char)*BUFSIZE);
set( mystring,"World");
prepend(mystring,"Hallo")
}
So the code will look something like (there might be bugs, but you get the idea).
所以代码看起来像（可能有错误，但你明白了）。
##代码##Since I suppose we could expect parent_dir to be small, going over it twice should be ok. If you want to pass around the file string, you can just use file+lastEmpty+1.
因为我想我们可以期望 parent_dir 很小，所以两次应该没问题。如果你想传递文件字符串，你可以使用file+lastEmpty+1.
回答by David Gladfelter
This solution has no more copying than necessary. It does require one strlen, so if the directory name retrieval can return the number of bytes copied or if you can precalculate the parent dir string length, you can optimize that away.
此解决方案没有多余的复制。它确实需要一个 strlen，因此如果目录名称检索可以返回复制的字节数，或者如果您可以预先计算父目录字符串长度，则可以对其进行优化。
##代码##回答by jurhas
I leave a buffer at left and at right of the array. You have to hold two index but if you have to do it a lot of times (otherweise there would be no problem for efficency) it worts it. The two index I suggest to be ]s;e], one included and one not:
我在数组的左侧和右侧留下了一个缓冲区。你必须持有两个索引，但如果你必须多次这样做（否则效率不会有问题）它会起作用。我建议的两个索引是 ]s;e]，一个包含，一个不包含：
##代码##then you have to prepare a function for fill substrings...
那么你必须准备一个函数来填充子字符串......
