数据结构—字符串

文章目录

  • 7.字符串
    • (1).字符串及其ADT
      • #1.基本概念
      • #2.ADT
    • (2).字符串的基本操作
      • #1.求子串substr
      • #2.插入字符串insert
      • #3.其他操作
    • (3).字符串的模式匹配
      • #1.简单匹配(Brute-Force方法)
      • #2.KMP算法
        • I.kmp_match()
        • II.getNext()
      • #3.还有更多
    • 小结
    • 附录:我自己写的string

7.字符串

  字符串几乎算得上是我们平时最常用的数据结构了,比如你看到的这篇博客,它也是由一系列的字符组成的。说实话,字符串相关的问题其实多的非常离谱,并且往后的各种问题也非常复杂。

  我们可以举这么一个例子,假设我给你一段C语言的代码:

#include <stdio.h>
int main()
{
    int a = 0;
    scanf("%d", &a);
    printf("%d\n", a + 10);
    return 0;
}

  这一段代码在你眼里看来是代码,但是在gcc看来,就是一串可能包含代码的字符串,经过处理之后,我们需要把这段代码解析成下面正确的汇编代码,从而经过之后的链接器等完成最终可执行文件的生成操作,而读入代码,生成汇编文件这个过程就涉及到了有限自动机(FAM) 这个模型,它将一个系统分成若干可数个离散的状态,在识别到特定模式后,进行对应的跳转,最终再进行判断。

        .file   "a.c"
        .text
        .section        .rodata.str1.1,"aMS",@progbits,1
.LC0:
        .string "%d"
.LC1:
        .string "%d\n"
        .text
        .globl  main
        .type   main, @function
main:
.LFB11:
        .cfi_startproc
        subq    $24, %rsp
        .cfi_def_cfa_offset 32
        movl    $0, 12(%rsp)
        leaq    12(%rsp), %rsi
        movl    $.LC0, %edi
        movl    $0, %eax
        call    __isoc99_scanf
        movl    12(%rsp), %eax
        leal    10(%rax), %esi
        movl    $.LC1, %edi
        movl    $0, %eax
        call    printf
        movl    $0, %eax
        addq    $24, %rsp
        .cfi_def_cfa_offset 8
        ret
        .cfi_endproc
.LFE11:
        .size   main, .-main
        .ident  "GCC: (GNU) 13.2.0"
        .section        .note.GNU-stack,"",@progbits

  而字符串的操作还远不止这些,关于有限自动机以及编译器的实现细节等内容,你将会在未来的编译原理课程中学到(当然是你们学校开的课,我还没有写编译原理博客的计划),在这一篇当中,我们会介绍字符串的ADT,基本操作,以及两种常用的字符串模式匹配算法

(1).字符串及其ADT

#1.基本概念

  假设V是程序语言所使用的字符集,由字符集V中的字符所组成的任何有限序列,称为字符串

不包含任何字符的字符串称为空字符串,而字符串的长度即为一个字符串所包含的字符个数;某个串的子串则是这个串中任意一个连续的子序列

  所以字符串也是一种线性表,其中的每个元素都是一个字符,这样我们用数组和链表理论上讲都是可以实现字符串的,不过通常情况下,我们会采取顺序存储的方式来实现字符串,因为有些算法可能涉及到随机访问,所以用顺序存储会方便些

#2.ADT

  具体的我就不提了,这里就说一说关于字符串的一些操作:

  • 创建、赋值、拷贝、清空、销毁
  • 串互相比较
  • 求串的长度
  • 连接两个字符串
  • 取出字符串的子串
  • 判断是否为空串
  • 子串替换、插入、删除

  接下来我们就来看看这些基本操作的实现方式。

(2).字符串的基本操作

  这里的字符串的容器采取STL vector实现,具体你可以试着自己写一写,我在GitHub上开源了一个MySTL,其中有基于vector<T>的basic_string<T>实现:MySTL-Voltline

#1.求子串substr

  求子串其实还挺简单的,只是有一些边界情况需要考虑,比如beg < end,beg、end > 0,end < _size这样,所以就可以得到以下的代码:

string substr(int beg, int end) const
{
    if (beg < 0) beg = 0;
    if (end > _size) end = _size;
    vector<char> vc;
    for (int i = beg; i <= end; i++) {
        vc.push_back(container[i]);
    }
    return string{ vc };
}

  还有一种子串的取法则是从位置i开始取j个字符形成子串,这个实现方法其实没什么太大的区别,你可以自己尝试实现。

#2.插入字符串insert

  这个函数其实和线性表向其中某个位置插入指定个数的元素的操作差不多,所以我们也可以很快地写出下面的代码:

string insert(const string& s1, int pos)
{
    if (pos > _size) pos = _size;
    else if (pos < 0) pos = 0;

    container.resize(_size + s1.size() + 100);
    // 给容器直接扩容,避免之后再挪动的时候出现越界访问的问题

    int mov = s1.size();

    for (int i = _size-1; i >= pos; i--) {
        container[i + mov] = container[i]; 
    }
    for (int i = pos; i < mov; i++) {
        container[i] = s1.container[i - pos];
    }
    return *this;
}

#3.其他操作

  其他操作真的很简单,比如concat,如果操作的是vector,一个个push_back就好了,这些操作还是自己实现一下吧。

