Z
zackp
I have been learning "modern C++" using "Accelerated C++" by Andrew
Koenig and Barbara Moo, working out all exercises along the way, and
sometimes go back to "improve" my own solutions.
I worked out the solution to Exercise 11-6 a while ago. In Chap. 13,
I learned about static member function, so I went back to my solution,
and change the std::allocator<T> alloc; to static std::allocator<T>
alloc; in the Vec template class. I also made what I believe the
necessary modifications to member function defintions. But the codes
(Vec.hpp, 11-6.cpp and Makefile are shown below) don't link anymore.
I'd appreciate any hints as to where I have done wrong.
Thanks,
--Zack
The following are errors that I got:
zperry@ubuntu:~/work/learn/c++/accel/chap11/11-6$ make
g++ -Wall -pedantic -Wextra -g -c -o 11-6.o 11-6.cpp
g++ -o 11-6 11-6.o
11-6.o: In function `Vec<int>::clear()':
/home/zperry/work/learn/c++/accel/chap11/11-6/Vec.hpp:148: undefined
reference to `Vec<int>::alloc'
11-6.o: In function `Vec<char>::erase(char*)':
/home/zperry/work/learn/c++/accel/chap11/11-6/Vec.hpp:167: undefined
reference to `Vec<char>::alloc'
11-6.o: In function `Vec<char>::erase(char*, char*)':
/home/zperry/work/learn/c++/accel/chap11/11-6/Vec.hpp:185: undefined
reference to `Vec<char>::alloc'
11-6.o: In function `Vec<int>::unchecked_append(int const&)':
/home/zperry/work/learn/c++/accel/chap11/11-6/Vec.hpp:138: undefined
reference to `Vec<int>::alloc'
11-6.o: In function `Vec<char>::unchecked_append(char const&)':
/home/zperry/work/learn/c++/accel/chap11/11-6/Vec.hpp:138: undefined
reference to `Vec<char>::alloc'
11-6.o: In function `Vec<int>::create(unsigned int, int const&)':
/home/zperry/work/learn/c++/accel/chap11/11-6/Vec.hpp:91: undefined
reference to `Vec<int>::alloc'
11-6.o: In function `Vec<int>::create(int const*, int const*)':
/home/zperry/work/learn/c++/accel/chap11/11-6/Vec.hpp:99: undefined
reference to `Vec<int>::alloc'
11-6.o: In function `Vec<int>::uncreate()':
/home/zperry/work/learn/c++/accel/chap11/11-6/Vec.hpp:109: undefined
reference to `Vec<int>::alloc'
/home/zperry/work/learn/c++/accel/chap11/11-6/Vec.hpp:112: undefined
reference to `Vec<int>::alloc'
11-6.o: In function `Vec<int>::grow()':
/home/zperry/work/learn/c++/accel/chap11/11-6/Vec.hpp:123: undefined
reference to `Vec<int>::alloc'
11-6.o: In function `Vec<char>::uncreate()':
/home/zperry/work/learn/c++/accel/chap11/11-6/Vec.hpp:109: undefined
reference to `Vec<char>::alloc'
/home/zperry/work/learn/c++/accel/chap11/11-6/Vec.hpp:112: undefined
reference to `Vec<char>::alloc'
11-6.o: In function `Vec<char>::grow()':
/home/zperry/work/learn/c++/accel/chap11/11-6/Vec.hpp:123: undefined
reference to `Vec<char>::alloc'
collect2: ld returned 1 exit status
make: *** [11-6] Error 1
-------------------------------------------- Vec.hpp
----------------------------------------------------------------------------
#ifndef ACCP_VEC_HPP
#define ACCP_VEC_HPP
#include <memory> // to use the allocator class
#include <algorithm> // for max(t1, t2)
#include <cstddef> // to use the size_t
template <class T> class Vec {
public:
typedef T* iterator;
typedef const T* const_iterator;
typedef std::size_t size_type; // in a header, use fully
qualified type
typedef T value_type;
typedef T& reference;
typedef const T& const_reference;
Vec(): data(0), avail(0), limit(0) { create(); }
explicit Vec(size_type n, const T& t = T()):
data(0), avail(0), limit(0) { create(n, t); }
Vec(const Vec& v): data(0), avail(0), limit(0)
{ create(v.begin(), v.end()); }
Vec& operator=(const Vec&);
~Vec() { uncreate(); }
T& operator[] (size_type i) { return data; }
const T& operator[] (size_type i) const { return data; }
void push_back(const T& t) {
if (avail == limit)
grow();
unchecked_append(t);
}
size_type size() const { return avail - data; }
iterator begin() { return data; }
const_iterator begin() const { return data; }
iterator end() { return avail; }
const_iterator end() const { return avail; }
void clear();
iterator erase(iterator it);
iterator erase(iterator, iterator);
bool empty() const { return data == avail; }
private:
iterator data; // first element in the Vec
iterator avail; // (one past) the last elemement in the Vec
iterator limit; // (one past) the allocated memory
static std::allocator<T> alloc; // object to handle memory
allocation
// allocate and initialize the underlying array
void create();
void create(size_type, const T&);
void create(const_iterator, const_iterator);
// destroy the elements in the array and free the memory
void uncreate();
// support functions for push_back
void grow();
void unchecked_append(const T&);
};
template <class T>
Vec<T>& Vec<T>:
perator=(const Vec& rhs)
{
// check for self-assignment
if (&rhs != this) {
// free the array in the lef-hand side
uncreate();
// copy elements from the right-hand to the left-hand side
create(rhs.begin(), rhs.end());
}
return *this;
}
template <class T> void Vec<T>::create()
{
data = avail = limit = 0;
}
template <class T> void Vec<T>::create(size_type n, const T& val)
{
data = Vec<T>::alloc.allocate(n);
limit = avail = data + n;
std::uninitialized_fill(data, limit, val);
}
template <class T>
void Vec<T>::create(const_iterator i, const_iterator j)
{
data = Vec<T>::alloc.allocate(j - i);
limit = avail = std::uninitialized_copy(i, j, data);
}
template <class T> void Vec<T>::uncreate()
{
if (data) {
// destroy (in reverse order) the elements that were
constructed
iterator it = avail;
while (it != data)
Vec<T>::alloc.destroy(--it);
// return all the space that was allocated
Vec<T>::alloc.deallocate(data, limit - data);
}
data = avail = limit = 0;
}
template <class T> void Vec<T>::grow()
{
// when growing, allocate twice as much space as currently in use
size_type new_size = std::max(2 * (limit - data) , ptrdiff_t(1));
// allocate new space and copy existing elements in the new space
iterator new_data = Vec<T>::alloc.allocate(new_size);
iterator new_avail = std::uninitialized_copy(data, avail,
new_data);
// return the old space
uncreate();
// reset pointers to point to the newly allocated space
data = new_data;
avail = new_avail;
limit = data + new_size;
}
// assume avail points at allocated, but uninitialized space
template <class T> void Vec<T>::unchecked_append(const T& val)
{
Vec<T>::alloc.construct(avail++, val);
}
// similar to uncreate, but no need to return memory
template <class T> void Vec<T>::clear()
{
if (data) {
// destroy (in reverse order) the elements that were
constructed
iterator it = avail;
while (it != data)
Vec<T>::alloc.destroy(--it);
}
data = avail = limit = 0;
}
// using the keyword typename is critical in defining the following
member
// function. The reason is described in p. 141 and p. 153. Without it,
g++
// issues "... error: expected constructor, destructor, or type
conversion
// before ‘Vec"
template <class T> typename Vec<T>::iterator Vec<T>::erase(iterator
it)
{
if (it != avail) {
iterator i = it, j = it + 1;
size_type d = avail - i; // number of element from i to the
end
// move everything behind the object referred by it by one
position
while (j != avail)
*i++ = *j++;
avail = i; // when j = avail, i refers the last element (to be
erased)
Vec<T>::alloc.destroy(i);
return avail - d - 1; // since it is erased, so one less
} else
return avail;
}
template <class T> typename Vec<T>::iterator
Vec<T>::erase(iterator b, iterator e)
{
if (b != e && e != avail) {
iterator i = b, j = e;
size_type span = e - b, behind = avail - e;
// copy over everything behind the objects referred by b .. e
while (j != avail)
*i++ = *j++;
// destroy (in reverse order) the elements that are left
towards the end
iterator it = avail;
while (it != i)
Vec<T>::alloc.destroy(--it);
avail -= span; // move forward avail span elements
forward
return avail - behind; // point to the element first copied
over
} else
return erase(b);
}
#endif
-------------------------------------------- 11-6.cpp
-------------------------------------------------------------------------
#include <iostream>
#include "Vec.hpp"
using std::cout;
using std::endl;
int main()
{
// test the default constructor and the size member function
Vec<int> v;
cout << "The just declared v has size " << v.size() << endl;
// test the explicit Vec constructor and the size member function
Vec<int> v1(3, 1);
cout << "The just defined v1 has size " << v1.size() << endl;
// test the copy constructor
Vec<int> v2(v1);
cout << "The just defined v2 has size " << v2.size() << endl;
{
// test the push_back member function, and the const begin and
end
// iterators
v.push_back(0);
v.push_back(1);
v.push_back(2);
Vec<int>::const_iterator b = v.begin(), e = v.end();
while (b != e) {
cout << "Now v has element " << *b << endl;
++b;
}
}
{
// test the non const begin and end iterators
Vec<int>::iterator b = v.begin(), e = v.end();
while (b != e) {
(*b) *= 2;
cout << "Now v has element " << *b << endl;
++b;
}
}
// test the non const [] operator
typedef Vec<int>::size_type st;
for (st i = 0; i != v2.size(); ++i) {
v2 *= 2;
cout << "Now v2[" << i << "] is " << v2 << endl;
}
// test the const [] operator
for (st i = 0; i != v1.size(); ++i)
cout << "v1[" << i << "] is " << v1 << endl;
// test the clear() member function
v2.clear();
cout << "After clear, v2 has size " << v2.size() << endl;
// test the empty() member function
if (v2.empty())
cout << "Now v2 is really empty." << endl;
// test the erase(it) member function.
{
// create a vector, load it with the first ten characters of
the
// alphabet
static const char text[] = "ABCDEFGHIJ";
Vec<char> a;
for(int i=0; i != 10; ++i) {
a.push_back( text );
}
Vec<char>::size_type size = a.size();
Vec<char>::iterator b;
Vec<char>::iterator t;
for(Vec<char>::size_type i=0; i != size; ++i) {
b = a.begin();
a.erase(b);
// display the vector
for(t = a.begin(); t != a.end(); ++t)
cout << *t;
cout << endl;
}
}
// test the erase(it) member function.
{
// create a vector, load it with the first ten characters of
the
// alphabet
Vec<char> a;
for(int i = 0; i != 10; ++i) {
a.push_back(i + 65);
}
// display the complete vector
for(Vec<char>::size_type i = 0; i != a.size(); ++i) {
cout << a;
}
cout << endl;
// use erase to remove all but the first two and last three
elements
// of the vector
a.erase(a.begin() + 2, a.end() - 3);
// display the modified vector
for(Vec<char>::size_type i = 0; i != a.size(); ++i) {
cout << a;
}
cout << endl;
}
return 0;
}
----------------------------------------------------------- Makefile
--------------------------------------------------------------
LIST=$(subst /, ,$(CURDIR))
PROGRAM=$(lastword $(LIST))
CXXSOURCES = $(PROGRAM).cpp
CXXOBJECTS = $(CXXSOURCES:.cpp=.o)
CXXFLAGS = -Wall -pedantic -Wextra -g
CXX = g++
all: $(PROGRAM)
$(PROGRAM): $(CXXOBJECTS)
$(CXX) -o $@ $(CXXOBJECTS) $(LDFLAGS)
run: $(PROGRAM)
@$(CURDIR)/$(PROGRAM)
..PHONY : clean
clean:
$(RM) $(CXXOBJECTS) $(PROGRAM) core
Koenig and Barbara Moo, working out all exercises along the way, and
sometimes go back to "improve" my own solutions.
I worked out the solution to Exercise 11-6 a while ago. In Chap. 13,
I learned about static member function, so I went back to my solution,
and change the std::allocator<T> alloc; to static std::allocator<T>
alloc; in the Vec template class. I also made what I believe the
necessary modifications to member function defintions. But the codes
(Vec.hpp, 11-6.cpp and Makefile are shown below) don't link anymore.
I'd appreciate any hints as to where I have done wrong.
Thanks,
--Zack
The following are errors that I got:
zperry@ubuntu:~/work/learn/c++/accel/chap11/11-6$ make
g++ -Wall -pedantic -Wextra -g -c -o 11-6.o 11-6.cpp
g++ -o 11-6 11-6.o
11-6.o: In function `Vec<int>::clear()':
/home/zperry/work/learn/c++/accel/chap11/11-6/Vec.hpp:148: undefined
reference to `Vec<int>::alloc'
11-6.o: In function `Vec<char>::erase(char*)':
/home/zperry/work/learn/c++/accel/chap11/11-6/Vec.hpp:167: undefined
reference to `Vec<char>::alloc'
11-6.o: In function `Vec<char>::erase(char*, char*)':
/home/zperry/work/learn/c++/accel/chap11/11-6/Vec.hpp:185: undefined
reference to `Vec<char>::alloc'
11-6.o: In function `Vec<int>::unchecked_append(int const&)':
/home/zperry/work/learn/c++/accel/chap11/11-6/Vec.hpp:138: undefined
reference to `Vec<int>::alloc'
11-6.o: In function `Vec<char>::unchecked_append(char const&)':
/home/zperry/work/learn/c++/accel/chap11/11-6/Vec.hpp:138: undefined
reference to `Vec<char>::alloc'
11-6.o: In function `Vec<int>::create(unsigned int, int const&)':
/home/zperry/work/learn/c++/accel/chap11/11-6/Vec.hpp:91: undefined
reference to `Vec<int>::alloc'
11-6.o: In function `Vec<int>::create(int const*, int const*)':
/home/zperry/work/learn/c++/accel/chap11/11-6/Vec.hpp:99: undefined
reference to `Vec<int>::alloc'
11-6.o: In function `Vec<int>::uncreate()':
/home/zperry/work/learn/c++/accel/chap11/11-6/Vec.hpp:109: undefined
reference to `Vec<int>::alloc'
/home/zperry/work/learn/c++/accel/chap11/11-6/Vec.hpp:112: undefined
reference to `Vec<int>::alloc'
11-6.o: In function `Vec<int>::grow()':
/home/zperry/work/learn/c++/accel/chap11/11-6/Vec.hpp:123: undefined
reference to `Vec<int>::alloc'
11-6.o: In function `Vec<char>::uncreate()':
/home/zperry/work/learn/c++/accel/chap11/11-6/Vec.hpp:109: undefined
reference to `Vec<char>::alloc'
/home/zperry/work/learn/c++/accel/chap11/11-6/Vec.hpp:112: undefined
reference to `Vec<char>::alloc'
11-6.o: In function `Vec<char>::grow()':
/home/zperry/work/learn/c++/accel/chap11/11-6/Vec.hpp:123: undefined
reference to `Vec<char>::alloc'
collect2: ld returned 1 exit status
make: *** [11-6] Error 1
-------------------------------------------- Vec.hpp
----------------------------------------------------------------------------
#ifndef ACCP_VEC_HPP
#define ACCP_VEC_HPP
#include <memory> // to use the allocator class
#include <algorithm> // for max(t1, t2)
#include <cstddef> // to use the size_t
template <class T> class Vec {
public:
typedef T* iterator;
typedef const T* const_iterator;
typedef std::size_t size_type; // in a header, use fully
qualified type
typedef T value_type;
typedef T& reference;
typedef const T& const_reference;
Vec(): data(0), avail(0), limit(0) { create(); }
explicit Vec(size_type n, const T& t = T()):
data(0), avail(0), limit(0) { create(n, t); }
Vec(const Vec& v): data(0), avail(0), limit(0)
{ create(v.begin(), v.end()); }
Vec& operator=(const Vec&);
~Vec() { uncreate(); }
T& operator[] (size_type i) { return data; }
const T& operator[] (size_type i) const { return data; }
void push_back(const T& t) {
if (avail == limit)
grow();
unchecked_append(t);
}
size_type size() const { return avail - data; }
iterator begin() { return data; }
const_iterator begin() const { return data; }
iterator end() { return avail; }
const_iterator end() const { return avail; }
void clear();
iterator erase(iterator it);
iterator erase(iterator, iterator);
bool empty() const { return data == avail; }
private:
iterator data; // first element in the Vec
iterator avail; // (one past) the last elemement in the Vec
iterator limit; // (one past) the allocated memory
static std::allocator<T> alloc; // object to handle memory
allocation
// allocate and initialize the underlying array
void create();
void create(size_type, const T&);
void create(const_iterator, const_iterator);
// destroy the elements in the array and free the memory
void uncreate();
// support functions for push_back
void grow();
void unchecked_append(const T&);
};
template <class T>
Vec<T>& Vec<T>:
perator=(const Vec& rhs){
// check for self-assignment
if (&rhs != this) {
// free the array in the lef-hand side
uncreate();
// copy elements from the right-hand to the left-hand side
create(rhs.begin(), rhs.end());
}
return *this;
}
template <class T> void Vec<T>::create()
{
data = avail = limit = 0;
}
template <class T> void Vec<T>::create(size_type n, const T& val)
{
data = Vec<T>::alloc.allocate(n);
limit = avail = data + n;
std::uninitialized_fill(data, limit, val);
}
template <class T>
void Vec<T>::create(const_iterator i, const_iterator j)
{
data = Vec<T>::alloc.allocate(j - i);
limit = avail = std::uninitialized_copy(i, j, data);
}
template <class T> void Vec<T>::uncreate()
{
if (data) {
// destroy (in reverse order) the elements that were
constructed
iterator it = avail;
while (it != data)
Vec<T>::alloc.destroy(--it);
// return all the space that was allocated
Vec<T>::alloc.deallocate(data, limit - data);
}
data = avail = limit = 0;
}
template <class T> void Vec<T>::grow()
{
// when growing, allocate twice as much space as currently in use
size_type new_size = std::max(2 * (limit - data) , ptrdiff_t(1));
// allocate new space and copy existing elements in the new space
iterator new_data = Vec<T>::alloc.allocate(new_size);
iterator new_avail = std::uninitialized_copy(data, avail,
new_data);
// return the old space
uncreate();
// reset pointers to point to the newly allocated space
data = new_data;
avail = new_avail;
limit = data + new_size;
}
// assume avail points at allocated, but uninitialized space
template <class T> void Vec<T>::unchecked_append(const T& val)
{
Vec<T>::alloc.construct(avail++, val);
}
// similar to uncreate, but no need to return memory
template <class T> void Vec<T>::clear()
{
if (data) {
// destroy (in reverse order) the elements that were
constructed
iterator it = avail;
while (it != data)
Vec<T>::alloc.destroy(--it);
}
data = avail = limit = 0;
}
// using the keyword typename is critical in defining the following
member
// function. The reason is described in p. 141 and p. 153. Without it,
g++
// issues "... error: expected constructor, destructor, or type
conversion
// before ‘Vec"
template <class T> typename Vec<T>::iterator Vec<T>::erase(iterator
it)
{
if (it != avail) {
iterator i = it, j = it + 1;
size_type d = avail - i; // number of element from i to the
end
// move everything behind the object referred by it by one
position
while (j != avail)
*i++ = *j++;
avail = i; // when j = avail, i refers the last element (to be
erased)
Vec<T>::alloc.destroy(i);
return avail - d - 1; // since it is erased, so one less
} else
return avail;
}
template <class T> typename Vec<T>::iterator
Vec<T>::erase(iterator b, iterator e)
{
if (b != e && e != avail) {
iterator i = b, j = e;
size_type span = e - b, behind = avail - e;
// copy over everything behind the objects referred by b .. e
while (j != avail)
*i++ = *j++;
// destroy (in reverse order) the elements that are left
towards the end
iterator it = avail;
while (it != i)
Vec<T>::alloc.destroy(--it);
avail -= span; // move forward avail span elements
forward
return avail - behind; // point to the element first copied
over
} else
return erase(b);
}
#endif
-------------------------------------------- 11-6.cpp
-------------------------------------------------------------------------
#include <iostream>
#include "Vec.hpp"
using std::cout;
using std::endl;
int main()
{
// test the default constructor and the size member function
Vec<int> v;
cout << "The just declared v has size " << v.size() << endl;
// test the explicit Vec constructor and the size member function
Vec<int> v1(3, 1);
cout << "The just defined v1 has size " << v1.size() << endl;
// test the copy constructor
Vec<int> v2(v1);
cout << "The just defined v2 has size " << v2.size() << endl;
{
// test the push_back member function, and the const begin and
end
// iterators
v.push_back(0);
v.push_back(1);
v.push_back(2);
Vec<int>::const_iterator b = v.begin(), e = v.end();
while (b != e) {
cout << "Now v has element " << *b << endl;
++b;
}
}
{
// test the non const begin and end iterators
Vec<int>::iterator b = v.begin(), e = v.end();
while (b != e) {
(*b) *= 2;
cout << "Now v has element " << *b << endl;
++b;
}
}
// test the non const [] operator
typedef Vec<int>::size_type st;
for (st i = 0; i != v2.size(); ++i) {
v2 *= 2;
cout << "Now v2[" << i << "] is " << v2 << endl;
}
// test the const [] operator
for (st i = 0; i != v1.size(); ++i)
cout << "v1[" << i << "] is " << v1 << endl;
// test the clear() member function
v2.clear();
cout << "After clear, v2 has size " << v2.size() << endl;
// test the empty() member function
if (v2.empty())
cout << "Now v2 is really empty." << endl;
// test the erase(it) member function.
{
// create a vector, load it with the first ten characters of
the
// alphabet
static const char text[] = "ABCDEFGHIJ";
Vec<char> a;
for(int i=0; i != 10; ++i) {
a.push_back( text );
}
Vec<char>::size_type size = a.size();
Vec<char>::iterator b;
Vec<char>::iterator t;
for(Vec<char>::size_type i=0; i != size; ++i) {
b = a.begin();
a.erase(b);
// display the vector
for(t = a.begin(); t != a.end(); ++t)
cout << *t;
cout << endl;
}
}
// test the erase(it) member function.
{
// create a vector, load it with the first ten characters of
the
// alphabet
Vec<char> a;
for(int i = 0; i != 10; ++i) {
a.push_back(i + 65);
}
// display the complete vector
for(Vec<char>::size_type i = 0; i != a.size(); ++i) {
cout << a;
}
cout << endl;
// use erase to remove all but the first two and last three
elements
// of the vector
a.erase(a.begin() + 2, a.end() - 3);
// display the modified vector
for(Vec<char>::size_type i = 0; i != a.size(); ++i) {
cout << a;
}
cout << endl;
}
return 0;
}
----------------------------------------------------------- Makefile
--------------------------------------------------------------
LIST=$(subst /, ,$(CURDIR))
PROGRAM=$(lastword $(LIST))
CXXSOURCES = $(PROGRAM).cpp
CXXOBJECTS = $(CXXSOURCES:.cpp=.o)
CXXFLAGS = -Wall -pedantic -Wextra -g
CXX = g++
all: $(PROGRAM)
$(PROGRAM): $(CXXOBJECTS)
$(CXX) -o $@ $(CXXOBJECTS) $(LDFLAGS)
run: $(PROGRAM)
@$(CURDIR)/$(PROGRAM)
..PHONY : clean
clean:
$(RM) $(CXXOBJECTS) $(PROGRAM) core