Implementation of std::map
$begingroup$
I have decided to make a basic C++ implementation of the std::map class, and I was checking that it is fine, as I am not sure if the operator is done correctly: should I be using the has_key function? e.t.c
template < typename _Key, typename _Ty, typename _Cmp = std::less<_Key>, typename _Alloc = std::allocator< std::pair<const _Key, _Ty> > > class map
{
public:
typedef map<_Key, _Ty, _Cmp, _Alloc> _Myt;
typedef _Key key_type;
typedef _Ty mapped_type;
typedef _Cmp compare_type;
typedef _Alloc allocator_type;
typedef std::pair<const key_type, mapped_type> value_type;
typedef value_type *pointer;
typedef const value_type *const_pointer;
typedef value_type *iterator;
typedef const value_type *const_iterator;
typedef std::size_t size_type;
typedef std::ptrdiff_t difference_type;
map()
: size_(0), capacity_(20), data_(_Alloc().allocate(20))
{
}
map(const _Myt &_Rhs)
: size_(_Rhs.size_), capacity_(_Rhs.size_ + 20), data_(_Alloc().allocate(_Rhs.size_))
{
int count = 0;
for (iterator i = &_Rhs.data_[0]; i != &_Rhs.data_[_Rhs.size_]; ++i, ++count)
{
_Alloc().construct(&data_[count], *i);
}
}
~map()
{
if (!empty())
{
for (iterator i = begin(); i != end(); ++i)
{
_Alloc().destroy(i);
}
_Alloc().deallocate(data_, capacity_);
}
}
_Myt &insert(const value_type &_Value)
{
if (++size_ >= capacity_)
{
reserve(capacity_ * 2);
}
_Alloc().construct(&data_[size_ - 1], _Value);
return *this;
}
bool has_key(const key_type &_Key)
{
for (iterator i = begin(); i != end(); ++i)
{
if (i->first == _Key)
{
return true;
}
}
return false;
}
mapped_type &operator(const key_type &_Key)
{
if (has_key(_Key))
{
for (iterator i = begin(); i != end(); ++i)
{
if (i->first == _Key)
{
return i->second;
}
}
}
size_type op = size_;
insert(value_type(_Key, mapped_type()));
return data_[op].second;
}
_Myt &reserve(size_type _Capacity)
{
int count = 0;
if (_Capacity < capacity_)
{
return *this;
}
pointer buf = _Alloc().allocate(_Capacity);
for (iterator i = begin(); i != end(); ++i, ++count)
{
_Alloc().construct(&buf[count], *i);
}
std::swap(data_, buf);
for (iterator i = &buf[0]; i != &buf[size_]; ++i)
{
_Alloc().destroy(i);
}
_Alloc().deallocate(buf, capacity_);
capacity_ = _Capacity;
return *this;
}
bool empty()
{
return size_ == 0;
}
iterator begin()
{
return &data_[0];
}
iterator end()
{
return &data_[size_];
}
private:
pointer data_;
size_type size_, capacity_;
};
c++ reinventing-the-wheel
edited Mar 10 '14 at 19:25
Jamal♦
30.5k11121227
asked Mar 10 '14 at 19:23
JosephJoseph
2601411
$endgroup$
add a comment |
$begingroup$
I have decided to make a basic C++ implementation of the std::map class, and I was checking that it is fine, as I am not sure if the operator is done correctly: should I be using the has_key function? e.t.c
template < typename _Key, typename _Ty, typename _Cmp = std::less<_Key>, typename _Alloc = std::allocator< std::pair<const _Key, _Ty> > > class map
{
public:
typedef map<_Key, _Ty, _Cmp, _Alloc> _Myt;
typedef _Key key_type;
typedef _Ty mapped_type;
typedef _Cmp compare_type;
typedef _Alloc allocator_type;
typedef std::pair<const key_type, mapped_type> value_type;
typedef value_type *pointer;
typedef const value_type *const_pointer;
typedef value_type *iterator;
typedef const value_type *const_iterator;
typedef std::size_t size_type;
typedef std::ptrdiff_t difference_type;
map()
: size_(0), capacity_(20), data_(_Alloc().allocate(20))
{
}
map(const _Myt &_Rhs)
: size_(_Rhs.size_), capacity_(_Rhs.size_ + 20), data_(_Alloc().allocate(_Rhs.size_))
{
int count = 0;
for (iterator i = &_Rhs.data_[0]; i != &_Rhs.data_[_Rhs.size_]; ++i, ++count)
{
_Alloc().construct(&data_[count], *i);
}
}
~map()
{
if (!empty())
{
for (iterator i = begin(); i != end(); ++i)
{
_Alloc().destroy(i);
}
_Alloc().deallocate(data_, capacity_);
}
}
_Myt &insert(const value_type &_Value)
{
if (++size_ >= capacity_)
{
reserve(capacity_ * 2);
}
_Alloc().construct(&data_[size_ - 1], _Value);
return *this;
}
bool has_key(const key_type &_Key)
{
for (iterator i = begin(); i != end(); ++i)
{
if (i->first == _Key)
{
return true;
}
}
return false;
}
mapped_type &operator(const key_type &_Key)
{
if (has_key(_Key))
{
for (iterator i = begin(); i != end(); ++i)
{
if (i->first == _Key)
{
return i->second;
}
}
}
size_type op = size_;
insert(value_type(_Key, mapped_type()));
return data_[op].second;
}
_Myt &reserve(size_type _Capacity)
{
int count = 0;
if (_Capacity < capacity_)
{
return *this;
}
pointer buf = _Alloc().allocate(_Capacity);
for (iterator i = begin(); i != end(); ++i, ++count)
{
_Alloc().construct(&buf[count], *i);
}
std::swap(data_, buf);
for (iterator i = &buf[0]; i != &buf[size_]; ++i)
{
_Alloc().destroy(i);
}
_Alloc().deallocate(buf, capacity_);
capacity_ = _Capacity;
return *this;
}
bool empty()
{
return size_ == 0;
}
iterator begin()
{
return &data_[0];
}
iterator end()
{
return &data_[size_];
}
private:
pointer data_;
size_type size_, capacity_;
};
c++ reinventing-the-wheel
edited Mar 10 '14 at 19:25
Jamal♦
30.5k11121227
asked Mar 10 '14 at 19:23
JosephJoseph
2601411
$endgroup$
3
$begingroup$
I am downvoting this for your use of reserved identifiers. You have been advised not to do this in all of your previous STL exercise that you put up here for review. Please STOP AND READ.
$endgroup$
– TemplateRex
Mar 12 '14 at 19:58
$begingroup$
You also fail at some basic points ofstd::map: it must not allow insertion of duplicates (which you only prevent inoperator, but not in.insert()), and it must store its elements in key order (which you make no effort at).
$endgroup$
– underscore_d
Nov 11 '18 at 13:58
add a comment |
$begingroup$
I have decided to make a basic C++ implementation of the std::map class, and I was checking that it is fine, as I am not sure if the operator is done correctly: should I be using the has_key function? e.t.c
template < typename _Key, typename _Ty, typename _Cmp = std::less<_Key>, typename _Alloc = std::allocator< std::pair<const _Key, _Ty> > > class map
{
public:
typedef map<_Key, _Ty, _Cmp, _Alloc> _Myt;
typedef _Key key_type;
typedef _Ty mapped_type;
typedef _Cmp compare_type;
typedef _Alloc allocator_type;
typedef std::pair<const key_type, mapped_type> value_type;
typedef value_type *pointer;
typedef const value_type *const_pointer;
typedef value_type *iterator;
typedef const value_type *const_iterator;
typedef std::size_t size_type;
typedef std::ptrdiff_t difference_type;
map()
: size_(0), capacity_(20), data_(_Alloc().allocate(20))
{
}
map(const _Myt &_Rhs)
: size_(_Rhs.size_), capacity_(_Rhs.size_ + 20), data_(_Alloc().allocate(_Rhs.size_))
{
int count = 0;
for (iterator i = &_Rhs.data_[0]; i != &_Rhs.data_[_Rhs.size_]; ++i, ++count)
{
_Alloc().construct(&data_[count], *i);
}
}
~map()
{
if (!empty())
{
for (iterator i = begin(); i != end(); ++i)
{
_Alloc().destroy(i);
}
_Alloc().deallocate(data_, capacity_);
}
}
_Myt &insert(const value_type &_Value)
{
if (++size_ >= capacity_)
{
reserve(capacity_ * 2);
}
_Alloc().construct(&data_[size_ - 1], _Value);
return *this;
}
bool has_key(const key_type &_Key)
{
for (iterator i = begin(); i != end(); ++i)
{
if (i->first == _Key)
{
return true;
}
}
return false;
}
mapped_type &operator(const key_type &_Key)
{
if (has_key(_Key))
{
for (iterator i = begin(); i != end(); ++i)
{
if (i->first == _Key)
{
return i->second;
}
}
}
size_type op = size_;
insert(value_type(_Key, mapped_type()));
return data_[op].second;
}
_Myt &reserve(size_type _Capacity)
{
int count = 0;
if (_Capacity < capacity_)
{
return *this;
}
pointer buf = _Alloc().allocate(_Capacity);
for (iterator i = begin(); i != end(); ++i, ++count)
{
_Alloc().construct(&buf[count], *i);
}
std::swap(data_, buf);
for (iterator i = &buf[0]; i != &buf[size_]; ++i)
{
_Alloc().destroy(i);
}
_Alloc().deallocate(buf, capacity_);
capacity_ = _Capacity;
return *this;
}
bool empty()
{
return size_ == 0;
}
iterator begin()
{
return &data_[0];
}
iterator end()
{
return &data_[size_];
}
private:
pointer data_;
size_type size_, capacity_;
};
c++ reinventing-the-wheel
edited Mar 10 '14 at 19:25
Jamal♦
30.5k11121227
asked Mar 10 '14 at 19:23
JosephJoseph
2601411
$endgroup$
I have decided to make a basic C++ implementation of the std::map class, and I was checking that it is fine, as I am not sure if the operator is done correctly: should I be using the has_key function? e.t.c
template < typename _Key, typename _Ty, typename _Cmp = std::less<_Key>, typename _Alloc = std::allocator< std::pair<const _Key, _Ty> > > class map
{
public:
typedef map<_Key, _Ty, _Cmp, _Alloc> _Myt;
typedef _Key key_type;
typedef _Ty mapped_type;
typedef _Cmp compare_type;
typedef _Alloc allocator_type;
typedef std::pair<const key_type, mapped_type> value_type;
typedef value_type *pointer;
typedef const value_type *const_pointer;
typedef value_type *iterator;
typedef const value_type *const_iterator;
typedef std::size_t size_type;
typedef std::ptrdiff_t difference_type;
map()
: size_(0), capacity_(20), data_(_Alloc().allocate(20))
{
}
map(const _Myt &_Rhs)
: size_(_Rhs.size_), capacity_(_Rhs.size_ + 20), data_(_Alloc().allocate(_Rhs.size_))
{
int count = 0;
for (iterator i = &_Rhs.data_[0]; i != &_Rhs.data_[_Rhs.size_]; ++i, ++count)
{
_Alloc().construct(&data_[count], *i);
}
}
~map()
{
if (!empty())
{
for (iterator i = begin(); i != end(); ++i)
{
_Alloc().destroy(i);
}
_Alloc().deallocate(data_, capacity_);
}
}
_Myt &insert(const value_type &_Value)
{
if (++size_ >= capacity_)
{
reserve(capacity_ * 2);
}
_Alloc().construct(&data_[size_ - 1], _Value);
return *this;
}
bool has_key(const key_type &_Key)
{
for (iterator i = begin(); i != end(); ++i)
{
if (i->first == _Key)
{
return true;
}
}
return false;
}
mapped_type &operator(const key_type &_Key)
{
if (has_key(_Key))
{
for (iterator i = begin(); i != end(); ++i)
{
if (i->first == _Key)
{
return i->second;
}
}
}
size_type op = size_;
insert(value_type(_Key, mapped_type()));
return data_[op].second;
}
_Myt &reserve(size_type _Capacity)
{
int count = 0;
if (_Capacity < capacity_)
{
return *this;
}
pointer buf = _Alloc().allocate(_Capacity);
for (iterator i = begin(); i != end(); ++i, ++count)
{
_Alloc().construct(&buf[count], *i);
}
std::swap(data_, buf);
for (iterator i = &buf[0]; i != &buf[size_]; ++i)
{
_Alloc().destroy(i);
}
_Alloc().deallocate(buf, capacity_);
capacity_ = _Capacity;
return *this;
}
bool empty()
{
return size_ == 0;
}
iterator begin()
{
return &data_[0];
}
iterator end()
{
return &data_[size_];
}
private:
pointer data_;
size_type size_, capacity_;
};
c++ reinventing-the-wheel
c++ reinventing-the-wheel
edited Mar 10 '14 at 19:25
Jamal♦
30.5k11121227
asked Mar 10 '14 at 19:23
JosephJoseph
2601411
edited Mar 10 '14 at 19:25
Jamal♦
30.5k11121227
asked Mar 10 '14 at 19:23
JosephJoseph
2601411
edited Mar 10 '14 at 19:25
Jamal♦
30.5k11121227
edited Mar 10 '14 at 19:25
Jamal♦
30.5k11121227
edited Mar 10 '14 at 19:25
Jamal♦
30.5k11121227
30.5k11121227
asked Mar 10 '14 at 19:23
JosephJoseph
2601411
asked Mar 10 '14 at 19:23
JosephJoseph
2601411
asked Mar 10 '14 at 19:23
JosephJoseph
2601411
2601411
3
$begingroup$
I am downvoting this for your use of reserved identifiers. You have been advised not to do this in all of your previous STL exercise that you put up here for review. Please STOP AND READ.
$endgroup$
– TemplateRex
Mar 12 '14 at 19:58
$begingroup$
You also fail at some basic points ofstd::map: it must not allow insertion of duplicates (which you only prevent inoperator, but not in.insert()), and it must store its elements in key order (which you make no effort at).
$endgroup$
– underscore_d
Nov 11 '18 at 13:58
add a comment |
3
$begingroup$
I am downvoting this for your use of reserved identifiers. You have been advised not to do this in all of your previous STL exercise that you put up here for review. Please STOP AND READ.
$endgroup$
– TemplateRex
Mar 12 '14 at 19:58
$begingroup$
You also fail at some basic points ofstd::map: it must not allow insertion of duplicates (which you only prevent inoperator, but not in.insert()), and it must store its elements in key order (which you make no effort at).
$endgroup$
– underscore_d
Nov 11 '18 at 13:58
3
3
$begingroup$
I am downvoting this for your use of reserved identifiers. You have been advised not to do this in all of your previous STL exercise that you put up here for review. Please STOP AND READ.
$endgroup$
– TemplateRex
Mar 12 '14 at 19:58
$begingroup$
I am downvoting this for your use of reserved identifiers. You have been advised not to do this in all of your previous STL exercise that you put up here for review. Please STOP AND READ.
$endgroup$
– TemplateRex
Mar 12 '14 at 19:58
$begingroup$
You also fail at some basic points of
std::map: it must not allow insertion of duplicates (which you only prevent in operator, but not in .insert()), and it must store its elements in key order (which you make no effort at).$endgroup$
– underscore_d
Nov 11 '18 at 13:58
$begingroup$
You also fail at some basic points of
std::map: it must not allow insertion of duplicates (which you only prevent in operator, but not in .insert()), and it must store its elements in key order (which you make no effort at).$endgroup$
– underscore_d
Nov 11 '18 at 13:58
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
Readability
With your lengthy template statement, I'd put the class statement onto the next line:
template </*...*/>
class map
Naming standards
According to this answer, identifiers in the form _Identifier are reserved:
7.1.3 Reserved identifiers
Each header declares or defines all identifiers listed in its
associated subclause, and optionally declares or defines identifiers
listed in its associated future library directions subclause and
identifiers which are always reserved either for any use or for use as
file scope identifiers.
- All identifiers that begin with an underscore and either an uppercase
letter or another underscore are always reserved for any use.
[...]
Const-correctness
You have iterators, but you should also have
constiterators:
const_iterator cbegin() const
{
return &data_[0];
}
const_iterator cend() const
{
return &data_[size_];
}
empty()should beconst:
bool empty() const
{
return size_ == 0;
}
has_key()should beconstand use the aforementionedconstiterators:
bool has_key(const key_type &_Key) const
{
for (const_iterator i = cbegin(); i != cend(); ++i)
{
if (i->first == _Key)
{
return true;
}
}
return false;
}
edited May 23 '17 at 12:40
Community♦
1
answered Mar 10 '14 at 19:36
Jamal♦Jamal
30.5k11121227
$endgroup$
1
$begingroup$
Havingconst_iterator begin() const;is probably a higher priority thancbegin(), 'twas introduced first because it's the more useful, propagatingconstcorrectness in certain template situations. The lack ofconstcorrectness obviously led tofor (iterator i = &_Rhs.data_[0]; i != &_Rhs.data_[_Rhs.size_]; ++i, ++count)- that can be cleaned up as...i = rhs.begin(); i != rhs.end();....
$endgroup$
– Tony D
Mar 14 '14 at 23:31
add a comment |
$begingroup$
[...] I am not sure if the operator is done correctly: should I be using the has_key function?
It is done correctly (i.e. it does what the contract of its API should), but not efficiently. The operator iterates twice (once in has_key and once in the operator). You can replace both calls with a call to std::find_if, and remove the has_key function completely.
edited 6 hours ago
Toby Speight
26.8k742118
answered Mar 11 '14 at 12:57
utnapistimutnapistim
3,270820
$endgroup$
add a comment |
$begingroup$
You are searching two times the entire arrays to find your key,pair value. This is highly inefficient. Instead you could extend your has type to take two arguments and in the second argument it could store the value. This way you only iterate once.
Otherwise yes, reusing your code is a yes yes, just don't iterate two times when you could easily done it once.
answered Mar 10 '14 at 19:32
ClaudiordgzClaudiordgz
1767
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
});
});
}, "mathjax-editing");
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "196"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f43972%2fimplementation-of-stdmap%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Readability
With your lengthy template statement, I'd put the class statement onto the next line:
template </*...*/>
class map
Naming standards
According to this answer, identifiers in the form _Identifier are reserved:
7.1.3 Reserved identifiers
Each header declares or defines all identifiers listed in its
associated subclause, and optionally declares or defines identifiers
listed in its associated future library directions subclause and
identifiers which are always reserved either for any use or for use as
file scope identifiers.
- All identifiers that begin with an underscore and either an uppercase
letter or another underscore are always reserved for any use.
[...]
Const-correctness
You have iterators, but you should also have
constiterators:
const_iterator cbegin() const
{
return &data_[0];
}
const_iterator cend() const
{
return &data_[size_];
}
empty()should beconst:
bool empty() const
{
return size_ == 0;
}
has_key()should beconstand use the aforementionedconstiterators:
bool has_key(const key_type &_Key) const
{
for (const_iterator i = cbegin(); i != cend(); ++i)
{
if (i->first == _Key)
{
return true;
}
}
return false;
}
edited May 23 '17 at 12:40
Community♦
1
answered Mar 10 '14 at 19:36
Jamal♦Jamal
30.5k11121227
$endgroup$
1
$begingroup$
Havingconst_iterator begin() const;is probably a higher priority thancbegin(), 'twas introduced first because it's the more useful, propagatingconstcorrectness in certain template situations. The lack ofconstcorrectness obviously led tofor (iterator i = &_Rhs.data_[0]; i != &_Rhs.data_[_Rhs.size_]; ++i, ++count)- that can be cleaned up as...i = rhs.begin(); i != rhs.end();....
$endgroup$
– Tony D
Mar 14 '14 at 23:31
add a comment |
$begingroup$
Readability
With your lengthy template statement, I'd put the class statement onto the next line:
template </*...*/>
class map
Naming standards
According to this answer, identifiers in the form _Identifier are reserved:
7.1.3 Reserved identifiers
Each header declares or defines all identifiers listed in its
associated subclause, and optionally declares or defines identifiers
listed in its associated future library directions subclause and
identifiers which are always reserved either for any use or for use as
file scope identifiers.
- All identifiers that begin with an underscore and either an uppercase
letter or another underscore are always reserved for any use.
[...]
Const-correctness
You have iterators, but you should also have
constiterators:
const_iterator cbegin() const
{
return &data_[0];
}
const_iterator cend() const
{
return &data_[size_];
}
empty()should beconst:
bool empty() const
{
return size_ == 0;
}
has_key()should beconstand use the aforementionedconstiterators:
bool has_key(const key_type &_Key) const
{
for (const_iterator i = cbegin(); i != cend(); ++i)
{
if (i->first == _Key)
{
return true;
}
}
return false;
}
edited May 23 '17 at 12:40
Community♦
1
answered Mar 10 '14 at 19:36
Jamal♦Jamal
30.5k11121227
$endgroup$
1
$begingroup$
Havingconst_iterator begin() const;is probably a higher priority thancbegin(), 'twas introduced first because it's the more useful, propagatingconstcorrectness in certain template situations. The lack ofconstcorrectness obviously led tofor (iterator i = &_Rhs.data_[0]; i != &_Rhs.data_[_Rhs.size_]; ++i, ++count)- that can be cleaned up as...i = rhs.begin(); i != rhs.end();....
$endgroup$
– Tony D
Mar 14 '14 at 23:31
add a comment |
$begingroup$
Readability
With your lengthy template statement, I'd put the class statement onto the next line:
template </*...*/>
class map
Naming standards
According to this answer, identifiers in the form _Identifier are reserved:
7.1.3 Reserved identifiers
Each header declares or defines all identifiers listed in its
associated subclause, and optionally declares or defines identifiers
listed in its associated future library directions subclause and
identifiers which are always reserved either for any use or for use as
file scope identifiers.
- All identifiers that begin with an underscore and either an uppercase
letter or another underscore are always reserved for any use.
[...]
Const-correctness
You have iterators, but you should also have
constiterators:
const_iterator cbegin() const
{
return &data_[0];
}
const_iterator cend() const
{
return &data_[size_];
}
empty()should beconst:
bool empty() const
{
return size_ == 0;
}
has_key()should beconstand use the aforementionedconstiterators:
bool has_key(const key_type &_Key) const
{
for (const_iterator i = cbegin(); i != cend(); ++i)
{
if (i->first == _Key)
{
return true;
}
}
return false;
}
edited May 23 '17 at 12:40
Community♦
1
answered Mar 10 '14 at 19:36
Jamal♦Jamal
30.5k11121227
$endgroup$
Readability
With your lengthy template statement, I'd put the class statement onto the next line:
template </*...*/>
class map
Naming standards
According to this answer, identifiers in the form _Identifier are reserved:
7.1.3 Reserved identifiers
Each header declares or defines all identifiers listed in its
associated subclause, and optionally declares or defines identifiers
listed in its associated future library directions subclause and
identifiers which are always reserved either for any use or for use as
file scope identifiers.
- All identifiers that begin with an underscore and either an uppercase
letter or another underscore are always reserved for any use.
[...]
Const-correctness
You have iterators, but you should also have
constiterators:
const_iterator cbegin() const
{
return &data_[0];
}
const_iterator cend() const
{
return &data_[size_];
}
empty()should beconst:
bool empty() const
{
return size_ == 0;
}
has_key()should beconstand use the aforementionedconstiterators:
bool has_key(const key_type &_Key) const
{
for (const_iterator i = cbegin(); i != cend(); ++i)
{
if (i->first == _Key)
{
return true;
}
}
return false;
}
edited May 23 '17 at 12:40
Community♦
1
answered Mar 10 '14 at 19:36
Jamal♦Jamal
30.5k11121227
edited May 23 '17 at 12:40
Community♦
1
edited May 23 '17 at 12:40
Community♦
1
edited May 23 '17 at 12:40
Community♦
1
1
answered Mar 10 '14 at 19:36
Jamal♦Jamal
30.5k11121227
answered Mar 10 '14 at 19:36
Jamal♦Jamal
30.5k11121227
answered Mar 10 '14 at 19:36
Jamal♦Jamal
30.5k11121227
30.5k11121227
1
$begingroup$
Havingconst_iterator begin() const;is probably a higher priority thancbegin(), 'twas introduced first because it's the more useful, propagatingconstcorrectness in certain template situations. The lack ofconstcorrectness obviously led tofor (iterator i = &_Rhs.data_[0]; i != &_Rhs.data_[_Rhs.size_]; ++i, ++count)- that can be cleaned up as...i = rhs.begin(); i != rhs.end();....
$endgroup$
– Tony D
Mar 14 '14 at 23:31
add a comment |
1
$begingroup$
Havingconst_iterator begin() const;is probably a higher priority thancbegin(), 'twas introduced first because it's the more useful, propagatingconstcorrectness in certain template situations. The lack ofconstcorrectness obviously led tofor (iterator i = &_Rhs.data_[0]; i != &_Rhs.data_[_Rhs.size_]; ++i, ++count)- that can be cleaned up as...i = rhs.begin(); i != rhs.end();....
$endgroup$
– Tony D
Mar 14 '14 at 23:31
1
1
$begingroup$
Having
const_iterator begin() const; is probably a higher priority than cbegin(), 'twas introduced first because it's the more useful, propagating const correctness in certain template situations. The lack of const correctness obviously led to for (iterator i = &_Rhs.data_[0]; i != &_Rhs.data_[_Rhs.size_]; ++i, ++count) - that can be cleaned up as ...i = rhs.begin(); i != rhs.end();....$endgroup$
– Tony D
Mar 14 '14 at 23:31
$begingroup$
Having
const_iterator begin() const; is probably a higher priority than cbegin(), 'twas introduced first because it's the more useful, propagating const correctness in certain template situations. The lack of const correctness obviously led to for (iterator i = &_Rhs.data_[0]; i != &_Rhs.data_[_Rhs.size_]; ++i, ++count) - that can be cleaned up as ...i = rhs.begin(); i != rhs.end();....$endgroup$
– Tony D
Mar 14 '14 at 23:31
add a comment |
$begingroup$
[...] I am not sure if the operator is done correctly: should I be using the has_key function?
It is done correctly (i.e. it does what the contract of its API should), but not efficiently. The operator iterates twice (once in has_key and once in the operator). You can replace both calls with a call to std::find_if, and remove the has_key function completely.
edited 6 hours ago
Toby Speight
26.8k742118
answered Mar 11 '14 at 12:57
utnapistimutnapistim
3,270820
$endgroup$
add a comment |
$begingroup$
[...] I am not sure if the operator is done correctly: should I be using the has_key function?
It is done correctly (i.e. it does what the contract of its API should), but not efficiently. The operator iterates twice (once in has_key and once in the operator). You can replace both calls with a call to std::find_if, and remove the has_key function completely.
edited 6 hours ago
Toby Speight
26.8k742118
answered Mar 11 '14 at 12:57
utnapistimutnapistim
3,270820
$endgroup$
add a comment |
$begingroup$
[...] I am not sure if the operator is done correctly: should I be using the has_key function?
It is done correctly (i.e. it does what the contract of its API should), but not efficiently. The operator iterates twice (once in has_key and once in the operator). You can replace both calls with a call to std::find_if, and remove the has_key function completely.
edited 6 hours ago
Toby Speight
26.8k742118
answered Mar 11 '14 at 12:57
utnapistimutnapistim
3,270820
$endgroup$
[...] I am not sure if the operator is done correctly: should I be using the has_key function?
It is done correctly (i.e. it does what the contract of its API should), but not efficiently. The operator iterates twice (once in has_key and once in the operator). You can replace both calls with a call to std::find_if, and remove the has_key function completely.
edited 6 hours ago
Toby Speight
26.8k742118
answered Mar 11 '14 at 12:57
utnapistimutnapistim
3,270820
edited 6 hours ago
Toby Speight
26.8k742118
edited 6 hours ago
Toby Speight
26.8k742118
edited 6 hours ago
Toby Speight
26.8k742118
26.8k742118
answered Mar 11 '14 at 12:57
utnapistimutnapistim
3,270820
answered Mar 11 '14 at 12:57
utnapistimutnapistim
3,270820
answered Mar 11 '14 at 12:57
utnapistimutnapistim
3,270820
3,270820
add a comment |
add a comment |
$begingroup$
You are searching two times the entire arrays to find your key,pair value. This is highly inefficient. Instead you could extend your has type to take two arguments and in the second argument it could store the value. This way you only iterate once.
Otherwise yes, reusing your code is a yes yes, just don't iterate two times when you could easily done it once.
answered Mar 10 '14 at 19:32
ClaudiordgzClaudiordgz
1767
$endgroup$
add a comment |
$begingroup$
You are searching two times the entire arrays to find your key,pair value. This is highly inefficient. Instead you could extend your has type to take two arguments and in the second argument it could store the value. This way you only iterate once.
Otherwise yes, reusing your code is a yes yes, just don't iterate two times when you could easily done it once.
answered Mar 10 '14 at 19:32
ClaudiordgzClaudiordgz
1767
$endgroup$
add a comment |
$begingroup$
You are searching two times the entire arrays to find your key,pair value. This is highly inefficient. Instead you could extend your has type to take two arguments and in the second argument it could store the value. This way you only iterate once.
Otherwise yes, reusing your code is a yes yes, just don't iterate two times when you could easily done it once.
answered Mar 10 '14 at 19:32
ClaudiordgzClaudiordgz
1767
$endgroup$
You are searching two times the entire arrays to find your key,pair value. This is highly inefficient. Instead you could extend your has type to take two arguments and in the second argument it could store the value. This way you only iterate once.
Otherwise yes, reusing your code is a yes yes, just don't iterate two times when you could easily done it once.
answered Mar 10 '14 at 19:32
ClaudiordgzClaudiordgz
1767
answered Mar 10 '14 at 19:32
ClaudiordgzClaudiordgz
1767
answered Mar 10 '14 at 19:32
ClaudiordgzClaudiordgz
1767
answered Mar 10 '14 at 19:32
ClaudiordgzClaudiordgz
1767
1767
add a comment |
add a comment |
Thanks for contributing an answer to Code Review Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f43972%2fimplementation-of-stdmap%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
3
$begingroup$
I am downvoting this for your use of reserved identifiers. You have been advised not to do this in all of your previous STL exercise that you put up here for review. Please STOP AND READ.
$endgroup$
– TemplateRex
Mar 12 '14 at 19:58
$begingroup$
You also fail at some basic points of
std::map: it must not allow insertion of duplicates (which you only prevent inoperator, but not in.insert()), and it must store its elements in key order (which you make no effort at).$endgroup$
– underscore_d
Nov 11 '18 at 13:58