(3).字符串的模式匹配

  什么是模式匹配呢,听起来有点复杂,不过其实很简单,就是依照查找子串的事情,比如:在hellowbabababbabbba中找到babb

#1.简单匹配(Brute-Force方法)

怎么找呢?很自然的想法就是一个个去遍历,比如这样:

int find_bf(const string& t, const string& p, int pos)
{
    int i{ pos }, j{ 0 };
    int n = t.size(), m = p.size();
    while (i < n && j < m) {
        if (t[i] == p[i]) { 
            i++, j++;
        }
        else {
            i += 1-j;
            j = 0;
        }
    }
    if (j == m) return i - m;
    else return -1;
}

  很简单,每到一个字符就往后匹配一次,匹配不上就继续遍历,如果匹配上了就直接返回,这样就好了

  假设正文字符串长度为n模式字符串长度为m,那么这个匹配方式的时间复杂度是 O ( n m ) O(nm) O(nm),如果模式串和正文串长度差不多,这个匹配方式的时间复杂度就会退化到 O ( n 2 ) O(n^2) O(n2)的时间复杂度,这有点太慢了。

#2.KMP算法

  Knuth,Morris和Pratt共同提出了一种全新的模式匹配算法,这个算法能够在 O ( n + m ) O(n+m) O(n+m)的线性时间复杂度内完成字符串的模式匹配。

  我们先来思考一下,Brute-Force方法到底有什么问题,比如t = abababcbababba,p = ababc,BF方法是这样:
p12

  我们会发现,p和t在第一次匹配的时候,前面的abab都已经匹配上了,只有c和a发生了失配,而因为失配,第二次我们把整个字符串往后挪动一次匹配,还得从a开始,这样我们貌似忘记了前面四个字符是匹配的了

  如果我们试着看看t可能可以发现这么一件事,出现的第二个ab后面又是a,而在字符串p中,第一个ab后出现的也是a,所以如果我们的p可以这么跳转:
p13

  只让p对应的那个指针动,动到刚才我们发现的"aba"的地方,就可以去掉第二次匹配,这个例子举的可能差距不大,我们把t变成abababababcbab,那么情况就会变成这样:
p14

  比较次数明显减少!所以KMP算法的核心就在于:如何找到模式字符串本身具备的特性,通过它本身的性质得到一个失配跳转值,从而尽可能增加每一次模式字符串跳转的字符数,从而大大减少重复匹配的次数,接下来我们来具体提一提怎么实现KMP算法

I.kmp_match()

  这次我打算先介绍一下,我们如何通过这个想法进行匹配,假设我们已经获得了对于模式字符串的next数组(这个等会儿再来看怎么实现),接下来要对正文串t和模式串p进行匹配,那么基于前面我们说的想法:在匹配的时候就继续前进,失配的时候根据失配跳转值让p向前跳,如果到第一个字符还是失配,那就不可能在现在已经走过的字符里找到能匹配的了,这时候只要让t的指针往后跳一个就行了,所以我们可以得出下面的代码:

struct chars
{
    char c;  // 字符
    int idx; // 跳转值
};

int kmp(const string& t, const string& p)
{
    int ans{ -1 };
    vector<chars> next = getNext(p);
    int t_size = t.size(), p_size = p.size();
    int i{ 0 }, j{ 0 };
    while (i < t_size) {
        if (j == -1 || t[i] == p[j]) {
            i++, j++;
        }
        else {
            if (j < p_size) j = next[j].idx;
        }

        if (j == p_size) {
            ans = i - j;
            break;
        }
    }
    return ans;
}

  我们首先用getNext()函数获得next数组,然后进行基于next数组的匹配,next数组的数据模式如下:第一个字符对应的值为-1,其他的字符对应的值则是对应字符失配时的跳转值,如果找到的next值是-1,就让指向正文串的"指针"i向后移动一位,否则就让指向模式串的"指针"j移动到next[j]的位置上去。

  那么接下来,我们就来看看这个getNext()函数怎么写的吧!

II.getNext()

  首先说一说前缀后缀的概念,前缀就是自第一个字符起的所有连续子串,后缀就是自最后一个字符起的所有连续子串,提到前缀和后缀主要是为了引入next的计算原理。

  接下来我们来看看next数组是怎么生成的,next数组的跳转顺序基于这样一个规则:当失配发生时,失配字符a的上一个字符b对应的某一个子串S在不包含当前子串的最长前缀中,子串S最后一次出现的位置中,字符b的位置,有点拗口,我们来详细地解释一下,例如:p = abcabd,我们找next的规则就是基于每个下一个字符都有可能是失配字符来做的,那么我们可以得到下面的一张表:
