- == 系统问题，暂停聊天功能。==
- 【征集】西西河的经济学，及清流措施，需要主动参与者，『稷下学宫』新认证方式，24年网站打算和努力目标
主题：说说我前面提到过的面试题 -- 使用尽量中文
家园 说说我前面提到过的面试题 原题如下：
不许用STL,实现一个类 string，封装库函数strcat。这个类可以这么调用：string s1("abcde"),s2("1234567"),s3;
s3=s1+s2; //now s3 should represent sth like "abcde1234567"
帖子后面给出了我的答案。当然好答案绝对不是唯一的，这里高手众多，希望大家能拨冗指正。
我对答案的评判有这么几个标准：
1. 知道基本的c++概念，类、构造析构、运算符重载，也知道必要的编程惯例，比如c风格的字符串。
2. 具有程序员级别的设计能力和问题解决能力，能根据简要的叙述设计出可行的实现框架。对问题中含糊或没有明确的部分，可以做出尽量合理的假设，并把这些假设体现在文档中。
3. 能够合理分配和释放资源，有RAII的概念。知道delelte[]和delete的区别。
4. 具备exception safe的概念。
5. 实现中避免常见的错误。知道一些避免错误的技巧。
6. 选择让代码的使用者不容易出错的实现方式。
7. 注意到一些易被忽略的实现细节，一个例子就是这道题里的字符串可能是双字节的或多字节的。
前6项都是比较基本和重要的。
我给出的答案里用了重载来实现编译时根据不同的类型调用不同版本的库函数，这个其实不很重要。大家可以忽略。
//myString.h
#ifndef MY_STRING_H
#define MY_STRING_H
#include <string.h>
#if _MSC_VER > 1000
#pragma warning(disable : 4996)
#endif
template<class T> //T could be char, wchar_t, unsigned char, specific to single character, wide character, or multibyte character string
class universal_string{
public:
universal_string();
universal_string(const T* source); //const is expected
virtual ~universal_string(); //virtual so that derived class would be deleted properly
universal_string(const universal_string<T>& source); //mandatory because of "rule of three"
universal_string<T>& operator =(const universal_string<T>& source);
size_t len() const{ //optional for this problem, good habit for a experienced programer though
return length;
}
//helper functions
universal_string<T>& concatenate(const universal_string<T>& source);
private:
size_t length; //we assume the longest string won't exceed an unsigned int.
T* pString;
};
template<class T> //allow expression like "AAA" + string2, in which the first operand is a pointer to char
const universal_string<T> operator + (const universal_string<T>& first, const universal_string<T>& second){ //first const here to make sure the expression won't be misused as lvalue.
universal_string<T> result(first);
return result.concatenate(second);
}
//following helper functions to decide which version function in library to call in compile time.
char * myStrCpy(char *strDestination,const char *strSource ){
return strcpy(strDestination,strSource);
}
wchar_t *myStrCpy( wchar_t *strDestination, const wchar_t *strSource){
return wcscpy(strDestination,strSource);
}
size_t myStrLen(const char* str){
return strlen(str);
}
size_t myStrLen(const wchar_t* str){
return wcslen(str);
}
#ifdef _MBCS
#include <mbstring.h>
unsigned char *myStrCpy(unsigned char *strDestination,const unsigned char *strSource ){
return _mbscpy(strDestination,strSource);
}
size_t myStrLen(const unsigned char* str){
return _mbslen(str);
}
#endif
template<class T>
universal_string<T>::universal_string(const T* source): //assume source is pointing to a valid string. especially, it can not be NULL
length(myStrLen(source)), //even we add codes to check if it is NULL, we still can not prevent it being some other non null but invalid value
pString(new T[length+1]){ //therefore such check does not make much sense.
myStrCpy(pString,source);
}
template<class T>
universal_string<T>::universal_string():
length(0),pString(new T[1]){ //T[1] instead of T to be compatible with destructor
*pString=0;
}
template<class T>
universal_string<T>::~universal_string(){
delete[] pString; //[] is mandatory
}
template<class T>
universal_string<T>::universal_string(const universal_string<T>& source):
length(source.length),
pString(new T[length+1]){
myStrCpy(pString, source.pString);
}
template<class T>
universal_string<T>& universal_string<T>::operator =(const universal_string<T>& source){
//your solution must gurantee that when
//1. source is *this, and/or
//2. exception is thrown inside the function
//it still handles correctly
T* buffer=new T[source.length+1];
myStrCpy(buffer,source.pString);
delete[] pString;
pString=buffer;
length=source.length;
return *this;
}
template<class T>
universal_string<T>& universal_string<T>::concatenate(const universal_string<T>& source){
//your solution must gurantee that when
//1. source is *this, and/or
//2. exception is thrown inside the function
if (source.length>0) {
size_t tmpLen=length+source.length;
T* buffer=new T[tmpLen+1];
if (pString!=NULL) myStrCpy(buffer,pString);
myStrCpy(buffer+length,source.pString); //since we know where to join, we use strcpy in stead of strcat for better performance
delete[] pString;
pString=buffer;
length=tmpLen;
}
return *this;
}
#define string universal_string<wchar_t>
#endif
//main.cpp
#include "myString.h"
int main(int narg,char**varg){
string s1(L"ABCDEFG"),s2(L"1234567"),s3;
s3=s1+s2;
}
本帖一共被 1 帖 引用 (帖内工具实现)家园 乱评一点答案 本着最小化俺的工作量的原则（猜测可能的需求引起工作量增加的事情俺不干，猜测错了要么干错了，要么白干）：
1.原题没指明何种平台和编译器，所以只用标准C++。（_MSC_VER，_mbslen之类的就不能用了）
2.原题没有要求处理不同字符类型，所以只支持char。
3.原题没说会从string派生子类，所以不要virtual dtor，耗内存更少。
#include <cstring>
#include <cassert>
#include <algorithm>
class string
{
public:
inline explicit string(const char* p=0, size_t len=0)
{ // if you know length, avoid strlen.
size_t length = p ? (len>0?len:(std::strlen(p))) : 0;
if( length>0 )
{
allocate(length);
std::memcpy(m_p, p, length+1);
}
else
{
m_p = 0;
m_len = 0;
}
}
inline string(const string& other) : m_len(0), m_p(0)
{
string s(other.m_p, other.m_len);
swap(s);
}
inline ~string()
{
delete []m_p;
}
inline string& operator=(const string& other)
{
string s(other);
swap(s);
return *this;
}
inline const string operator+(const string& other) const
{
string s(*this);
s+=other;
return s;
}
inline string& operator+=(const string& other)
{
if( other.m_len>0 )
{
string s;
size_t len = m_len + other.m_len;
s.allocate(len);
std::memcpy(s.m_p, m_p, m_len);
std::memcpy(s.m_p+m_len, other.m_p, other.m_len);
s.m_p[len] = '\0';
swap(s);
}
return *this;
}
inline void swap(string& other)
{
std::swap(m_len, other.m_len);
std::swap(m_p, other.m_p);
}
private:
// only for uninitialized or empty string.
// controlled use! m_p will not be a valid C-style string.
inline void allocate(size_t len)
{
assert(len>0);
m_p = new char[len+1];
m_len = len;
}
private:
size_t m_len;
char* m_p;
};
int main(int argc, char* argv[])
{
string s1("abcde"),s2("1234567"),s3;
s3=s1+s2; //now s3 should represent sth like "abcde1234567"
return 0;
}
修改: 所有函数加了inline
家园 你这够复杂，面试的时候要写这么一个类，得花多少时间啊。