<分区>
我有一个 std::string 和一个 int 序列。我想在 int 指示的位置之前 添加字符。此操作应就地执行。例如考虑:
string: "abcde"
positions: 1, 3
character to be inserted: ' '
=> string after modification: "a bc de"
从算法上讲，在 O(n) 时间内实现它是没有问题的，但我怀疑这已经在某个地方实现了，例如 boost 。但是，我在那里找不到实现。是否有提供此功能的 C++ 库？
最佳答案
更新更新的问题包括就地操作的要求:
#include <algorithm>
#include <vector>
#include <cassert>
#include <array>
template <typename What>
void multi_insert(std::string& text, std::vector<size_t> positions, What const& insertion) {
using std::begin;
using std::end;
assert(std::is_sorted(positions.begin(), positions.end()));
auto source_n = text.length();
auto extension = insertion.size() * positions.size();
text.resize(text.length() + extension);
using Rit = std::string::reverse_iterator;
Rit dest_it = text.rbegin(),
source_it = dest_it + extension;
auto posit = positions.rbegin();
while (dest_it != source_it) {
assert(*posit <= source_n);
for (;source_n && *posit != source_n; --source_n)
*dest_it++ = *source_it++;
dest_it = std::copy(std::make_reverse_iterator(insertion.end()), std::make_reverse_iterator(insertion.begin()), dest_it);
++posit;
}
}
void multi_insert(std::string& text, std::vector<size_t> positions, char insertion = ' ') {
multi_insert(text, std::move(positions), std::array<char, 1> {{insertion}});
}
#include <iostream>
static size_t constexpr NONE = -1;
template <typename What>
void do_tests(What const& insertion) {
std::vector<size_t> p;
for (size_t a : { NONE, 0ul, 1ul, 2ul, 3ul, 4ul, 5ul })
for (size_t b : { NONE, 0ul, 1ul, 2ul, 3ul, 4ul, 5ul })
{
if (b<a)
continue;
p.assign({a,b});
p.erase(std::remove_if(p.begin(), p.end(), [](auto n) { return n == NONE; }), p.end());
std::string text = "abcde";
multi_insert(text, p, insertion);
auto opt = [](size_t n) -> char { return n==NONE?'.':('0'+n); };
std::cout << opt(a) << " " << opt(b) << " Result: '" << text << "'\n";
}
}
int main() {
do_tests('!');
do_tests(std::string("***"));
}
打印
. . Result: 'abcde'
0 . Result: '!abcde'
0 0 Result: '!!abcde'
0 1 Result: '!a!bcde'
0 2 Result: '!ab!cde'
0 3 Result: '!abc!de'
0 4 Result: '!abcd!e'
0 5 Result: '!abcde!'
1 . Result: 'a!bcde'
1 1 Result: 'a!!bcde'
1 2 Result: 'a!b!cde'
1 3 Result: 'a!bc!de'
1 4 Result: 'a!bcd!e'
1 5 Result: 'a!bcde!'
2 . Result: 'ab!cde'
2 2 Result: 'ab!!cde'
2 3 Result: 'ab!c!de'
2 4 Result: 'ab!cd!e'
2 5 Result: 'ab!cde!'
3 . Result: 'abc!de'
3 3 Result: 'abc!!de'
3 4 Result: 'abc!d!e'
3 5 Result: 'abc!de!'
4 . Result: 'abcd!e'
4 4 Result: 'abcd!!e'
4 5 Result: 'abcd!e!'
5 . Result: 'abcde!'
5 5 Result: 'abcde!!'
. . Result: 'abcde'
0 . Result: '***abcde'
0 0 Result: '******abcde'
0 1 Result: '***a***bcde'
0 2 Result: '***ab***cde'
0 3 Result: '***abc***de'
0 4 Result: '***abcd***e'
0 5 Result: '***abcde***'
1 . Result: 'a***bcde'
1 1 Result: 'a******bcde'
1 2 Result: 'a***b***cde'
1 3 Result: 'a***bc***de'
1 4 Result: 'a***bcd***e'
1 5 Result: 'a***bcde***'
2 . Result: 'ab***cde'
2 2 Result: 'ab******cde'
2 3 Result: 'ab***c***de'
2 4 Result: 'ab***cd***e'
2 5 Result: 'ab***cde***'
3 . Result: 'abc***de'
3 3 Result: 'abc******de'
3 4 Result: 'abc***d***e'
3 5 Result: 'abc***de***'
4 . Result: 'abcd***e'
4 4 Result: 'abcd******e'
4 5 Result: 'abcd***e***'
5 . Result: 'abcde***'
5 5 Result: 'abcde******'
关于c++ - 在线性时间内在给定位置将字符就地插入到字符串中，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/47055316/