p15

  a首先是-1没问题,b去往前找,只有a,那就赋为0吧。之后是c,往前找一个字符是b,它对应的idx是0,next[0]是a,a和b并不匹配,那就继续往前走,字符a对应的idx是-1,这时候就结束了,我们让c的idx为a的idx+1,也就是0。

  然后又是b,b前面一个字符是a,而a在前面的字符中出现过,在第0个,因此当这个b失配的时候,下一次我们可以试着从它前面一个字符出现的上一次的后面一个字符继续匹配,很显然,a在0出现了,后面一位是1,所以b就赋为1了。

  最后是d,d前面一个字符是b,而b上一次出现在数组中是1,那么d失配的时候,b满足,就跳转到上一次出现的b的后面一位,也就是c,对应的是2,所以d就赋为2了。

  然后我们就走完了全程,你发现了,虽然我们是在做子串和前缀的重叠匹配,但是实际上,因为每个字符的上一个字符总是已经包含了之前字符的重叠情况,因此我们只需要考虑当前这个字符是不是匹配就好了,这其实也能算是一种动态规划的思想,因为我们让每一次字符的查找都变得有用了起来,每一次下一个字符的查找都基于上一个查找的结果来确定,因此查找的过程就变得简单了起来:

  • 1.到了某一个字符c,先看看这个字符的前一个字符
  • 2.如果这个字符的前一个字符b和b自己的next值对应的字符相同,那就让c的next值等于b的next值+1(允许你从上一次b出现的后面一个字符开始匹配)
  • 3.如果这个字符的前一个字符b和b自己的next值对应的字符不相同,那就让继续找到b的next值对应的字符对应的next值,继续往前找,直到找到一个匹配的字符,或者找到第一个字符(对应的next值为-1),如果找到匹配的字符,则类似2操作,让c的next值等于找到的这个字符的位置+1;否则就赋值为0,对应最前的字符

  很好,那代码就很好写了:

vector<chars> getNext(const string& sub_str)
{
    vector<chars> next;
    size_t sub_str_size{ sub_str.size() };
    next.push_back(chars{ sub_str[0], -1 });
    for (size_t i = 1; i < sub_str_size; i++) {
        next.push_back(chars{ sub_str[i], 0 });
    }
    for (size_t i = 1; i < sub_str_size; i++) {
        if (next[i - 1].idx != -1 && next[i - 1].c == next[next[i - 1].idx].c) {
            next[i].idx = next[i - 1].idx + 1;
        }
        else {
            int j = next[i - 1].idx;
            while (j != -1 && next[j].c != next[i - 1].c) {
                j = next[j].idx;
            }
            next[i].idx = j + 1;
        }
    }
    return next;
}

  我这里next存的是一个叫做chars的结构体,它对应的结构是这样:

struct chars
{
    char c;  // 字符
    int idx; // 跳转值
};

  其实你只存这个idx也是可以的,你可以稍微改改,有一个特别需要注意的点:

    for (size_t i = 1; i < sub_str_size; i++) {
        next.push_back(chars{ sub_str[i], 0 });
    }

  这个数组在初始化的时候,我们把所有后续字符的idx值都赋为0,如果没有后续的操作,这个情况如果调用kmp_match函数的匹配过程就会和前面说的Brute-Force方式完全一样了,所以后续的找next过程还是非常重要的呢!那么KMP算法其实到这里基本上就结束了,我们会发现,如果真的理解了它的做法,其实感觉还挺简单的,实际上就是一个动态规划的思想,很多动态规划的问题也是这样,其实想出来之后它的思路并不复杂,但是要想到这个思路的过程是相当困难的。

#3.还有更多

  其实字符串的匹配方式还有很多很多,例如BM算法等,因为时间的限制,在这里我就不做过多介绍了。

小结

  字符串这一篇,相当的短啊哈哈哈哈哈哈,毕竟这一部分在数据结构中我们主要还是以掌握KMP算法为主,毕竟它在模式匹配上表现出的时间复杂度 O ( n + m ) O(n+m) O(n+m)是非常优秀的。下一篇我们将会介绍一系列内部排序的算法。
  然后,我会在下面给出我写过的MySTL中的basic_string的代码,仅供参考,如果你发现了什么bug,一定要告诉我哦!这对我帮助很大!

附录:我自己写的string

#pragma once
#include <iostream>
#include <cstring>
#include "vector.h"

namespace MySTL 
{
	template <typename T>
	class basic_string
	{
	private:
		vector<T> container;
		size_t _size;
	public:
		using iterator = T*;
		using const_iterator = const T*;
		inline static size_t npos = -1;
	public:
		basic_string();
		basic_string(const char* _c_str);
		basic_string(const char* _c_str, size_t _size);
		basic_string(const char* _c_str, size_t _begin, size_t _size);
		basic_string(size_t _size, char c);
		basic_string(const basic_string<T>& _str);
		basic_string(basic_string<T>&& _mv_str) noexcept;
		basic_string(std::initializer_list<T> l);
		~basic_string();

		basic_string<T>& operator=(const basic_string<T>& _Right);
		basic_string<T>& operator=(basic_string<T>&& _Right) noexcept;
		basic_string<T>& operator=(const char* _str);
		basic_string<T>& operator=(char c);

		basic_string<T> operator+(const basic_string<T>& _Right);
		basic_string<T> operator+(const char* _str);
		basic_string<T> operator+(char c);

		basic_string<T>& operator+=(const basic_string<T>& _Right);
		basic_string<T>& operator+=(const char* _str);
		basic_string<T>& operator+=(char c);

		T& operator[](size_t _index);
		const T& operator[](size_t _index) const;
		T& at(size_t _index);

		bool operator==(const basic_string<T>& _Right);
		bool operator!=(const basic_string<T>& _Right);
		bool operator>(const basic_string<T>& _Right);
		bool operator<(const basic_string<T>& _Right);
		bool operator>=(const basic_string<T>& _Right);
		bool operator<=(const basic_string<T>& _Right);

