Boost.org multi_index module
Home Page: http://boost.org/libs/multi_index
| Branch | Travis | Drone | GitHub Actions | AppVeyor | Regression tests |
|---|---|---|---|---|---|
| develop |  |
 |
 |
 |
|
| master |  |
 |
 |
|
Boost.MultiIndex provides a class template
named multi_index_container which enables the construction of containers
maintaining one or more indices with different sorting and access semantics.
Hello.
I have a task:
Create a template class that internally uses a multi_index_container with a data type that depends on the class template parameter.
I wrote the implementation code for VS2022, but under Linux (gcc) it didn't want to compile.
The compiler throws errors, but I don't see any errors in the code.
Below is an example and my solution.
In this regard, I have questions for the developers:
Hints improve performance. Sometimes we have more than one hint available before insert, and not using them all is a waste of time and power.
I figure the insert would have to be on the multi_index object itself and not a specific index.
Class template mem_fun reference
mem_fun<Class,Type,PtrToMemberFunction> is a model of:
Key Extractor from reference_wrapper<Class>,
Key Extractor from any chained pointer to Class.
but:
if the member function returns non-const reference, the key extractor can be a read/write Key Extractor from reference_wrapper and any chained pointer to Class
struct student
{
int _i;
double _d;
friend bool operator<(student const& s1, student const& s2)
{
return std::tie(s1._i, s1._d) < std::tie(s2._i, s2._d);
}
int & i() { return this->_i; }
template<typename stream_t>
friend stream_t&& operator<<(stream_t&& stream, student *const& s)
{
return static_cast<stream_t && >(stream << "(" << s->_i << "," << s->_d << ")");
}
};
int main()
{
typedef boost::multi_index::multi_index_container<
student*,
boost::multi_index::indexed_by<
boost::multi_index::ordered_unique<boost::multi_index::identity<student>>,
boost::multi_index::ordered_unique<boost::multi_index::mem_fun<student,int&,&student::i>>
>
>multi_index_student;
multi_index_student s({ new student{1,1.0},new student{3,3.0},new student{2,3.0} });
std::copy(std::begin(boost::get<1>(s)), std::end(boost::get<1>(s)), std::ostream_iterator<student*>(std::cout));
boost::get<1>(s).modify_key(std::begin(boost::get<1>(s)), [](int& i) {i = 5; });
std::copy(std::begin(boost::get<1>(s)), std::end(boost::get<1>(s)), std::ostream_iterator<student*>(std::cout));
}void ordered_index_impl<...>::swap_(ordered_index_impl<...>& x) uses std::swap for swapping the key and comp_ functors. Is there any particular reason for not using boost::swap here?
Here are a class and a multi_index contaier.
struct foo {
int key1;
int key2;
std::atomic<int> no_key; // thread-safe itself
};
namespace mi = boost::multi_index;
using mi_foo = mi::multi_index_container<
foo,
mi::indexed_by<
mi::ordered_non_unique<
mi::key<&foo::key1>
>,
mi::ordered_non_unique<
mi::key<&foo::key2>
>
>
>;key1 and key2 are used as index key but no_key doesn't.
In order to access the container, I use boost::shared_mutex.
boost::shared_mutex m;
mi_foo mf;When I insert to mf or erase from mf, I use exclusive lock.
boost::lock_guard<boost::shared_mutex> g{m}; // exclusive lock guard
mf.emplace(....);When I want to update no_key, I can't do as follows:
boost::shared_lock_guard<boost::shared_mutex> g{m}; // shared lock guard
auto it = mf.begin(); // in actual code, find something
++it->no_key; It's because it is const_iterator. It is reasonable that if key1 or key2 is overwritten, indexes would be broken.
So I need to do as follows:
boost::shared_lock_guard<boost::shared_mutex> g{m}; // shared lock guard
auto it = mf.begin(); // in actual code, find something
mf.modify(
it,
[](auto& e) {
++e.no_key;
}
);After mod lambda expression is called, multi_index container can re-calculate indexes.
modify() is called is shared lock guard. That means multiple threads can call modify() concurrently.
Is it safe as long as I update only no key members in modify() function from multiple threads ?
NOTE no_key itself is thread safe because std::atomic<int> no_key.
I'm not sure after mod function called process is thread safe if keys are not updated.
As the subject says - this is causing us issues in code that could otherwise be constexpr where it not for boost::multi_index
What hashing implementation is boost::multi_index using? My apologies if this was obvious, but I couldn't find it from the documentation.
I'm curious because there's been a large amount of performance work going into boost::container's hashes recently, and it would be interesting to see if that could be applied to multi_index as well.
Hi,
I really like multi_index. I use multiple versions of the following schema: a vector which has an additional hashed-key to access the values.
typedef boost::multi_index::multi_index_container<
some_type,
boost::multi_index::indexed_by<
boost::multi_index::random_access<>, // keep insertion order
boost::multi_index::hashed_unique<
boost::multi_index::tag<some_tag>,
boost::multi_index::member<some_type, key_type, &some_type::m_key> >
>
> some_vector;
But I always stumble when I want to change the "mapped-to" values after find-ing them through the hashed_unique-interface: I can either
const from the mapped-to members when writing to them, but if you want to do it in a generic way you end up with something like this const_cast<std::add_lvalue_reference_t<std::remove_cvref_t<decltype((*it))>>>(*it).m_member = value;
So, my idea is to add a new function, e.g. named modify_payload, which has the same syntax as modify BUT it DOES NOT check for changes of keys (I also would remove the try-catch handling). And it is absolutely UP TO THE USER to not change any value that is used a key.
If you like the idea, I could implement I first try and create a PR.
best
Tobias
I am trying to build a version of Caffe for GPU on Ubuntu 18.04 with boost 1.67 an CUDA 10.1
I checked out the code and I am getting the error cannot call member function ‘boost::multi_index::detail::sequenced_index_node::impl_pointer boost::multi_index::detail::sequenced_index_node::impl() which seems to be related to boost library and I have installed boost as a dependency:
NVCC src/caffe/layers/cudnn_conv_layer.cu
/usr/include/boost/multi_index/detail/seq_index_node.hpp: In instantiation of ‘static void boost::multi_index::detail::sequenced_index_node::increment(boost::multi_index::detail::sequenced_index_node&) [with Super = boost::multi_index::detail::ordered_index_node<boost::multi_index::detail::null_augment_policy, boost::multi_index::detail::index_node_base<std::pair<const std::__cxx11::basic_string, boost::property_tree::basic_ptree<std::__cxx11::basic_string, std::__cxx11::basic_string > >, std::allocator<std::pair<const std::__cxx11::basic_string, boost::property_tree::basic_ptree<std::__cxx11::basic_string, std::__cxx11::basic_string > > > > >]’:
/usr/include/boost/multi_index/detail/bidir_node_iterator.hpp:55:16: required from ‘boost::multi_index::detail::bidir_node_iterator& boost::multi_index::detail::bidir_node_iterator::operator++() [with Node = boost::multi_index::detail::sequenced_index_node<boost::multi_index::detail::ordered_index_node<boost::multi_index::detail::null_augment_policy, boost::multi_index::detail::index_node_base<std::pair<const std::_cxx11::basic_string, boost::property_tree::basic_ptree<std::cxx11::basic_string, std::cxx11::basic_string > >, std::allocator<std::pair<const std::cxx11::basic_string, boost::property_tree::basic_ptree<std::cxx11::basic_string, std::cxx11::basic_string > > > > > >]’
/usr/include/boost/multi_index_container.hpp:269:73: required from ‘boost::multi_index::multi_index_container<Value, IndexSpecifierList, Allocator>::multi_index_container(const boost::multi_index::multi_index_container<Value, IndexSpecifierList, Allocator>&) [with Value = std::pair<const std::cxx11::basic_string, boost::property_tree::basic_ptree<std::cxx11::basic_string, std::cxx11::basic_string > >; IndexSpecifierList = boost::multi_index::indexed_by<boost::multi_index::sequenced<boost::multi_index::tag<> >, boost::multi_index::ordered_non_unique<boost::multi_index::tag<boost::property_tree::basic_ptree<std::cxx11::basic_string, std::cxx11::basic_string >::subs::by_name, mpl::na, mpl::na, mpl::na, mpl::na, mpl::na, mpl::na, mpl::na, mpl::na, mpl::na, mpl::na, mpl::na, mpl::na, mpl::na, mpl::na, mpl::na, mpl::na, mpl::na, mpl::na, mpl::na>, boost::multi_index::member<std::pair<const std::cxx11::basic_string, boost::property_tree::basic_ptree<std::cxx11::basic_string, std::cxx11::basic_string > >, const std::cxx11::basic_string, &std::pair<const std::cxx11::basic_string, boost::property_tree::basic_ptree<std::cxx11::basic_string, std::cxx11::basic_string > >::first>, std::less<std::cxx11::basic_string > >, mpl::na, mpl::na, mpl::na, mpl::na, mpl::na, mpl::na, mpl::na, mpl::na, mpl::na, mpl::na, mpl::na, mpl::na, mpl::na, mpl::na, mpl::na, mpl::na, mpl::na, mpl::na>; Allocator = std::allocator<std::pair<const std::__cxx11::basic_string, boost::property_tree::basic_ptree<std::__cxx11::basic_string, std::__cxx11::basic_string > > >]’
/usr/include/boost/property_tree/detail/ptree_implementation.hpp:191:94: required from ‘boost::property_tree::basic_ptree<Key, Data, KeyCompare>::basic_ptree(const boost::property_tree::basic_ptree<Key, Data, KeyCompare>&) [with Key = std::__cxx11::basic_string; Data = std::__cxx11::basic_string; KeyCompare = std::less<std::__cxx11::basic_string >]’
src/caffe/layers/detection_output_layer.cu:220:29: required from ‘void caffe::DetectionOutputLayer::Forward_gpu(const std::vector<caffe::Blob>&, const std::vector<caffe::Blob>&) [with Dtype = float]’
src/caffe/layers/detection_output_layer.cu:302:147: required from here
/usr/include/boost/multi_index/detail/seq_index_node.hpp:198:23: error: cannot call member function ‘boost::multi_index::detail::sequenced_index_node::impl_pointer boost::multi_index::detail::sequenced_index_node::impl() [with Super = boost::multi_index::detail::ordered_index_node<boost::multi_index::detail::null_augment_policy, boost::multi_index::detail::index_node_base<std::pair<const std::__cxx11::basic_string, boost::property_tree::basic_ptree<std::__cxx11::basic_string, std::__cxx11::basic_string > >, std::allocator<std::pair<const std::__cxx11::basic_string, boost::property_tree::basic_ptree<std::__cxx11::basic_string, std::__cxx11::basic_string > > > > >; boost::multi_index::detail::sequenced_index_node::impl_pointer = boost::multi_index::detail::sequenced_index_node_impl<std::allocator >]’ without object
impl_pointer xi=x->impl();
~~~~^~
#include <iostream>
#include <cstdlib>
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/identity.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index/tag.hpp>
#include <boost/multi_index/hashed_index.hpp>
namespace bmi = boost::multi_index;
namespace Node {
using Id = std::int64_t;
struct Tag {};
}
namespace Edge {
using Id = std::int64_t;
struct Tag {};
}
struct IndexById {};
struct IndexBySource {};
struct IndexByTarget {};
struct EdgeData {
Edge::Id id;
bool deleted = false;
Node::Id source;
Node::Id target;
};
using EdgeDataContainer = boost::multi_index_container<
EdgeData,
bmi::indexed_by<
bmi::ordered_unique<bmi::tag<IndexById>, bmi::member<EdgeData, Edge::Id, &EdgeData::id>>,
bmi::ordered_non_unique<bmi::tag<IndexBySource>, bmi::member<EdgeData, Node::Id, &EdgeData::source>>,
bmi::ordered_non_unique<bmi::tag<IndexByTarget>, bmi::member<EdgeData, Node::Id, &EdgeData::target>>
>
>;
using EdgeDataContainerByIdIndex = typename bmi::index<EdgeDataContainer, IndexById>::type;
using EdgeDataContainerBySourceIndex = typename bmi::index<EdgeDataContainer, IndexBySource>::type;
using EdgeDataContainerByTargetIndex = typename bmi::index<EdgeDataContainer, IndexByTarget>::type;
int main()
{
EdgeDataContainerByIdIndex::const_iterator it_1, it_2;
std::cout << (it_1 == it_2 ? "true" : "false") << std::endl;
}
Is there a reason why this print false? i would expected to print true since the iterator are both default constructed
When using a custom allocator that contains say a smart pointer to a resource manager then moving the allocator results in the smart pointer being a nullptr due to it being moved. Taking copies of this moved-from allocator results in unusable allocators due to the nullptr to a resource manager.
The move-constructor of multi_index_container moves the allocator but then copies the moved-from allocator into the indexes.
According to the document:
https://www.boost.org/doc/libs/1_77_0/libs/multi_index/doc/reference/seq_indices.html
template bool modify(iterator position,Modifier mod);
...
Postconditions: Validity of position is preserved if the operation succeeds.
I wrote the following PoC code.
Before modify() calling, it2 is point to the value order=2.
After modify() is called, the order is updated to 10.
it2 is now point to updated element. (order 10)
The it2 is now point to the last element because the order is the biggest value(10).
So assert(it2 == it10) should success.
it3 is also modified by modify() call. it3 is got before it2 's modification. it3 isn't effected by it2 modification.
Am I understanding correctly?
The actual usecase is calling multiple async APIs (Boost.Asio) on the single thread.
And async completion handler captures the iterator that points to multi index element.
The multi_index container could be reordered by modify but never added and removed in my usecase.
#include <iostream>
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/key.hpp>
namespace mi = boost::multi_index;
struct my {
int order;
int data;
};
using mi_my = mi::multi_index_container<
my,
mi::indexed_by<
mi::ordered_unique<
mi::key<&my::order>
>
>
>;
int main() {
mi_my m;
m.emplace(my{3, 30});
m.emplace(my{1, 10});
m.emplace(my{2, 20});
auto it = m.begin();
auto it1 = it++;
auto it2 = it++;
auto it3 = it++;
std::cout << it1->order << std::endl;
std::cout << it2->order << std::endl;
std::cout << it3->order << std::endl;
std::cout << "---" << std::endl;
{
bool ret = m.modify(it2, [&](auto& e){ e.order = 10; });
assert(ret);
}
{
bool ret = m.modify(it3, [&](auto& e){ e.order = 0; });
assert(ret);
}
std::cout << it1->order << std::endl;
std::cout << it2->order << std::endl;
std::cout << it3->order << std::endl;
std::cout << "---" << std::endl;
for (auto const& e : m) std::cout << e.order << std::endl;
auto it10 = --m.end();
assert(it2 == it10);
} I work on MSVC's C++ Standard Library implementation, and we regularly build Boost (along with many other open-source projects) to identify compiler/library bugs that would break your project, so we can fix them before shipping. This also allows us to provide advance notice of source-breaking changes - which is the case here.
The paper P2166R1 "Prohibiting basic_string And basic_string_view Construction From nullptr" has been accepted for the upcoming C++23 Standard, and we recently implemented it by merging microsoft/STL#1995 from our contributor @sam20908. Our open-source test pass then discovered the following code in Boost.MultiIndex's tests that is now disallowed by C++23:
multi_index/test/test_composite_key.cpp
Line 329 in 436c60c
std::string str_=0 now fails to compile with:
error C2440: 'default argument': cannot convert from 'int' to 'std::string'
note: No constructor could take the source type, or constructor overload resolution was ambiguous
(This is because the null pointer constant 0 is convertible to const char* and nullptr_t, so it's a compiler error, although with a less clear message than nullptr would generate.) This code has undefined behavior in C++98 through C++20 (as string's constructor has a precondition that the pointer is non-null); C++23 makes it ill-formed.
There are several ways to fix this code, for example std::string str_="", that are backward-compatible with previous Standards.
Hello, I really like your library but there is one thing that I miss while using it. Databases usually can create indexes of optional unique fields and this can be very useful. As I can see there is no way to model this behavior using multi_index container because there can be only one empty optional in the container. Maybe I am just missing something from documentation.
I am thinking of is as an additional index type that will add values to the index only if optional holds a value. But such a solution will require changes in other types of the library because if used incorrectly (single optional index) it can leak objects because there won't be any references in indexes.
C++20 added a new method to the associative containers, contains, which takes a key and returns a boolean, indicating whether or not the element is in the container.
This releases us from using functions like count or find just for checking if the element is in the container, and be more explicit about our intentions.
As multi-index tries to be as similar as the STL counterparts, this is a logical addition.
Windows
Visual Studio 2022
boost 1.78.0
vcpkg
C++ 17
C2039: 'is_first_of_group': is not a member of 'boost::multi_index::detail::hashed_index_node_alg
Since C++17, associative containers of STL such as std::set have a member function extract().
It returns internal node-handle.
https://en.cppreference.com/w/cpp/container/set/extract
https://en.cppreference.com/w/cpp/container/node_handle
If multi_index's containers have the same or similar member function, it is useful especially moving an element from the container. I tried to do that using modify() member function but I couldn't do that. I wrote a move operation in 2nd argument (lambda expression) of modify(). modify() calls the lambda expression and then, does re-arrange process. During the process, the container accesses the moved from object.
Here is a discussion on the stackoverflow:
https://stackoverflow.com/questions/57335172/is-there-any-way-to-move-an-element-from-ordered-index-ed-multi-index
I guess multi_index container will be able to have something like extract() member function but I'm not sure it is possible.
Hi,
I have tested the attached code with boost 1.74 compiled with msys2 / mingw-w64 / g++ 10.2 on windows 10.
I have an example with a multi_index container of entities which represent table columns. Each table column has its id, name as fields, and a position as intrinsic sequence index.
Suppose I add to the container these columns : { col0, col1, col2 }. I have found that if I relocate one column backward, i.e. col1 from position 1 to position 0, it works; but, again starting with columns { col0, col1, col2 }, if I instead try to move col0 from position 0 to position 1 it doesn't work (columns remain the same)
Could this be fixed ?
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/sequenced_index.hpp>
#include <iostream>
#include <string>
struct column
{
column(int id, const std::string& name) : id(id), name(name) {}
int id;
std::string name;
bool operator<(const column& c) const { return id < c.id; }
};
// tags
struct id {};
struct name {};
struct pos {};
std::ostream& operator<<(std::ostream& out, const column& c)
{
out << c.id << " - " << c.name;
return out;
}
using column_set = boost::multi_index_container<
column,
boost::multi_index::indexed_by<
// index 0 : sort by less<int> on id
boost::multi_index::ordered_unique<
boost::multi_index::tag<id>,
boost::multi_index::member<
column,
int,
&column::id
>
>,
// index 1 : sort by less<string> on name
boost::multi_index::ordered_unique<
boost::multi_index::tag<name>,
boost::multi_index::member<
column,
std::string,
&column::name
>
>,
// index 2 : sequenced
boost::multi_index::sequenced<
boost::multi_index::tag<pos>
>
>
>;
void print_column(const column& c, const column_set::index<pos>::type& pos_index)
{
// get a view to pos index
auto pos_it = pos_index.iterator_to(c);
std::cout << c << " | " << std::distance(begin(pos_index), pos_it) << "\n";
}
void print_out_by_id(const column_set& cs)
{
// get a view to id index
const column_set::index<id>::type& id_index = cs.get<id>();
// get a view to pos index
const column_set::index<pos>::type& pos_index = cs.get<pos>();
// use id_index as a regular std::set
// pos_index will give the actual item pos
std::for_each(
begin(id_index),
end(id_index),
[&pos_index](const auto& column)
{ print_column(column, pos_index); });
}
void print_out_by_name(const column_set& cs)
{
// get a view to name_index
const column_set::index<name>::type& name_index = cs.get<name>();
// get a view to pos index
const column_set::index<pos>::type& pos_index = cs.get<pos>();
// use name_index as a regular std::set
std::for_each(
begin(name_index),
end(name_index),
[&pos_index](const auto& column)
{ print_column(column, pos_index); });
}
void print_out_by_pos(const column_set& cs)
{
// get a view to id index
const column_set::index<pos>::type& pos_index = cs.get<pos>();
// use id_index as a regular std::set
std::for_each(
begin(pos_index),
end(pos_index),
[&pos_index](const auto& column)
{ print_column(column, pos_index); });
}
void test_decrement_pos()
{
column c0 { 0, "name" };
column c1 { 1, "age" };
column c2 { 2, "city" };
column_set cs { c2, c0, c1 };
std::cout << "---------------\n";
std::cout << "by pos :\n";
print_out_by_pos(cs);
auto& col_name_index = cs.get<name>();
std::string col_name = "name";
auto col_name_it = col_name_index.find(col_name);
auto old_col_pos_it = cs.project<pos>(col_name_it);
auto& col_pos_index = cs.get<pos>();
auto new_col_pos_it = begin(col_pos_index);
std::advance(new_col_pos_it, 0);
col_pos_index.relocate(new_col_pos_it, old_col_pos_it);
std::cout << "---------------\n";
print_out_by_pos(cs);
}
void test_increment_pos()
{
column c0 { 0, "name" };
column c1 { 1, "age" };
column c2 { 2, "city" };
column_set cs { c2, c0, c1 };
std::cout << "---------------\n";
std::cout << "by pos :\n";
print_out_by_pos(cs);
auto& col_name_index = cs.get<name>();
std::string col_name = "city";
auto col_name_it = col_name_index.find(col_name);
auto old_col_pos_it = cs.project<pos>(col_name_it);
auto& col_pos_index = cs.get<pos>();
auto new_col_pos_it = begin(col_pos_index);
std::advance(new_col_pos_it, 1);
col_pos_index.relocate(new_col_pos_it, old_col_pos_it);
std::cout << "---------------\n";
print_out_by_pos(cs);
}
int main()
{
test_decrement_pos(); // ok, this works and columns are printed with changed position
test_increment_pos(); // this doesn't seem to work :(
}
Thanks,
Marco
testing.capture-output bin.v2/libs/multi_index/test/test_key.test/gcc-4.8/debug/cxxstd-11-iso/test_key.run
====== BEGIN OUTPUT ======
libs/multi_index/test/test_key.cpp(22): test 'false' failed in function 'void test_key()'
1 error detected.
EXIT STATUS: 1
====== END OUTPUT ======
It would probably be better to use something like
#include <boost/config/pragma_message.hpp>
#if !defined(BOOST_MULTI_INDEX_KEY_SUPPORTED)
BOOST_PRAGMA_MESSAGE("Skipping test, boost::multi_index::key not supported")
void test_key()
{
}
#else
I'm trying to build p4c, the reference compiler for the P4 language. This worked fine with Boost 1.81, but fails with 1.83 due to the following error:
In file included from /usr/include/boost/multi_index/hashed_index.hpp:32,
from /usr/include/boost/graph/named_graph.hpp:18,
from /usr/include/boost/graph/adjacency_list.hpp:36,
from /home/jkhsjdhjs/aur/p4lang-p4c/src/p4c-1.2.4.3/backends/graphs/graphs.h:33,
from /home/jkhsjdhjs/aur/p4lang-p4c/src/p4c-1.2.4.3/backends/graphs/graphs.cpp:17,
from /home/jkhsjdhjs/aur/p4lang-p4c/src/p4c-1.2.4.3/build/backends/graphs/CMakeFiles/p4cgraphs.dir/Unity/unity_0_cxx.cxx:4:
/usr/include/boost/multi_index/detail/bucket_array.hpp: In function ‘void boost::serialization::load_construct_data(Archive&, boost::multi_index::detail::bucket_array<Allocator>*, unsigned int)’:
/usr/include/boost/multi_index/detail/bucket_array.hpp:239:19: error: there are no arguments to ‘bad_archive_exception’ that depend on a template parameter, so a declaration of ‘bad_archive_exception’ must be available [-fpermissive]
239 | throw_exception(bad_archive_exception());
| ^~~~~~~~~~~~~~~~~~~~~
/usr/include/boost/multi_index/detail/bucket_array.hpp:239:19: note: (if you use ‘-fpermissive’, G++ will accept your code, but allowing the use of an undeclared name is deprecated)
In file included from /usr/include/boost/multi_index/hashed_index.hpp:35:
/usr/include/boost/multi_index/detail/index_node_base.hpp: In function ‘void boost::serialization::load_construct_data(Archive&, boost::multi_index::detail::index_node_base<Value, Allocator>*, unsigned int)’:
/usr/include/boost/multi_index/detail/index_node_base.hpp:120:19: error: there are no arguments to ‘bad_archive_exception’ that depend on a template parameter, so a declaration of ‘bad_archive_exception’ must be available [-fpermissive]
120 | throw_exception(bad_archive_exception());
| ^~~~~~~~~~~~~~~~~~~~~
Looking at the trace, this seems to be a boost issue. What do you think?
See also: p4lang/p4c#4147
The program below as-is inserts a set of values into a multi_index_container with ordered_non_unique indices via a for loop, with each element being inserted individually. When the elements with the key "Bob" (as identified by equal_range) are iterated over, they appear in the same order as they were inserted (which can be seen by looking at the age of each "Bob"). However, if you change the #if 1 to #if 0 then the elements are inserted via a call to the iterator range-based overload of insert. In this case, the ages of the people named "Bob" are not displayed in the order of insertion (which I assume would be forward pass from the begin iterator to the end iterator).
The following demo program can also be found here: https://gcc.godbolt.org/z/EvG4rW1ba
#include <iostream>
#include <string>
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/member.hpp>
using namespace boost::multi_index;
struct person {
std::string name;
int age;
};
typedef multi_index_container<
person,
indexed_by<
ordered_non_unique<member<person, std::string, &person::name>>,
ordered_non_unique<member<person, int, &person::age>>
>
> person_set;
int main()
{
std::vector<person> people = {
{"Bob", 32},
{"Charlie", 32},
{"Bob", 32},
{"Emily", 32},
{"Bob", 30},
{"Alex", 32},
{"Bob", 56},
{"Bob", 32}
};
person_set persons;
#if 1
for (auto const & p : people)
{
persons.insert(p);
}
#else
persons.insert(people.begin(), people.end());
#endif
std::cout << "People named Bob: \n";
auto &name_index = persons.get<0>();
auto range2 = name_index.equal_range("Bob");
for (auto it = range2.first; it != range2.second; ++it) {
std::cout << it->name << ", " << it->age << "\n";
}
return 0;
}
Both insert_or_assign and try_emplace would be really handy on multi_index but especially try_emplace. Are they going to be implemented any time soon?
(copied from https://svn.boost.org/trac10/ticket/13331, only MultiIndex's parts from the attached report)
Boost 1.57.0
A static analysis tool called Coverity found medium and high defects in the boost source code. See attached file for defect type, defect category, filename and line number of defect.
| Defect Type | Defect Category | Line Number | Filename |
|---|---|---|---|
| Uninitialized pointer field | Uninitialized members | 990 | /boost/include/boost/multi_index/ordered_index.hpp |
The following program does not compile (https://wandbox.org/permlink/odsAUNRroBveTxqw). (I tested clang 8.0.0 and g++ 9.1.0.)
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/key.hpp>
struct S final {
int m_n;
S(int n) noexcept : m_n(n) {}
int Get() const & noexcept { // removing "& noexcept" makes it compile
return m_n;
}
};
int main() {
boost::multi_index::multi_index_container<
S,
boost::multi_index::indexed_by<
boost::multi_index::ordered_unique<
boost::multi_index::key<&S::Get>
>
>
> container;
}
clang 8.0.0 reports:
In file included from prog.cc:3:
/opt/wandbox/boost-1.70.0/clang-8.0.0/include/boost/multi_index/key.hpp:77:22: error: implicit instantiation of undefined template 'boost::multi_index::detail::typed_key_impl<int (S::*)() const & noexcept, &S::Get, void>'
struct key_impl<Key>:typed_key_impl<decltype(Key),Key>{};
^
/opt/wandbox/boost-1.70.0/clang-8.0.0/include/boost/multi_index/key.hpp:134:23: note: in instantiation of template class 'boost::multi_index::detail::key_impl<&S::Get>' requested here
using type=typename key_impl<Keys...>::type;
^
/opt/wandbox/boost-1.70.0/clang-8.0.0/include/boost/multi_index/key.hpp:140:1: note: in instantiation of template class 'boost::multi_index::detail::limited_size_key_impl<&S::Get>' requested here
using key=typename detail::limited_size_key_impl<Keys...>::type;
^
prog.cc:18:37: note: in instantiation of template type alias 'key' requested here
boost::multi_index::key<&S::Get>
^
/opt/wandbox/boost-1.70.0/clang-8.0.0/include/boost/multi_index/key.hpp:38:8: note: template is declared here
struct typed_key_impl;
^
prog.cc:20:9: error: expected a type
>
^
prog.cc:21:5: error: expected a type
> container;
^
prog.cc:21:7: error: C++ requires a type specifier for all declarations
> container;
^
4 errors generated.
I suspect that the problem is that key_impl is not specialized for const& and/or noexcept member functions.
For example, on this page, there are three question mark characters in places where an ellipsis (...) would be expected.
If we want to follow std::set::insert, then insert should have no effect if insertion did not take place. Otherwise, insert is unusable in cases when collisions are expected as loosing the input argument is an unlikely intent by the caller.
Reproduction:
https://godbolt.org/z/bofeMo8fd
#include <memory>
#include <vector>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/identity.hpp>
#include <boost/multi_index/indexed_by.hpp>
#include <boost/multi_index/mem_fun.hpp>
#include <boost/multi_index/sequenced_index.hpp>
#include <boost/multi_index/tag.hpp>
#include <boost/multi_index_container.hpp>
class Base {
public:
virtual size_t GetId() const = 0;
virtual ~Base() = default;
};
class Derived : public Base {
public:
size_t GetId() const { return 42; }
};
int main(int, char**) {
// A tag to view elements in the order of insertion.
struct Sequenced{};
// A tag to view elements in the order sorted by type id.
struct Ordered{};
using ContainerType = boost::multi_index_container<
// Elements are pointers to Base.
std::unique_ptr<Base>,
boost::multi_index::indexed_by<
boost::multi_index::sequenced<boost::multi_index::tag<Sequenced>>,
boost::multi_index::hashed_unique<
boost::multi_index::tag<Ordered>,
boost::multi_index::const_mem_fun<Base, size_t,
&Base::GetId>>>>;
ContainerType container;
// Insert first element.
auto& ordered_view = container.get<Ordered>();
auto new_element = std::make_unique<Derived>();
auto insert_result = ordered_view.insert(std::move(new_element));
if (!insert_result.second) return -1;
// Try toInsert second element with the same key.
auto new_element2 = std::make_unique<Derived>();
auto insert_result2 = ordered_view.insert(std::move(new_element2));
assert(!insert_result2.second);
assert(new_element2->GetId() == 42);
}
Situation
We are storing a Multi-Index in a Boost Interprocess Shared Memory that is accessed by a 32bit process and a 64bit process. The 32bit process or the 64bit process can be the creator of the object.
Symptoms
If a 64bit process creates the Multi-Index, the 32bit process will crash trying to retrieve it and vice-versa.
If a 64bit process inserts object into te Multi-Index, the 32bit process will fail to retrieve them by hashing and vice-versa.
Solution
I had to modify some headers so that the sizeof of the Multi-Index is exactly the same in 32 and 64bits.
In my own code, I force the hashing to be on 32bit instead of size_t. I extracted some Boost hash function to do so. But there is still issue with the composite_key. It will perform bitwise operation on a size_t carry which will yield different result if on a 32bit or 64bit.
See patch attached.
boost-1.68.0-fix-interoperability-32-64-multi_index.patch.zip
See related issue for Boost Unordered boostorg/unordered#9
Currently, we cannot use multi_index with c++17 std::pmr::polymorphic_allocator, because multi_index didn't provide copy/move constructors with an extra allocator parameter.
For example, as shown in https://www.boost.org/doc/libs/1_72_0/libs/multi_index/doc/reference/multi_index_container.html#constructors),
multi_index only provided the following copy/move constructors
multi_index_container(const multi_index_container<Value,IndexSpecifierList,Allocator>& x); multi_index_container(multi_index_container<Value,IndexSpecifierList,Allocator>&& x);
The following two constructors are not provided.
multi_index_container(const multi_index_container<Value,IndexSpecifierList,Allocator>& x, const allocator_type& alloc); multi_index_container(multi_index_container<Value,IndexSpecifierList,Allocator>&& x, const allocator_type& alloc);
According to https://en.cppreference.com/w/cpp/named_req/AllocatorAwareContainer, these two special constructors are required when used with nested containers, such as
std::pmr::vector<boost::multi_index::multi_index_container<T, ..., std::pmr::polymorphic_allocator<T>>>.
Could you please add these special constructors?
I have tested the following code in boost 1.71. It seems working, but I am not very sure about it.
multi_index_container( const multi_index_container<Value,IndexSpecifierList,Allocator>& x, const Allocator& al): bfm_allocator(al), bfm_header(), super(x), node_count(0) { copy_map_type map(bfm_allocator::member,x.size(),x.header(),header()); for(const_iterator it=x.begin(),it_end=x.end();it!=it_end;++it){ map.clone(it.get_node()); } super::copy_(x,map); map.release(); node_count=x.size(); /* Not until this point are the indices required to be consistent, * hence the position of the invariant checker. */ BOOST_MULTI_INDEX_CHECK_INVARIANT; } multi_index_container(BOOST_RV_REF(multi_index_container) x, const Allocator& al): bfm_allocator(al), bfm_header(), super(x,detail::do_not_copy_elements_tag()), node_count(0) { BOOST_MULTI_INDEX_CHECK_INVARIANT; BOOST_MULTI_INDEX_CHECK_INVARIANT_OF(x); swap_elements_(x); }
Thanks a lot!
Inspired by std::make_tuple for std::tuple..
I recently tried to create 4 simple make methods for types from this library:
template<typename T, typename M>
ordered_unique<T, M> make_ordered_unique(T, M)
{
return {};
}
template<typename T, typename M>
ordered_non_unique<T, M> make_ordered_non_unique(T, M)
{
return {};
}
template<typename... T>
indexed_by<T...> make_indexed_by(T...)
{
return {};
}
template<typename T, typename I>
multi_index_container<T, I> make_multi_index_container(I)
{
return {};
}
These methods allow me to write like this:
auto es = make_multi_index_container<employee>(make_indexed_by(
make_ordered_unique( tag<id>{}, BOOST_MULTI_INDEX_MEMBER(employee,int,id){}),
make_ordered_non_unique( tag<name>{},BOOST_MULTI_INDEX_MEMBER(employee,std::string,name){}),
make_ordered_non_unique( tag<age>{}, BOOST_MULTI_INDEX_MEMBER(employee,int,age){})));
..And the same code without methods (how it works now):
typedef multi_index_container<
employee,
indexed_by<
ordered_unique<
tag<id>, BOOST_MULTI_INDEX_MEMBER(employee,int,id)>,
ordered_non_unique<
tag<name>,BOOST_MULTI_INDEX_MEMBER(employee,std::string,name)>,
ordered_non_unique<
tag<age>, BOOST_MULTI_INDEX_MEMBER(employee,int,age)> >
> employee_set;
employee_set es;
In my opinion, the variant with make-methods is much better. Why not support for these methods on the library side?
It seems that boost/multi_index/detail/define_if_constexpr_macro.hpp is included inside inline member functions (multi_index_container.hpp around line 370 for instance). define_if_constexpr_macro.hpp #includes <boost/config.h>. That's problematic.
It causes problems with clang implicit modules, if one tries to make boost/config.h (/and/ its entire subgraph) importable headers (and by implication C++20 header units).
But AFAICT, it's just plain wrong, because boost/config.hpp can expand to namespace-scope code on first inclusion -- config/detail/suffix.hpp contains typedefs for a 64bit int type and templates for missing min/max fns. So if define_if_constexpr_macro.hpp contains the first inclusion, things will go sadly wrong anyway. (I don't think this happens, because the users of define_if_constexpr_macro have already included config.hpp.
Either remove the #include <boost/config.hpp> from define_if_constexpr_macro.hpp or replace it with something like:
-#include <boost/config.hpp>
+#ifndef BOOST_CONFIG_HPP
+// We can't #include config.hpp ourselves as it can expand to
+// top-level source, and this file is intended for inclusion inside
+// functions (for instance).
+#error "#include <boost/config.hpp> missing"
+#endif
Can we switch this library over to mp11 and require C++11 or later?
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
Django
The Web framework for perfectionists with deadlines.
Laravel
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
Microsoft
Open source projects and samples from Microsoft.
Google
Google ❤️ Open Source for everyone.
Alibaba
Alibaba Open Source for everyone
D3
Data-Driven Documents codes.
Tencent
China tencent open source team.