		bool operator==(const char* _c_Right);
		bool operator!=(const char* _c_Right);
		bool operator>(const char* _c_Right);
		bool operator<(const char* _c_Right);
		bool operator>=(const char* _c_Right);
		bool operator<=(const char* _c_Right);

		size_t size() const noexcept;
		size_t capacity() const noexcept;
		bool empty() const noexcept;
		const T* data();
		const T* c_str();
		iterator begin();
		iterator end();
		const_iterator begin() const;
		const_iterator end() const;

		void reserve(size_t new_capacity_size);
		void resize(size_t new_elem_size);
		void clear();
		void erase(const size_t _Where);
		void erase(const size_t _Off, const size_t _Count);
		void erase(iterator _begin, iterator _end);
		void erase(iterator _pos);

		void append(size_t _Count, char c);
		void append(const basic_string<T>& _str);
		void append(const basic_string<T>& _str, size_t _Begin = 0);
		void append(const basic_string<T>& _str, size_t _Begin, size_t _Count);
		void append(const char* _str);
		void append(const char* _str, size_t _Begin);
		void append(const char* _str, size_t _Begin, size_t _Count);
		void append(std::initializer_list<char> l);
		void push_back(char c);

		size_t find(char c, size_t _begin_pos = 0);
		size_t find(const char* _str, size_t _begin_pos = 0);
		size_t find(const basic_string<T>& _str, size_t _begin_pos = 0);

		void swap(basic_string<T>& _Right);

		template<typename U>
		friend std::ostream& operator<<(std::ostream& output, const basic_string<U>& _str)
		{
			for (auto& i : _str) {
				output << i;
			}
			return output;
		}

		template<typename U>
		friend std::istream& operator>>(std::istream& input, basic_string<U>& _str)
		{
			_str.clear();
			U c = input.get();
			while (c != ' ' && c != '\n' && c != '\t') {
				_str.push_back(c);
				c = input.get();
			}
			return input;
		}
	};

	template<typename T>
	basic_string<T>::basic_string()
	{
		container = vector<unsigned char>{};
	}

	template<typename T>
	basic_string<T>::basic_string(const char* _c_str)
	{
		size_t length{ strlen(_c_str) };
		_size = length;
		container = vector<T>();
		for (size_t i = 0; i < length; i++) {
			container.push_back(*(_c_str + i));
		}
		container.push_back('\0');
	}

	template<typename T>
	basic_string<T>::basic_string(const char* _c_str, size_t _size)
	{
		size_t length{ _size };
		if (_size > strlen(_c_str)) {
			length = strlen(_c_str);
		}

		_size = length;
		container = vector<T>();
		for (size_t i = 0; i < length; i++) {
			container.push_back(*(_c_str + i));
		}
		container.push_back('\0');
	}

	template<typename T>
	basic_string<T>::basic_string(const char* _c_str, size_t _begin, size_t _size)
	{
		size_t c_str_len{ strlen(_c_str) };
		container = vector<T>();
		if (_begin > c_str_len) {
			_size = 0;
		}
		else {
			size_t length{ _size };
			if (_size > strlen(_c_str + _begin)) {
				length = strlen(_c_str + _begin);
			}

			_size = length;
			for (size_t i = _begin; i < length; i++) {
				container.push_back(*(_c_str + i));
			}
			container.push_back('\0');
		}
	}

	template<typename T>
	basic_string<T>::basic_string(size_t _size, char c)
	{
		container = vector<T>(_size, c);
		_size = _size;
	}

	template<typename T>
	basic_string<T>::basic_string(const basic_string<T>& _str)
	{
		container = vector<T>(_str.container);
		_size = _str._size;
	}

	template<typename T>
	basic_string<T>::basic_string(basic_string<T>&& _mv_str) noexcept
	{
		container = std::move(_mv_str.container);
		_size = _mv_str._size;
		_mv_str.container = vector<T>{};
	}

	template<typename T>
	basic_string<T>::basic_string(std::initializer_list<T> l)
	{
		container = vector<T>(l.size() + 128);
		_size = l.size();
		for (auto it = l.begin(); it != l.end(); it++) {
			container.push_back(static_cast<T>(*it));
		}
		container.push_back('\0');
	}

	template<typename T>
	basic_string<T>::~basic_string()
	{
		_size = 0;
		container.~vector();
	}

	template<typename T>
	basic_string<T>& basic_string<T>::operator=(const basic_string<T>& _Right)
	{
		container.~vector();
		container = _Right.container;
		_size = _Right._size;
		return *this;
	}

	template<typename T>
	basic_string<T>& basic_string<T>::operator=(basic_string<T>&& _Right) noexcept
	{
		container.~vector();
		container = std::move(_Right.container);
		_size = _Right._size;
		return *this;
	}

	template<typename T>
	basic_string<T>& basic_string<T>::operator=(const char* _str)
	{
		container.~vector();
		size_t length{ strlen(_str) };
		container = vector<T>(length + 128);
		_size = 0;
		for (size_t i = 0; i < length; i++) {
			container.push_back(_str[i]);
			_size++;
		}
		return *this;
	}

	template<typename T>
	basic_string<T>& basic_string<T>::operator=(char c)
	{
		clear();
		push_back(c);
		return *this;
	}

	template<typename T>
	basic_string<T> basic_string<T>::operator+(const basic_string<T>& _Right)
	{
		basic_string<T> temp{ *this };
		for (auto& i : _Right) {
			temp.push_back(i);
		}
		return temp;
	}

	template<typename T>
	basic_string<T> basic_string<T>::operator+(const char* _str)
	{
		basic_string<T> temp{ *this };
		size_t length{ strlen(_str) };
		for (size_t i = 0; i < length; i++) {
			temp.push_back(_str[i]);
		}
		return temp;
	}

	template<typename T>
	basic_string<T> basic_string<T>::operator+(char c)
	{
		basic_string<T> temp{ *this };
		temp.push_back(c);
		return temp;
	}

	template<typename T>
	basic_string<T>& basic_string<T>::operator+=(const basic_string<T>& _Right)
	{
		for (auto& i : _Right) {
			push_back(i);
		}
		return *this;
	}

	template<typename T>
	basic_string<T>& basic_string<T>::operator+=(const char* _str)
	{
		size_t length{ strlen(_str) };
		for (size_t i = 0; i < length; i++) {
			push_back(_str[i]);
		}
		return *this;
	}

	template<typename T>
	basic_string<T>& basic_string<T>::operator+=(char c)
	{
		push_back(c);
		return *this;
	}

	template<typename T>
	T& basic_string<T>::operator[](size_t _index)
	{
		return container[_index];
	}

	template<typename T>
	const T& basic_string<T>::operator[](size_t _index) const
	{
		return container[_index];
	}

	template<typename T>
	T& basic_string<T>::at(size_t _index)
	{
		if (_index <= _size) {
			return container[_index];
		}
		else {
			throw std::out_of_range("Index Out of Range");
		}
	}

	template<typename T>
	bool basic_string<T>::operator==(const basic_string<T>& _Right)
	{
		if (_size != _Right._size) {
			return false;
		}
		else {
			for (size_t i = 0; i < _size; i++) {
				if (container[i] != _Right[i]) return false;
			}
			return true;
		}
	}

	template<typename T>
	bool basic_string<T>::operator!=(const basic_string<T>& _Right)
	{
		return !(*this == _Right);
	}

	template<typename T>
	bool basic_string<T>::operator>(const basic_string<T>& _Right)
	{
		size_t min_size{ _size < _Right.size() ? _size : _Right.size() };
		for (size_t i = 0; i < min_size; i++) {
			if (container[i] > _Right[i]) return true;
			else if (container[i] < _Right[i]) {
				return false;
			}
		}
		return _size > _Right.size();
	}

	template<typename T>
	bool basic_string<T>::operator<(const basic_string<T>& _Right)
	{
		return (*this <= _Right) && (*this != _Right);
	}

	template<typename T>
	bool basic_string<T>::operator>=(const basic_string<T>& _Right)
	{
		return (*this > _Right) || (*this == _Right);
	}

	template<typename T>
	bool basic_string<T>::operator<=(const basic_string<T>& _Right)
	{
		return !(*this > _Right);
	}

	template<typename T>
	bool basic_string<T>::operator==(const char* _c_Right)
	{
		if (strlen(_c_Right) != _size) return false;
		else {
			for (size_t i = 0; i < _size; i++) {
				if (container[i] != _c_Right[i])
					return false;
			}
			return true;
		}
	}

	template<typename T>
	bool basic_string<T>::operator!=(const char* _c_Right)
	{
		return !(*this == _c_Right);
	}

	template<typename T>
	bool basic_string<T>::operator>(const char* _c_Right)
	{
		size_t length{ strlen(_c_Right) };
		size_t min_size{ _size < length ? _size : length };
		for (size_t i = 0; i < min_size; i++) {
			if (container[i] > _c_Right[i]) return true;
			else if (container[i] < _c_Right[i]) {
				return false;
			}
		}
		return _size > length;
	}

	template<typename T>
	bool basic_string<T>::operator<(const char* _c_Right)
	{
		return (*this <= _c_Right) && (*this != _c_Right);
	}

	template<typename T>
	bool basic_string<T>::operator>=(const char* _c_Right)
	{
		return (*this > _c_Right) || (*this == _c_Right);
	}

	template<typename T>
	bool basic_string<T>::operator<=(const char* _c_Right)
	{
		return !(*this > _c_Right);
	}

	template<typename T>
	size_t basic_string<T>::size() const noexcept
	{
		return _size;
	}

	template<typename T>
	size_t basic_string<T>::capacity() const noexcept
	{
		return container.capacity();
	}

	template<typename T>
	bool basic_string<T>::empty() const noexcept
	{
		if (_size != 0) return false;
		else return true;
	}

	template<typename T>
	const T* basic_string<T>::data()
	{
		return container.data();
	}

	template<typename T>
	const T* basic_string<T>::c_str()
	{
		return container.data();
	}

	template<typename T>
	typename basic_string<T>::iterator basic_string<T>::begin()
	{
		return container.begin();
	}

	template<typename T>
	typename basic_string<T>::iterator basic_string<T>::end()
	{
		return container.begin() + _size;
	}

	template<typename T>
	typename basic_string<T>::const_iterator basic_string<T>::begin() const
	{
		return container.begin();
	}

	template<typename T>
	typename basic_string<T>::const_iterator basic_string<T>::end() const
	{
		return container.begin() + _size;
	}

	template<typename T>
	void basic_string<T>::reserve(size_t new_capacity_size)
	{
		container.reserve(new_capacity_size);
	}

	template<typename T>
	void basic_string<T>::resize(size_t new_elem_size)
	{
		container.resize(new_elem_size);
		_size = new_elem_size;
	}

	template<typename T>
	void basic_string<T>::clear()
	{
		_size = 0;
		container.clear();
	}

	template<typename T>
	void basic_string<T>::erase(const size_t _Where)
	{
		if (_Where <= _size) {
			_size = _Where;
			container.erase(container.begin() + _Where, container.end());
			container.push_back('\0');
		}
	}

	template<typename T>
	void basic_string<T>::erase(const size_t _Off, const size_t _Count)
	{
		if (_Off <= _size) {
			if (_size - _Off > _Count) {
				_size -= _Count;
				container.erase(container.begin() + _Off, container.begin() + _Off + _Count);
				container[_size] = '\0';
			}
			else {
				erase(_Off);
			}
		}
	}

	template<typename T>
	void basic_string<T>::erase(basic_string<T>::iterator _begin, basic_string<T>::iterator _end)
	{
		if (_end >= _begin) {
			if (_begin >= begin()) {
				size_t _Off = _begin - begin();
				size_t _Count = _end - _begin;
				if (_Off <= _size) {
					if (_size - _Off > _Count) {
						_size -= _Count;
						container.erase(container.begin() + _Off, container.begin() + _Off + _Count);
						container[_size] = '\0';
					}
					else {
						erase(_Off);
					}
				}
			}
			else {
				throw IteratorOutOfRangeException{};
			}
		}
		else {
			throw IteratorErrorException{};
		}
	}

	template<typename T>
	void basic_string<T>::erase(basic_string<T>::iterator _pos)
	{
		if (_pos >= begin()) {
			if (_pos < end()) {
				size_t _Where = _pos - begin();
				if (_Where <= _size) {
					_size--;
					container.erase(_pos, _pos + 1);
					container[_size] = '\0';
				}
			}
		}
		else {
			throw IteratorErrorException{};
		}
	}

	template<typename T>
	void basic_string<T>::append(size_t _Count, char c)
	{
		for (size_t i = 0; i < _Count; i++) {
			push_back(c);
		}
	}

	template<typename T>
	void basic_string<T>::append(const basic_string<T>& _str)
	{
		*this += _str;
	}

	template<typename T>
	void basic_string<T>::append(const basic_string<T>& _str, size_t _Begin)
	{
		if (_Begin <= _str.size()) {
			if (_Begin == 0) {
				*this += _str;
			}
			else {
				for (auto it = _str.begin() + _Begin; it != _str.end(); it++) {
					push_back(*it);
				}
			}
		}
		else {
			throw std::out_of_range("Begin index out of range!");
		}
	}

	template<typename T>
	void basic_string<T>::append(const basic_string<T>& _str, size_t _Begin, size_t _Count)
	{
		if (_Begin <= _str.size()) {
			if (_Begin + _Count > _str.size()) {
				_Count = _str.size() - _Begin;
			}
			for (size_t i = 0; i < _Count; i++) {
				push_back(_str[_Begin + i]);
			}
		}
		else {
			throw std::out_of_range("Begin index out of range!");
		}
	}

	template<typename T>
	void basic_string<T>::append(const char* _str)
	{
		*this += _str;
	}

	template<typename T>
	void basic_string<T>::append(const char* _str, size_t _Begin)
	{
		if (_Begin <= strlen(_str)) {
			*this += (_str + _Begin);
		}
		else {
			throw std::out_of_range("Begin index out of range!");
		}
	}

	template<typename T>
	void basic_string<T>::append(const char* _str, size_t _Begin, size_t _Count)
	{
		if (_Begin <= strlen(_str)) {
			if (strlen(_str) - _Begin < _Count) {
				_Count = strlen(_str) - _Begin;
			}
			if (_Count != 0) {
				for (size_t i = 0; i < _Count; i++) {
					push_back(_str[_Begin + i]);
				}
			}
		}
		else {
			throw std::out_of_range("Begin index out of range!");
		}
	}

	template<typename T>
	void basic_string<T>::append(std::initializer_list<char> l)
	{
		for (auto& i : l) {
			push_back(i);
		}
	}

	template<typename T>
	void basic_string<T>::push_back(char c)
	{
		if (_size == container.size()) {
			container.push_back(c);
		}
		else {
			container[_size] = c;
		}
		container.push_back('\0');
		_size++;
	}

	template<typename T>
	size_t basic_string<T>::find(char c, size_t _begin_pos)
	{
		for (size_t i = _begin_pos; i < _size; i++) {
			if (container[i] == c) {
				return i;
			}
		}
		return npos;
	}

	template<typename T>
	size_t basic_string<T>::find(const char* _str, size_t _begin_pos)
	{
		size_t length{ strlen(_str) };
		bool isFind{ true };
		if (_size < length) return npos;
		else {
			for (size_t i = _begin_pos; i < _size; i++) {
				if (_size - i >= length) {
					if (container[i] == _str[0]) {
						isFind = true;
						for (size_t j = 1; j < length; j++) {
							if (container[i + j] != _str[j]) {
								i = i + j - 1;
								isFind = false;
								break;
							}
						}
						if (isFind) return i;
					}
				}
				else {
					return npos;
				}
			}
			return npos;
		}
	}

	template<typename T>
	size_t basic_string<T>::find(const basic_string<T>& _str, size_t _begin_pos)
	{
		size_t length{ _str.size() };
		bool isFind{ true };
		if (_size < length) return npos;
		else {
			for (size_t i = _begin_pos; i < _size; i++) {
				if (_size - i >= length) {
					if (container[i] == _str[0]) {
						isFind = true;
						for (size_t j = 1; j < length; j++) {
							if (container[i + j] != _str[j]) {
								i = i + j - 1;
								isFind = false;
								break;
							}
						}
						if (isFind) return i;
					}
				}
				else {
					return npos;
				}
			}
			return npos;
		}
	}

	template<typename T>
	void basic_string<T>::swap(basic_string<T>& _Right)
	{
		basic_string<T> temp{ _Right };
		_Right.clear();
		for (auto& c : *this) {
			_Right.push_back(c);
		}
		clear();
		for (auto& c : temp) {
			push_back(c);
		}
	}

	template<typename T>
	bool operator==(const char* _Left, const basic_string<T>& _Right)
	{
		return _Right == _Left;
	}

	template<typename T>
	bool operator!=(const char* _Left, const basic_string<T>& _Right)
	{
		return _Right != _Left;
	}

	template<typename T>
	bool operator>(const char* _Left, const basic_string<T>& _Right)
	{
		return _Right < _Left;
	}

	template<typename T>
	bool operator<(const char* _Left, const basic_string<T>& _Right)
	{
		return _Right > _Left;
	}

	template<typename T>
	bool operator>=(const char* _Left, const basic_string<T>& _Right)
	{
		return _Right <= _Left;
	}

	template<typename T>
	bool operator<=(const char* _Left, const basic_string<T>& _Right)
	{
		return _Right >= _Left;
	}

	template<typename T>
	std::istream& getline(std::istream& input, basic_string<T>& _Target, const char _End = '\n')
	{
		_Target.clear();
		T c = input.get();
		while (c != '\n') {
			_Target.push_back(c);
			c = input.get();
		}
		return input;
	}

	using string = basic_string<char>;
	using wstring = basic_string<wchar_t>;
#ifdef __cpp_lib_char8_t
	using u8string = basic_string<char8_t>;
#endif // __cpp_lib_char8_t
	using u16string = basic_string<char16_t>;
	using u32string = basic_string<char32_t>;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/117077.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

C语言——选择排序

完整代码&#xff1a; //选择排序 // 选择排序是一种简单直观的排序算法。它的工作原理如下:首先在未排序序列中找到最小&#xff08;大&#xff09;元素&#xff0c;存放到排序序列的起始位置&#xff0c;然后&#xff0c;再从剩余未排序元素中继续寻找最小&#xff08;大&am…

【Liunx基础】之指令(一)

【Liunx基础】之指令&#xff08;一&#xff09; 1.ls指令2.pwd命令3.cd指令4.touch指令5.mkdir指令(重要)6.rmdir指令与rm指令&#xff08;重要&#xff09;7.man指令&#xff08;重要&#xff09;8.cp指令&#xff08;重要&#xff09; &#x1f4c3;博客主页&#xff1a; 小…

✔ ★【备战实习(面经+项目+算法)】 11.5学习

✔ ★【备战实习&#xff08;面经项目算法&#xff09;】 坚持完成每天必做如何找到好工作1. 科学的学习方法&#xff08;专注&#xff01;效率&#xff01;记忆&#xff01;心流&#xff01;&#xff09;2. 每天认真完成必做项&#xff0c;踏实学习技术 认真完成每天必做&…

C++二分算法:平衡子序列的最大和

涉及知识点 二分 动态规划 #题目 给你一个下标从 0 开始的整数数组 nums 。 nums 一个长度为 k 的 子序列 指的是选出 k 个 下标 i0 < i1 < … < ik-1 &#xff0c;如果这个子序列满足以下条件&#xff0c;我们说它是 平衡的 &#xff1a; 对于范围 [1, k - 1] 内的所…

Git从基础到实践

1.Git是用来做什么的&#xff1f; git就是一款版本控制软件&#xff0c;主要面向代码的管理。你可以理解为Git是一个代码的备份器&#xff0c;给你的每一次修改后的代码做个备份&#xff0c;防止丢失&#xff0c;这个是git最基本的功能。 其次,git不止备份,当你需要比对多…

【探索Linux】—— 强大的命令行工具 P.13(文件系统 | 软硬链接 | 动态库和静态库)

阅读导航 引言一、文件系统1. 磁盘文件系统2. 磁盘结构&#xff08;1&#xff09;物理结构&#xff08;2&#xff09;存储结构 3. stat 命令4. Linux ext2文件系统 二、软硬链接1. 软连接2. 硬链接 三、动态库和静态库1. 动态库&#xff08;1&#xff09;动态库文件扩展名&…

docker 常用

系统 Ubuntu 20.04 64位 安装文档 ubuntu&#xff1a;https://docs.docker.com/engine/install/ubuntu/ centos&#xff1a;https://docs.docker.com/engine/install/centos/ debian&#xff1a;https://docs.docker.com/engine/install/debian/ 常用命令 查找公共镜像库镜…

5 ip的分配

如上一节所述&#xff0c;需要和其他设备通信&#xff0c;那么需要先配置ip. 1、如何配置ip 1.可以使用 ifconfig&#xff0c;也可以使用 ip addr 2.设置好了以后&#xff0c;用这两个命令&#xff0c;将网卡 up 一下&#xff0c;就可以了 //---------------------------- 使…

Unity2D中瓦片地图的创建与绘制教程

Unity2D中瓦片地图的创建与绘制 素材切割创建地图创建瓦片绘制地图瓦片调色板画笔拓展素材资源链接 素材切割 选中以下素材&#xff0c;以Tiles为例&#xff08;素材链接在文章最下方&#xff09; 修改素材属性。 将Sprite Mode属性改为Multiple多张&#xff08;不然切割不了&…

JVM字节码文件浅谈

文章目录 版权声明java虚拟机的组成字节码文件打开字节码文件的姿势字节码文件的组成魔数&#xff08;基本信息&#xff09;主副版本号&#xff08;基本信息&#xff09;主版本号不兼容的错误解决方法基本信息常量池方法 字节码文件的常用工具javap -v命令jclasslib插件阿里art…

IP路由配置

一、路由协议分类 路由协议是路由器之间维护路由表的规则,用于发现路由并生成路由表以指导报文转发。可分为: 通过链路层协议发现的直连路由通过网络管理员手动配置的静态路由通过动态路由协议发现的动态路由其中,动态路由根据作用范围分为: 内部网关协议(IGP):包括rip…

asp.net人事管理信息系统VS开发sqlserver数据库web结构c#编程Microsoft Visual Studio

一、源码特点 asp.net 人事管理信息系统是一套完善的web设计管理系统&#xff0c;系统具有完整的源代码和数据库&#xff0c;系统主要采用B/S模式开发。开发环境为vs2010&#xff0c;数据库为sqlserver2008&#xff0c;使用c#语言 开发 asp.net 人事管理系统1 应用技术…

23种设计模式-Java语言实现

因为要准备一个考试所以又重新接触到了设计模式&#xff0c;之前只是别人说什么就是什么&#xff0c;记下就好了&#xff0c;完全不理解其中的思想以及为什么要用(虽然现在也不太理解…) 先慢慢总结吧&#xff0c;常读常新。 23种设计模式 “每一个模式描述了一个在我们周围不…

如何使用CodeceptJS、Playwright和GitHub Actions构建端到端测试流水线

介绍 端到端测试是软件开发的一个重要方面&#xff0c;因为它确保系统的所有组件都能正确运行。CodeceptJS是一个高效且强大的端到端自动化框架&#xff0c;与Playwright 结合使用时&#xff0c;它成为自动化Web、移动甚至桌面 (Electron.js) 应用程序比较好用的工具。 在本文中…

虚拟机VirtualBox添加磁盘

一、创建虚拟硬盘 二、虚拟硬盘分区 fdisk -l 我们新添加的磁盘/dev/sdb&#xff0c;还没有分区 sdb磁盘分区 fdisk /dev/sdb n 创建一个新分区 选择p添加主分区 我们把所有10GB空间都格式化为一个分区了 。 w 键入w&#xff0c;保存…

Windows安装WinDbg调试工具

一.下载 微软官网下载SDK的地址&#xff0c;有win11&#xff0c;win10&#xff0c;win8&#xff0c;win7&#xff0c;其他 https://developer.microsoft.com/en-us/windows/downloads/sdk-archive/ 二.安装 打开windbg\Installers\X64 Debuggers And Tools-x64_en-us.msi 要安…

如何将R128的lspsram频率提高至200M?

一、修改频率方法 首先通过cboot0命令&#xff0c;跳转到boot0的代码中&#xff0c;路径为&#xff1a; ${root_dir}/lichee/brandy-2.0/spl/ 找到lspsram的代码&#xff0c;路径为&#xff1a; ${root_dir}/lichee/brandy-2.0/spl/drivers/psram 修改头文件&#xff0c;将2…

SQL Server2000mdf升级SQL Server2005数据库还原

SQL Server2000数据库还原sqlserver 2000mdf升级 sqlserver 2008数据库还原SQL Server2005数据库脚本 sqlserver数据库低版本升级成高版本 sqlserver数据库版本升级 数据库版本还原 如果本机安装了sqlserver2012或者sqlserver2019等高版本 怎么样才能运行sqlserver2000的数据库…

开启AWS的ubuntu服务器的root用户登录权限

设置root用户密码 输入以下命令修改root用户密码 sudo passwd root输入以下命令切换到root用户 su root仅允许root用户用密码登录 输入以下命令编辑ssh配置文件 vi /etc/ssh/sshd_config新增以下配置允许root用户登录 PermitRootLogin yes把PasswordAuthentication修改为…

设计模式—结构型模式之适配器模式

设计模式—结构型模式之适配器模式 将一个接口转换成客户希望的另一个接口&#xff0c;适配器模式使接口不兼容的那些类可以一起工作&#xff0c;适配器模式分为类结构型模式&#xff08;继承&#xff09;和对象结构型模式&#xff08;组合&#xff09;两种&#xff0c;前者&a…